题目大意
给你 \(m\) 条线段 \((a_i,b_i)\)，再给 \(n\) 个区间 \([l_i,r_i]\)，\(q\) 次操作，
- \(\texttt{A x y}\) 添加一条线段 \((x,y)\)，其编号为最后一条线段加一。
- \(\texttt{C x}\) 查询 \([l_x,r_x]\) 和线段有交集（在边界点也算）的最长编号区间。
- \(\texttt{Q}\) 查询 \(\operatorname{xor}_{i=1}^n \texttt{C i}\)。
保证 \(q\le 2\times 10^5\)，\(\texttt{Q}\) 操作不超过 20 次。
\(1\le l_i,r_i,a_i,b_i \le V=4\times 10^5\)。
解法
一开始考虑，感觉维护很困难，考虑一条线段对一个区间的贡献。
对于线段 \((a_i,b_i)\)，有且仅有以下区间会和其有交：
- \(a_i\le l_i\le b_i\) 或 \(a_i\le r_i\le b_i\)。
- \(l_i<a_i\) 且 \(r_i>b_i\)。
这像不像在 \(V \times V\) 的矩形上进行操作？转换一下就是：区间 \(i\) 在矩形上的答案是点 \((l_i,r_i)\) 的值。令一轴为 \(l\)，另一轴为 \(r\)，那么对于第一种情况，要操作的即为图中的黄色部分，第二种情况为绿色部分。
考虑如何计算最长连续区间。
如果令图中有颜色的部分 +1，那么变成了计算被几条线段交到。
但是如果同时令没有颜色的部分清零，我们发现，只要记录每个点的历史最大值，即为答案（最长连续段）。
也就是说，答案一定是某一次清零开始，一直 +1，然后又被清零。
注意到矩形上的有效值（被用到的值）只有 \(n\) 个，可以考虑使用 kdt 维护。
这时候转化成为了子树加 1，子树清零，单点加 1，单点清零，求单点历史最大值的问题。
但是怎么做历史最大值？
对于最暴力的方法，访问到一个点就按照上面方法修改其值，无法通过。
考虑对子树打标记，如果标记下传是 \(O(1)\) 的，那么复杂度为 \(O(n\sqrt n)\)，可以接受。
考虑每次访问到一个点就 pushdown，那么到达该点时该点一定没有标记。于是可以方便地添加标记。
现在考虑 pushdown 怎样下放标记。
考虑最暴力，最正确直接地：按时间先后维护标记队列，每次直接把队列插到儿子节点队列的后方，从前到后计算，正确性显然。
约定：标记有 +1，赋值（不一定置零）两种，命名为 \(t1,t0\)。
于是标记队列有下面几种可能：
- \(t1,t1,\cdots,t1 (1)\)
- \(t1,t1,\cdots,t1,t0,t0,\cdots,t0 (2)\)，当然也包括不存在 \(t1\) 的情况。
- \(t1,t0,t1,t1,t0,\cdots,t1,t0 (3)\)，即混乱的。
接下来考虑将 \((3)\) 转化为 \((2)\)。
注意到一次 \(t0\) 将值清零，于是后面的加法标记和赋值标记等价（清零后子树加 1，答案全为 1）。变为 \((2)\)。
于是对于一个点的标记，维护一个 \(typ\) 表示是否存在 \(t0\) 标记。（有为 1，否则为 0）。
维护 \(pre\) 表示前面有几个 \(t1\)，\(mx\) 表示赋值标记的最大值。
维护 \(lst\) 表示从 \(0\) 开始进行标记队列的操作最后的值。
维护 \(v\) 表示单点加、单点赋值后的值。注意，因为访问到某一个点时该点没有标记，于是单点加、单点赋值一定在标记队列头部 之前 ，方便了计算 \(v\) 的值。
维护 \(vmx\) 表示从单点操作开始到走完标记队列得到的最大值。即 \(\max(v+pre,mx)\)
维护 \(hmx\) 表示历史最大值（答案）。
于是对于父节点的值，考虑子节点怎么接收：令父节点的各值后面加上 \('\) 方便区分。即 \(pre_{fa}\to pre'\)。
- \(typ=1\)
- \(typ'=1\)
- \(mx=\max(mx,mx',lst+pre')\)
- \(vmx=\max(v+pre,mx)\)
- \(lst=lst'\)
- \(typ'=0\)
- \(mx=\max(mx,mx',lst+pre')\)
- \(vmx=\max(v+pre,mx)\)
- \(lst=lst+pre'\)
- \(typ'=1\)
- \(typ=0\)
- \(typ'=1\)
- \(typ=1\)
- \(mx=mx'\)
- \(pre=pre'\)
- \(vmx=\max(mx,pre+v)\)
- \(lst=lst'\)
- \(typ'=0\)
- \(pre=pre+pre'\)
- \(lst=pre\)
- \(vmx=v+pre\)
- \(typ'=1\)
记得随手更新 \(hmx\)。
上面的转移看起来复杂，其实自己画一画能够理解的。
附上卡常代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5, V = 4e5;
struct pos {int l[2], r[2];};
struct point {int x[2];};
struct arr{point v; int id;} b[N];
struct node
{
int v, vmx;
node *ls, *rs, *fa;
pos p; point u;
int pre, lst, mx, hmx;
bool typ, tg;
inline void add(int w)
{
tg = 1;
if(typ) mx = max(mx, lst + w);
else pre = lst + w;
lst += w;
updhmx();
}
inline void to0() {tg = typ = 1; mx = lst = v = 0;}
inline void updhmx()
{
vmx = max(vmx, v + pre);
if(typ) hmx = max(hmx, mx);
hmx = max(hmx, vmx);
}
inline void clrtg() {v = (typ ? lst : v + pre); tg = mx = pre = typ = lst = 0;}
inline void upd(int _pre, int _lst, int _mx, bool _typ)
{
tg = 1;
if(typ)
{
mx = max(mx, max(_mx, lst + _pre));
if(_typ) lst = _lst;
else lst += _pre;
vmx = max(v + pre, mx);
}
else if(_typ)
{
typ = 1;
mx = _mx;
pre += _pre;
vmx = max(mx, pre + v);
lst = _lst;
}
else
{
pre += _pre;
lst = pre;
vmx = v + pre;
}
updhmx();
}
} a[N];
node* pp[N];
int n, m, q, bl[N], br[N], idx;
inline void pd(node* x)
{
if(!x->tg) return;
if(x->ls != nullptr) x->ls->upd(x->pre, x->lst, x->mx, x->typ);
if(x->rs != nullptr) x->rs->upd(x->pre, x->lst, x->mx, x->typ);
x->clrtg();
}
node* build(int l, int r, int d, node *fa)
{
int x = ++idx;
int mid = l + r >> 1;
a[x].fa = fa;
nth_element(b + l, b + mid, b + r + 1, [&](arr &x, arr &y) {return x.v.x[d] < y.v.x[d];});
a[x].u = b[mid].v;
pp[b[mid].id] = &a[x];
if(mid > l) a[x].ls = build(l, mid - 1, d ^ 1, &a[x]);
if(mid < r) a[x].rs = build(mid + 1, r, d ^ 1, &a[x]);
a[x].p = {b[mid].v.x[0], b[mid].v.x[1], b[mid].v.x[0], b[mid].v.x[1]};
for(int i : {0, 1}) a[x].p.l[i] = min(a[x].p.l[i], min(a[x].ls->p.l[i], a[x].rs->p.l[i]));
for(int i : {0, 1}) a[x].p.r[i] = max(a[x].p.r[i], max(a[x].ls->p.r[i], a[x].rs->p.r[i]));
return &a[x];
}
inline bool out(pos& x , pos& p) {return x.l[0] > p.r[0] || x.l[1] > p.r[1] || x.r[0] < p.l[0] || x.r[1] < p.l[1]; }
inline bool out(point& x, pos& p) {return x.x[0] > p.r[0] || x.x[1] > p.r[1] || x.x[0] < p.l[0] || x.x[1] < p.l[1]; }
inline bool in (pos& x , pos& p) {return x.l[0] >= p.l[0] && x.l[1] >= p.l[1] && x.r[0] <= p.r[0] && x.r[1] <= p.r[1];}
inline bool in (point& x, pos& p) {return x.x[0] >= p.l[0] && x.x[0] <= p.r[0] && x.x[1] >= p.l[1] && x.x[1] <= p.r[1];}
void upd(node* x, int d, pos& p, pos& q1, pos& q2)
{
pd(x);
bool o1 = out(x->p, p), o2 = out(x->p, q1), o3 = out(x->p, q2);
if(o1 && o2 && o3) return;
if(!o1 && in(x->p, p))
{
x->add(1);
return;
}
if((!o2 && in(x->p, q1)) || (!o3 && in(x->p, q2)))
{
x->to0();
return;
}
if(in(x->u, p))
{
x->v ++;
x->updhmx();
}
else x->v = 0;
if(x->ls) upd(x->ls, d ^ 1, p, q1, q2);
if(x->rs) upd(x->rs, d ^ 1, p, q1, q2);
}
node* rt;
inline void add(int l, int r)
{
pos p = {0, l, r, V}, q1 = {0, 0, l - 1, l - 1}, q2 = {r + 1, r + 1, V, V};
upd(rt, 0, p, q1, q2);
}
const int maxn = (1 << 23);
char buf[maxn], *S = buf, *T = buf;
inline char gc() {return (S == T ? (T = (S = buf) + fread(buf, 1, maxn, stdin), (S == T) ? EOF : *S ++) : *S ++);}
inline void read(int &x)
{
x = 0; char c = gc();
while(!isdigit(c)) c = gc();
while(isdigit(c)) x = x * 10 + c - '0', c = gc();
x = x;
}
inline void rdch(char &c) {c = gc(); while(!isalpha(c)) c = gc();}
inline void pdt(node* x) {if(!x) return; pdt(x->fa); pd(x);}
signed main()
{
for(int i = 0; i < N; i ++) a[i].ls = a[i].rs = &a[0];
a[0].p = {(int)1e9, (int)1e9, (int)-1e9, (int)-1e9};
read(n), read(m), read(q);
for(int i = 1; i <= n; i ++) read(bl[i]), read(br[i]), b[i] = {bl[i], br[i], i};
rt = build(1, n, 0, nullptr);
for(int i = 1; i <= m; i ++)
{
int l, r; read(l), read(r);
add(l, r);
}
int cc;
for(int i = 1; i <= q; i ++)
{
char op;
rdch(op);
if(op == 'A')
{
int l, r; read(l), read(r);
add(l, r);
}
else if(op == 'C')
{
int x; read(x);
pdt(pp[x]); cout << pp[x]->hmx << "\n";
}
else
{
int ans = 0;
for(int j = 1; j <= n; j ++) {pdt(pp[j]); ans ^= pp[j]->hmx;}
cout << ans << "\n";
}
}
return 0;
}