P9995 [Ynoi2000] rspcn 题解

JiaY19 · 2023-12-26 14:40:57 · 题解

思路

比较典的 ODT 题目。

发现排序是一个非常有性质的操作。

它对区间的更改与颜色段均摊差不多。

那么我们可以想到用 ODT 来维护这一整个序列。

具体的，区间排序操作可以用 ODT 维护每次排序产生的段，每段用线段树维护排序后的结果。

每次修改就可以进行线段树的分裂与合并。

如何查询。

可以发现，我们所查询的是一段前缀的颜色数量。

那么只需维护每种颜色的最左出现位置。

可以在线段树上维护每个权值的出现次数和是否是最左出现。

另外再使用一个树状树组进行辅助修改，维护段的前缀答案。

查询时需要查完整的段上最左出现的值个数的前缀和，以及在查询切开的段的线段树上查前缀即可。

时间复杂度是一个常数巨大的单 \log。

空间复杂度相同。

Code

这份没有卡常的代码只能勉强跑过，最慢点要 7.9s。

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define fro(i, x, y) for (int i = (x); i <= (y);i++)
#define pre(i, x, y) for (int i = (x); i >= (y);i--)

typedef pair<int, int> PII;

const int N = 1000010;
const int M = N * 32;

int n, m, a[N], t[N], rt[N], stk[N], ton[N], del[M];
int cnt, top, tot, lol, vis[N], siz[M], val[M], s[M][2];

struct Node
{
    int l;
    mutable int r, id;
    inline bool operator<(const Node& other) const
        { return l < other.l; }
};

set<Node> q;

inline int lowbit(int x) { return x & (-x); }
inline void delet(int x) { del[++cnt] = x; }
inline int node()
{
    int x = (cnt ? del[cnt--] : ++tot);
    val[x] = siz[x] = s[x][0] = s[x][1] = 0;
    return x;
}
inline int pode()
{
    int x = (top ? stk[top--] : ++lol);
    rt[x] = vis[x] = 0;
    return x;
}
inline void add(int x, int k)
    { while (x <= n) t[x] += k, x += lowbit(x); }
inline int ask(int x)
    { int res = 0; while(x) res += t[x], x -= lowbit(x); return res; }
inline void push_up(int p)
{
    siz[p] = siz[s[p][0]] + siz[s[p][1]];
    val[p] = val[s[p][0]] + val[s[p][1]];
}
inline void update(int &p, int k, int l = 1, int r = n)
{
    if(!p) p = node();
    if (l == r)
    {
        siz[p]++, val[p] |= (ton[l] ^ 1), ton[l] |= 1;
        return;
    }
    int mid = (l + r) / 2;
    if(k <= mid)
        update(s[p][0], k, l, mid);
    else
        update(s[p][1], k, mid + 1, r);
    push_up(p);
}
inline int merge(int p1, int p2, int l = 1, int r = n)
{
    if(!p1 || !p2) return p1 + p2;
    if(l == r)
        return siz[p1] += siz[p2], val[p1] |= val[p2], delet(p2), p1;
    int mid = (l + r) / 2;
    s[p1][0] = merge(s[p1][0], s[p2][0], l, mid);
    s[p1][1] = merge(s[p1][1], s[p2][1], mid + 1, r);
    return delet(p2), push_up(p1), p1;
}
inline void split(int &p1, int &p2, int op, int k, int l = 1, int r = n)
{
    if(!p1) p1 = node();
    if(l == r)
    {
        siz[p1] = k, siz[p2] -= k;
        val[p1] = val[p2], val[p2] = 0;
        if(siz[p2] == 0) delet(p2), p2 = 0;
        return;
    }
    int mid = (l + r) / 2;
    if(siz[s[p2][op]] <= k)
    {
        s[p1][op] = s[p2][op], k -= siz[s[p2][op]], s[p2][op] = 0;
        if(k != 0)
        {
            if(op == 0) split(s[p1][!op], s[p2][!op], op, k, mid + 1, r);
            else split(s[p1][!op], s[p2][!op], op, k, l, mid);
        }
    }
    else
    {
        if(op == 0)
            split(s[p1][op], s[p2][op], op, k, l, mid);
        else
            split(s[p1][op], s[p2][op], op, k, mid + 1, r);
    }
    push_up(p1), push_up(p2);
    if (siz[p2] == 0)
        delet(p2), p2 = 0;
}
inline auto split(int x)
{
    if(x > n) return q.end();
    auto it = --q.upper_bound({x, 0, 0});
    if ((*it).l == x) return it;
    int nw = pode(); add((*it).r, -val[rt[(*it).id]]);
    swap(nw, (*it).id), q.insert({x, (*it).r, nw}), (*it).r = x - 1;
    split(rt[(*it).id], rt[nw], vis[nw], (*it).r - (*it).l + 1);
    vis[(*it).id] = vis[nw];
    add((*it).r, val[rt[(*it).id]]), it++;
    add((*it).r, val[rt[(*it).id]]);
    return it;
}
inline void change(int l, int r, int op)
{
    auto it1 = split(l);
    auto it2 = split(r + 1);
    int id = (*it1).id;
    for (auto i = it1; i != it2; i++)
    {
        add((*i).r, -val[rt[(*i).id]]);
        if (i != it1)
            rt[id] = merge(rt[id], rt[(*i).id]), stk[++top] = (*i).id;
    }
    q.erase(it1, it2);
    auto it = q.insert({l, r, id}).x;
    add(r, val[rt[id]]), vis[id] = op;
}
inline int ask(int p, int k, int op, int l = 1, int r = n)
{
    if (!p || !k) return 0;
    if(l == r) return val[p];
    int mid = (l + r) / 2, sum = 0;
    if (k >= siz[s[p][op]])
    {
        k -= siz[s[p][op]];
        if(op == 0)
            return val[s[p][op]] + ask(s[p][!op], k, op, mid + 1, r);
        return val[s[p][op]] + ask(s[p][!op], k, op, l, mid);
    }
    if(op == 0)
        return ask(s[p][op], k, op, l, mid);
    return ask(s[p][op], k, op, mid + 1, r);
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    fro(i, 1, n) cin >> a[i];
    fro(i, 1, n)
    {
        ++lol;
        update(rt[lol], a[i]);
        q.insert({i, i, lol});
        add(i, val[rt[lol]]);
    }
    int lastans = 0;
    fro(i, 1, m)
    {
        int l, r, c;
        cin >> l >> r >> c;
        l ^= lastans, r ^= lastans, c ^= lastans;
        change(min(l, r), max(l, r), l >= r);
        int s = (*(--q.upper_bound({c, 0, 0}))).l;
        int x = (*(--q.upper_bound({c, 0, 0}))).id;
        cout << (lastans = ask(rt[x], c - s + 1, vis[x]) + ask(c - 1)) << "\n";
    }
    return 0;
}