JZOJ 5067 有理有据题

考虑加入一个建筑的同时维护每个炸弹能摧毁的最长后缀的长度。
若一个炸弹能摧毁，则令其加一，否则令其覆盖为 0。
则只需要维护历史最值即可。

然后就把线段树历史最值的标记套到 K-D Tree 上……
另外修改的时候建议两种修改一起做，否则会被卡常（

代码：

#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
#include <cstdio>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}
inline char getc()
{
    char ch = 0;
    for(;ch < 'A' || ch > 'Z';ch = gc());
    return ch;
}

const int N = 5e4;
const int V = 4e5;
int n,m,q;
struct node
{
    int x,y,dim;
    int L,R,D,U;
    int ls,rs;
    int add,set,val;
    int Add,Set,Val;
} kdt[N + 5];
int a[N + 5],rt;
inline bool cmp1(int x,int y)
{
    return kdt[x].x < kdt[y].x;
}
inline bool cmp2(int x,int y)
{
    return kdt[x].y < kdt[y].y;
}
inline void up(int p)
{
    kdt[p].L = kdt[p].R = kdt[p].x,
    kdt[p].D = kdt[p].U = kdt[p].y;
    if(kdt[p].ls)
        kdt[p].L = min(kdt[p].L,kdt[kdt[p].ls].L),kdt[p].R = max(kdt[p].R,kdt[kdt[p].ls].R),
        kdt[p].D = min(kdt[p].D,kdt[kdt[p].ls].D),kdt[p].U = max(kdt[p].U,kdt[kdt[p].ls].U);
    if(kdt[p].rs)
        kdt[p].L = min(kdt[p].L,kdt[kdt[p].rs].L),kdt[p].R = max(kdt[p].R,kdt[kdt[p].rs].R),
        kdt[p].D = min(kdt[p].D,kdt[kdt[p].rs].D),kdt[p].U = max(kdt[p].U,kdt[kdt[p].rs].U);
}
int build(int l,int r)
{
    if(l > r)
        return 0;
    int mid = l + r >> 1;
    double av1 = 0,av2 = 0,v1 = 0,v2 = 0;
    for(register int i = l;i <= r;++i)
        av1 += kdt[a[i]].x,av2 += kdt[a[i]].y;
    av1 /= r - l + 1,av2 /= r - l + 1;
    for(register int i = l;i <= r;++i)
        v1 += (kdt[a[i]].x - av1) * (kdt[a[i]].x - av1),
        v2 += (kdt[a[i]].y - av2) * (kdt[a[i]].y - av2);
    if(v1 > v2)
        nth_element(a + l,a + mid,a + r + 1,cmp1),kdt[a[mid]].dim = 1;
    else
        nth_element(a + l,a + mid,a + r + 1,cmp2),kdt[a[mid]].dim = 2;
    kdt[a[mid]].set = kdt[a[mid]].Set = -1;
    kdt[a[mid]].ls = build(l,mid - 1),kdt[a[mid]].rs = build(mid + 1,r);
    up(a[mid]);
    return a[mid];
}
inline void push_add(int p,int add,int Add)
{
    if(~kdt[p].set)
        kdt[p].Set = max(kdt[p].Set,kdt[p].set + Add),
        kdt[p].Val = max(kdt[p].Val,kdt[p].val + Add),
        kdt[p].set += add,kdt[p].val += add;
    else
        kdt[p].Add = max(kdt[p].Add,kdt[p].add + Add),
        kdt[p].Val = max(kdt[p].Val,kdt[p].val + Add),
        kdt[p].add += add,kdt[p].val += add;
}
inline void just_add(int p,int add)
{
    kdt[p].Val = max(kdt[p].Val,kdt[p].val + add),
    kdt[p].val += add;
}
inline void push_set(int p,int set,int Set)
{
    kdt[p].Set = max(kdt[p].Set,Set),
    kdt[p].Val = max(kdt[p].Val,Set),
    kdt[p].set = kdt[p].val = set;
}
inline void just_set(int p,int set)
{
    kdt[p].Val = max(kdt[p].Val,set),
    kdt[p].val = set;
}
inline void push(int p)
{
    kdt[p].ls && (push_add(kdt[p].ls,kdt[p].add,kdt[p].Add),1),
    kdt[p].rs && (push_add(kdt[p].rs,kdt[p].add,kdt[p].Add),1),
    kdt[p].add = kdt[p].Add = 0;
    if(~kdt[p].set)
        kdt[p].ls && (push_set(kdt[p].ls,kdt[p].set,kdt[p].Set),1),
        kdt[p].rs && (push_set(kdt[p].rs,kdt[p].set,kdt[p].Set),1),
        kdt[p].set = kdt[p].Set = -1;
}
int R,D;
void update(int p)
{
    if(!p)
        return ;
    if(R >= kdt[p].R && D <= kdt[p].D)
    {
        push_add(p,1,1);
        return ;
    }
    if(R < kdt[p].L || D > kdt[p].U)
    {
        push_set(p,0,0);
        return ;
    }
    if(R >= kdt[p].x && D <= kdt[p].y)
        just_add(p,1);
    else
        just_set(p,0);
    push(p);
    update(kdt[p].ls),update(kdt[p].rs);
}
int query(int p)
{
    if(!p || R < kdt[p].L || R > kdt[p].R || D < kdt[p].D || D > kdt[p].U)
        return 0;
    if(R == kdt[p].x && D == kdt[p].y)
        return kdt[p].Val;
    push(p);
    return query(kdt[p].ls) | query(kdt[p].rs);
}
int query_all(int p)
{
    if(!p)
        return 0;
    push(p);
    return kdt[p].Val ^ query_all(kdt[p].ls) ^ query_all(kdt[p].rs);
}
int main()
{
    freopen("bomb.in","r",stdin),freopen("bomb.out","w",stdout);
    read(n),read(m),read(q);
    for(register int i = 1;i <= n;++i)
        read(kdt[i].x),read(kdt[i].y),a[i] = i;
    rt = build(1,n);
    for(;m;--m)
        read(D),read(R),
        update(rt);
    char op;
    for(int x;q;--q)
    {
        op = getc();
        if(op == 'A')
            read(D),read(R),
            update(rt);
        else if(op == 'C')
            read(x),R = kdt[x].x,D = kdt[x].y,
            printf("%d\n",query(rt));
        else
            printf("%d\n",query_all(rt));
    }
}