前言

断续地调了一天一夜，终于做出来了！

题目链接-Rectangle Painting

大概就是：给 \(n\) 个集合 \(S_i\)，两种操作，

1. 1 {[l,r],x }l r 向 \(S_l\) 到 \(S_r\) 插入 \(x\)
2. 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;
}