ACM特定算法的卡常优化

今天做一道树链剖分的题目，发现被卡常了，于是修改了很久，打印出运行时间，发现有这3个地方对常数的影响特比大

1. I/O:           

          用输入外挂所消耗的时间大概是用关同步+tie的cin的一半

         测试:输入了1e5*3的数据,cin用了0.2s,IN用了0.1s

2. vector[]/链式前向星

         不得不说cache友好真的是强

         1e5条带权边,

         

 

存图方式	存图时间	dfs耗时
vector[]+push_back	0.7	0.2
vector[]+   (++cnt)	0.5	0.2
别人的链式前向星	0.3	0.05
我的链式前向星	0.2	0.03

3.vector[]优化

        从上表也可以看出,事先resize()掉vector可以防止中途重新分配内存，可以加速，但好像效果也不是很明显，现在就先不管了吧

 

4.线段树优化

        找到了2种update和2种query的写法

void update(int o, int l, int r, int v)//区间加v
{
	if (l > r)return;
	if (e[o].l == l && e[o].r == r) { S_T(o, v); return; }//找到边缘

	PushDown(o);
	update(ls, max(e[ls].l, l), min(r, mid), v);
	update(rs, max(mid + 1, l), min(e[rs].r, r), v);
	PushUp(o);
}
void update2(int o, int l, int r, int v)//单点加v
{
	if (l <= e[o].l&&e[o].r <= r) { S_T(o, v); return; }
	if (max(l, e[o].l) > min(r, e[o].r))return;//舍弃

	PushDown(o);
	update2(ls, l, r, v);
	update2(rs, l, r, v);
	PushUp(o);
}

  以及query

ll query(int o, int l, int r)//done
{
	if (l > r)return 0;
	if (e[o].l == l && e[o].r == r)return e[o].sum;
	PushDown(o);
	PushUp(o);
	return query(ls, max(l,e[ls].l), min(r, mid)) + query(rs, max(l, mid + 1), min(r,e[rs].r));
}
ll query2(int o,int l,int r)
{
	if(e[o].l==l&&e[o].r==r)return e[o].sum;
	PushDown(o);
	PushUp(o);
	if(r<=mid)return query2(ls,l,r);
	else if(mid+1<=l)return query2(rs,l,r);
	else return query2(ls,l,mid)+query(rs,mid+1,r);
}
ll query3(int o,int l,int r)
{
	if(max(l,e[o].l)>min(r,e[o].r))return 0;
	if(e[o].l==e[o].r)return e[o].sum;
	PushDown(o);
	PushUp(o);
	return query(ls,l,r)+query(rs,l,r);
}

这里还加了1种，以上三种,比较常见的是2和3,1是我写的，是2和3的折衷，其实效率不高，写起来虽然比2好但不如3

效率:2>1>3

好写:3>1>2