AC后的对树上莫队的疑惑?
查看原帖
AC后的对树上莫队的疑惑?
389985
最後の祈りを楼主2021/12/7 18:56

如果使询问保持l<r,即 使括号序上的询问区间保持l<r,这样却出现了错误。

对于树上询问,将树上[x,y]路径->括号序[first[x],first[y]]或[last[x],first[y]]+lca(x,y)的区间处理,那么这个区间不应该满足l<=r吗?

即取消掉如下注释会全部WA掉:

void modui()	//o[]为树的括号序
{
	sort(q+1,q+1+cntq);
	int nowl=q[1].l,nowr=nowl-1,nowt=0;
	for(rint i=1;i<=cntq;i++)
	{
		int l=q[i].l,r=q[i].r,t=q[i].t;
//		if(l>r) swap(l,r);
		while(nowl>l) add(o[--nowl]);
		while(nowr<r) add(o[++nowr]);
		while(nowl<l) add(o[nowl++]);
		while(nowr>r) add(o[nowr--]);
		if(q[i].fa) add(q[i].fa);
		while(nowt<t) change(++nowt);
		while(nowt>t) change(nowt--);
		ans[q[i].id]=nowans;
		if(q[i].fa) add(q[i].fa);
	}
}
2021/12/7 18:56
加载中...