【BZOJ5223】有理有据题（K

有理有据题（K"/>

【BZOJ5223】有理有据题（K

题目大意

有n颗炸弹，第i颗炸弹的爆炸范围为 [ l i , r i ] [l_i,r_i] [li​,ri​].
有m个房子，标号为i的房子为一条线段 [ a i , b i ] [a_i,b_i] [ai​,bi​]
（只要房子线段与炸弹相交视为炸弹能摧毁房子）
几种操作：
A x y：增加一个房子 [ x , y ] [x,y] [x,y]，按顺序标号。
C i：查询第i个炸弹能炸毁的连续标号的房子，最多连续多少个。
Q：查询每个C 1~n结果的异或和（保证该操作数很少）

题解

给每个炸弹维护一个权值val，增加一个房子，给能炸到这个房子的炸弹val+1，不能炸到房子的炸弹val改为0。每个炸弹记录一个历史最高值，这个最高值即这颗炸弹的答案。

现在我们需要一种数据结构，能快速找到一个房子能被哪些炸弹炸到，即一条线段与哪些线段相交。
并且这个数据结构能快速修改大量的权值，即+1和清0。

线段 [ l i , r i ] [l_i,r_i] [li​,ri​]与 [ l j , r j ] [l_j,r_j] [lj​,rj​]相交，当且仅当 l i ≤ r j l_i \leq r_j li​≤rj​且 l j ≤ r i l_j \leq r_i lj​≤ri​。
线段树是不能完成的。
但是K-D Tree却可以。

将每个炸弹当作一个点 ( l i , r i ) (l_i,r_i) (li​,ri​)，建一棵K-D Tree，每个结点存储子树中x,y坐标的最小最大值，方便修改权值时能利用懒标记批量修改。

节点上存储：
now：当前这个炸弹的权值
best：历史最高权值

接着就是一大堆懒标记。
add：这个结点的子树需增加的值（不包含此节点）
clean：这个结点的子树需要清0

然而没这么简单：如果一棵子树本来有add标记，如果此时clean，会把add清0，但add还没有往下传去更新其它炸弹的best，所以还需要一些标记。
pre：表示这个结点已被清0，但有pre的值需往下传。（如果此标记不为0，则clean一定为true）

如果一个子树有add，然后被清0（此时pre有值），然后再被多次add，再次被清0。第二次add的值就不能存储在pre中了（因为第一次clean的操作中已有pre还没有下传）。但可以发现因为第一次已经清0，第二次add后，整个子树的值都为add。如果这个子树多次被add，然后clean。我们需要记录一个mxadd，表示子树被增加的最大权值。
mxadd：表示此子树虽未将清0操作下传，但之后又进行了add，且使得整个子树最优答案达到了mxadd

然后讲K-D Tree中下传标记的操作。
首先检查是否有clean
如果有clean，首先需下传pre。用pre+子节点的now来更新子节点best。
如果子节点没有clean标记，则将pre加到子节点的pre上，否则将pre更新到子节点的mxadd上
然后下传clean标记
如果子节点没有clean标记，则把子节点的add加到子节点的pre上，并把clean标上。
否则，把子节点的add更新子节点的mxadd。
然后下传add标记，直接加在子节点的add和now上即可，记得更新子节点的best。
然后下穿mxadd，用mxadd更新子节点的best和子节点的mxadd

最后记得清掉当前结点的所有懒标记。

代码

调了一整天。。。

#include<cstdio>
#include<assert.h>
#include<algorithm>
using namespace std;
const int MAXN=300005;int N,M,Q;struct Node
{int x,y,id;int now,best;int maxx,maxy,minx,miny;int add,pre,mxadd;bool clean;Node *son[2],*fa;void PushUp(){maxx=minx=x;maxy=miny=y;for(int i=0;i<2;i++)if(son[i]){maxx=max(maxx,son[i]->maxx);maxy=max(maxy,son[i]->maxy);minx=min(minx,son[i]->minx);miny=min(miny,son[i]->miny);}}void PushDown(){assert(pre==0||(pre!=0&&clean==true));for(int i=0;i<2;i++)if(son[i]){if(clean){son[i]->best=max(son[i]->best,son[i]->now+pre);if(son[i]->clean)son[i]->mxadd=max(son[i]->mxadd,son[i]->add+pre);elseson[i]->pre+=son[i]->add+pre;son[i]->now=son[i]->add=0;son[i]->clean=true;}if(add){son[i]->now+=add;son[i]->add+=add;son[i]->best=max(son[i]->best,son[i]->now);}son[i]->best=max(son[i]->best,mxadd);son[i]->mxadd=max(son[i]->mxadd,mxadd);}add=pre=mxadd=0;clean=false;}
}bomb[MAXN],*root;bool cmpx(const Node &a,const Node &b){return a.x<b.x;}
bool cmpy(const Node &a,const Node &b){return a.y<b.y;}Node *Build(int L=1,int R=N,int d=0)
{int mid=(L+R)/2;nth_element(bomb+L,bomb+mid,bomb+R+1,d==0?cmpx:cmpy);swap(bomb[L],bomb[mid]);Node *u=&bomb[L];if(L<mid){u->son[0]=Build(L+1,mid,d^1);u->son[0]->fa=u;}if(mid<R){u->son[1]=Build(mid+1,R,d^1);u->son[1]->fa=u;}u->PushUp();return u;
}
void Add(int x,int y,Node *u=root)//find x <= u->y && u->x <= y
{assert(u->pre==0||(u->pre!=0&&u->clean==true));if(x>u->maxy||u->minx>y){if(u->clean)u->mxadd=max(u->mxadd,u->add);elseu->pre=u->add;u->clean=true;u->now=u->add=0;return;}if(x<=u->miny&&u->maxx<=y){u->add++;u->now++;u->best=max(u->best,u->now);return;}if(x<=u->y&&u->x<=y){u->now++;u->best=max(u->best,u->now);}elseu->now=0;u->PushDown();if(u->son[0])Add(x,y,u->son[0]);if(u->son[1])Add(x,y,u->son[1]);
}int pos[MAXN];int main()
{scanf("%d%d%d",&N,&M,&Q);for(int i=1;i<=N;i++){scanf("%d%d",&bomb[i].x,&bomb[i].y);bomb[i].id=i;}root=Build();for(int i=1;i<=N;i++)pos[bomb[i].id]=i;for(int i=1,l,r;i<=M;i++){scanf("%d%d",&l,&r);Add(l,r);}while(Q--){char op[3];int a,b,ans;scanf("%s",op);if(op[0]=='A'){scanf("%d%d",&a,&b);Add(a,b);}else if(op[0]=='C'){scanf("%d",&a);Node *u=&bomb[pos[a]];int sum=0;ans=u->best;sum=u->now;u=u->fa;while(u){sum+=u->pre;if(u->clean){ans=max(ans,sum);sum=0;}sum+=u->add;ans=max(ans,u->mxadd);u=u->fa;}ans=max(ans,sum);printf("%d\n",ans);}else{ans=0;for(int i=1;i<=N;i++){ans^=bomb[i].best;bomb[i].PushDown();}printf("%d\n",ans);}}return 0;
}