前言
断续地调了一天一夜，终于做出来了！
题目链接-Rectangle Painting
大概就是：给 \(n\) 个集合 \(S_i\)，两种操作，
1 {[l,r],x }l r向 \(S_l\) 到 \(S_r\) 插入 \(x\)2 l r询问 \(\max\limits_{i=l}^r \{\text{mex}(S_i)\}\)。
但是强制在线！
\(1\le n,l,r\le 2\times 10^5,1\le q\le 10^5,\texttt{10s,1024MiB}\)
解题思路
乍一看很不可做，但是可以尝试枚举答案。
先开 \(N\) 颗线段树，每棵树 \(T_i\) 存储从每个集合里是否有 \(col_i\)。
计算答案时一个节点 \(x\) 的答案 \(Ans_x=\max\limits_{i=l}^r \{\text{mex}(S_i)\}=\max\{Ans_{ls_x},Ans_{rs_x}\}\) ,即两个儿子的答案最大值。
但是维护一个节点的 \(mex\) 是 \(O(n)\) 的，并且不支持懒标记，怎么优化？
先把每个节点 \(j\) 对每个颜色 \(x\) 分为 \(0,1,2\) 三种状态，分别是：
- \(state_{j,x}=0:\sum\limits_{i=l}^r1[col_x\in S_i]=0\)
- \(state_{j,x}=1:0 < \sum\limits_{i=l}^r1[col_x\in S_i] < r-l+1\)
- \(state_{j,x}=2:\sum\limits_{i=l}^r1[col_x\in S_i]=r-l+1\)
即完全没有覆盖，部分覆盖和全覆盖。
于是对于一个点，我们额外维护一个集合 \(A_x\)，满足 \(\forall i\in[1,N],i\in A_x\Leftrightarrow state_{x,i}=0 \land state_{\lfloor\frac{x}{2}\rfloor,i}=1\)。
令从节点 \(i\) 到 \(root\) 的路径为 \(p_{i\to root}\)
注意到，一个叶子结点 \(i\) 的 \(\text{mex}\) 就是 \(\max\limits_{j\in p_{i\to root}}\{\min\limits_{k\in A_j}k\}\)。也就是路径上每个点的 \(A\) 的最小值的最大值。不懂的读者可以自己画一画。
这样就可以把之前的柿子 \(Ans_x=\max\{Ans_{ls_x},Ans_{rs_x}\}\) 转化成 \(Ans_x=\min\{\min\limits_{i\in A_x}i,\max\{Ans_{ls_x},Ans_{rs_x}\}\}\)
这样可以每个节点 \(x\) 开一个set存一下 \(A_x\)，这样每个节点 pushup() 的时间复杂度就是 \(\log n\) 的，query() 的时间复杂度是 \(\log n\) 的，update() 的时间复杂度是 \(\log^2 n\) 的。
但是，这都是基于对每个颜色操作不交的前提，所以需要使用 set 来在线维护没有被修改的区间，然后对每个区间进行修改。
所以总时间复杂度为 \(O(n\log^2 n)\)。
事实上，程序只跑了1s。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int V = 2e5, N = V + 5;
namespace sgt
{
set<int> s[N << 2];
int a[N << 2], typ[N << 2];
void init()
{
memset(a, 0x3f, sizeof a);
for(int i = 0; i <= V; i ++) s[1].insert(i);
a[1] = 0;
}
void pushup(int x, int typ)
{
if(typ) return a[x] = (s[x].empty() ? 0x3f3f3f3f : *s[x].begin()), void();
a[x] = max(a[x << 1], a[x << 1 | 1]);
if(!s[x].empty()) a[x] = min(a[x], *s[x].begin());
}
void update(int ql, int qr, int l, int r, int x, int g, int v)
{
if(ql <= l && r <= qr)
{
if(s[x].count(v))
s[x].erase(v), pushup(x, l == r);
return;
}
int mid = (l + r) >> 1, st = 0;
if(s[x].count(v)) g = 1, s[x].erase(v);
if(mid >= ql) update(ql, qr, l, mid, x << 1, g, v), st |= 1;
if(mid < qr) update(ql, qr, mid + 1, r, x << 1 | 1, g, v), st |= 2;
if(g)
{
if(!(st & 1)) s[x << 1].insert(v), pushup(x << 1, l == mid);
if(!(st & 2)) s[x << 1 | 1].insert(v), pushup(x << 1 | 1, mid + 1 == r);
}
pushup(x, l == r);
}
int query(int ql, int qr, int l, int r, int x)
{
if(ql <= l && r <= qr)
return a[x];
int mid = (l + r) >> 1, ans = 0;
if(mid >= ql) ans = max(ans, query(ql, qr, l, mid, x << 1));
if(mid < qr) ans = max(ans, query(ql, qr, mid + 1, r, x << 1 | 1));
ans = min(ans, a[x]);
return ans;
}
}
using pii = pair<int, int>;
set<pii> s[N];
set<pii>::iterator split(set<pii> &s, int x)
{
auto it = s.upper_bound({x, V + 1});
if(it == s.begin()) return it;
if((--it)->second < x) return ++it;
pii y = *it;s.erase(it);
if(x > y.first) s.insert({y.first, x - 1});
return s.insert({max(y.first, x), y.second}).first;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
int q;cin >> q;
sgt::init();
for(int i = 0; i <= V; i ++) s[i].insert({1, V});
int ans = 0;
while(q --)
{
int op;cin >> op;
if(op == 1)
{
int x, a, b;cin >> x >> a >> b;
x ^= ans, a ^= ans, b ^= ans;
auto itb = split(s[x], b + 1);
auto ita = split(s[x], a);
for(auto it1 = ita; it1 != itb; it1 ++)
sgt::update(it1->first, it1->second, 1, V, 1, 0, x);
s[x].erase(ita, itb);
}
else
{
int l, r;cin >> l >> r;
l ^= ans, r ^= ans;
int aans = sgt::query(l, r, 1, V, 1);
cout << aans << "\n";
ans += aans;
}
}
return 0;
}