JZOJ 5067 有理有据题

发表于 | 分类于 |

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

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

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#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));
    }
}