思路
比较典的 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;
}