赏赐的是CCF，收回的也是CCF -《CCF圣经》
2024/10/01
国庆快乐！
P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces
题面：
题目描述
给定一个长度为 \(n=2^k\) 的数组 \(a\)，下标从 \(0\) 开始，维护 \(m\) 次操作：
- 操作一：给定 \(x\)，设数列 \(a'\) 满足 \(a'_i=a_{i\oplus x}\)，将 \(a\) 修改为 \(a'\)。其中 \(\oplus\) 表示按位异或运算。
- 操作二：给定 \(l,r\)，查询 \(a\) 的下标在 \(l,r\) 之间的子数组有多少颜色段。不保证 \(\bm {l\le r}\)，若 \(\bm{l > r}\)，请自行交换 \(\bm{l,r}\)。
其中，一个极长的所有数都相等的子数组称为一个颜色段。
部分测试点要求强制在线。
输入格式
第一行三个整数 \(T,k,m\)，其中 \(T \in \{ 0, 1 \}\) 为决定是否强制在线的参数。
第二行 \(n\) 个整数 \(a_0, \ldots, a_{n-1}\)。
接下来 \(m\) 行，每行两或三个整数，描述一次操作。第一个整数 \(\mathit{op}\) 表示操作类型。
- 若 \(op=1\)，为操作一，接下来一个整数 \(x'\)，满足 \(x=x'\oplus(T\times \mathit{lst})\)。
- 若 \(op=2\)，为操作二，接下来两个整数 \(l',r'\)，满足 \(l=l'\oplus(T\times \mathit{lst})\)，\(r=r'\oplus(T\times \mathit{lst})\)。不保证 \(\bm{l \le r}\)，若 \(\bm{l > r}\)，请自行交换 \(\bm{l, r}\)。
- 其中 \(\mathit{lst}\) 表示上次询问的答案。特别地，如果此前没有询问操作，则 \(\mathit{lst}=0\)。
输出格式
输出若干行，每行包含一个整数，依次表示每个询问的答案。
样例 #1
样例输入 #1
0 3 3 1 2 1 3 2 4 5 1 2 1 5 1 3 2 5 1样例输出 #1
5 4样例 #2
样例输入 #2
1 3 3 1 2 1 3 2 4 5 1 2 1 5 1 6 2 0 4样例输出 #2
5 4样例 #3
样例输入 #3
1 4 16 12 9 5 9 12 12 9 12 9 16 5 9 12 16 9 5 2 0 4 1 15 2 14 0 1 15 2 6 0 2 4 14 1 0 1 14 2 4 10 2 6 3 1 7 2 4 13 1 3 1 3 2 4 3 2 15 2样例输出 #3
5 7 4 7 9 5 7 2 11提示
【样例解释 #1】
此样例允许离线。
初始时 \(a=[1,2,1,3,2,4,5,1]\)。
\(a\) 的下标在 \(1,5\) 之间的子数组为 \([2,1,3,2,4]\)，它的颜色段数为 \(5\)。
进行重排操作后，\(a=[3,1,2,1,1,5,4,2]\)。
\(a\) 的下标在 \(5,1\) 之间的子数组为 \([1,2,1,1,5]\)，它的颜色段数为 \(4\)。
【样例解释 #2】
此样例除强制在线外，与样例 #1 完全一致。
【数据范围】
对于所有测试数据，\(T \in \{ 0, 1 \}\)，\(0\le k\le 18\)，\(n=2^k\)，\(1\le m\le 2\times 10^5\)，\(1\le a_i\le n\)，\(\mathit{op} \in \{ 1, 2 \}\)，\(0\le x,l,r < n\)。
本题采用捆绑测试。
- Subtask 1（15 points）：\(T=1\)，\(k\le 10\)，\(m\le 10^3\)。
- Subtask 2（15 points）：\(T=1\)，不存在操作一。
- Subtask 3（20 points）：\(T=1\)，对于所有操作二，要么 \(l=0,r=n-1\)，要么 \(l=n-1,r=0\)。
- Subtask 4（20 points）：\(T=0\)。
- Subtask 5（30 points）：\(T=1\)。
注意：Subtask 5 依赖前四个 Subtask，只有通过前四个 Subtask 才能尝试获得该 Subtask 的分数。
全局下标异或上一个 \(x\)，查询区间极长颜色段数。
下标范围为 \(\in [0,2^m - 1]\)，我们可以先用 01-trie 来理解。
当我们将每个位置的下标伴随着颜色插入到 01-trie 中，如同用线段树一样求间极长颜色段数。
我们不难发现 01-trie 和 线段树 —— 本质是一样的，原因是下标范围恰为 \(\in [0,2^m - 1]\)。
当我们在 01-trie 上判断最高位是否为 \(1 / 0\)，和线段树上二分区间 \([0\sim 2^i - 1]\ \ /\ \ [2^i \sim 2^i + (2 ^ i - 1)]\) 是一样的范围。
那我们查询区间极长颜色段数，就上线段树的基本操作：
struct node {
int lx,rx; // lx <- 最左侧颜色 || rx <- 最右侧颜色
int ans; // <- 区间极长颜色段数
};
然后，如何合并线段树上区间答案呢？
我们合并区间的时候，只有中间的颜色段会被影响，故：
node merge(node a,node b) {
node c;
c.lx = a.lx,c.rx = b.rx;
c.ans = a.ans + b.ans - (a.rx == b.lx);
return c;
}
关键问题：如何处理全局下标异或？
下标异或交换————旋转 01-trie！
我们发现如果在 01-trie 上做全局异或操作，
当异或到 \(x\) 的某一位为 \(1\) 时，我们就相当于将左右子树互换，
然后继续向下继续异或操作，并且异或具有交换律，我们只有在询问的时候考虑异或操作。
这个做法看起来很 \(cool\)，但遗憾的是，如果我们每一次修改都都做一边上述操作，时间复杂度和暴力无异！
问题出在哪？我们想打 \(tag\) —— 很遗憾，对于一个区间打完 tag 后，我们无法知道区间左右颜色！询问是有问题的。
我们从此发现问题的本质：全局 旋转tag 线段树的问题在于，异或操作是自顶向下的，而下面的操作不实行，答案就无法得出！
我们如何能让下面的答案也清晰起来呢？
神之操作：可持久化！
我们只对询问时的异或和感兴趣，而异或和在 \(\in [0,2^m - 1]\) 之中，
能不能我们直接处理出所有不同异或和版本的线段树？\(exactly!\)
我们对于每一个异或和版本的线段树上可持久化，每一个 \(x\) 版本的线段树来自于 \(x\oplus\operatorname{highbit}(x)\) 版本的线段树。
我们因为在 \(x\oplus\operatorname{highbit}(x)\) 版本上建可持久化线段树，所以我们只有异或到 \(x\) 的 \(\operatorname{highbit}\) 就可以交换左右子树并退出（因为 \(\operatorname{highbit}\) 以下的已经在 \(x\oplus\operatorname{highbit}(x)\) 版本上做过了）
（这是用 \(\mathcal{O}(n\log n)\) 建出每一个异或和版本的线段树的保证）
这样就很好的做到了自下而上的线段树更新！
这样本题就基本上解决了！
AC-code:
#include<bits/stdc++.h>
using namespace std;
int rd() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
void wt(int x) {
static int sta[35];
int f = 1;
if(x < 0) f = -1,x *= f;
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
if(f == -1) putchar('-');
while (top) putchar(sta[--top] + 48);
}
const int N = 3e5+5;
int T,k,m,n,a[N];
int rt[N];
namespace sgt{
#define mid ((pl + pr) >> 1)
struct node {
int lx,rx,ans;
node(int l,int r,int a) :lx(l),rx(r),ans(a){}
node(){}
friend node operator + (node a,node b) {
node c;
c.lx = a.lx;
c.rx = b.rx;
c.ans = a.ans + b.ans - (a.rx == b.lx);
return c;
}
}t[N * 30];
int ls[N * 30],rs[N * 30],cnt;
int newnode(node x) {
t[++cnt] = x;
ls[cnt] = rs[cnt] = 0;
return cnt;
}
int build(int pl,int pr) {
if(pl == pr) {
int cur = newnode(node(a[pl],a[pl],1));
return cur;
}
int cur = newnode(node());
ls[cur] = build(pl,mid);
rs[cur] = build(mid+1,pr);
t[cur] = t[ls[cur]] + t[rs[cur]];
return cur;
}
int update(int pre,int pl,int pr,int x) {
int cur = newnode(node());
int len = (pr - pl + 1);
if(x & (len >> 1)) {
ls[cur] = rs[pre],rs[cur] = ls[pre];
}else {
ls[cur] = update(ls[pre],pl,mid,x);
rs[cur] = update(rs[pre],mid+1,pr,x);
}
t[cur] = t[ls[cur]] + t[rs[cur]];
return cur;
}
node query(int p,int pl,int pr,int l,int r) {
if(l <= pl && pr <= r) return t[p];
if(r <= mid) return query(ls[p],pl,mid,l,r);
else if(l > mid) return query(rs[p],mid+1,pr,l,r);
else return query(ls[p],pl,mid,l,r) + query(rs[p],mid+1,pr,l,r);
}
void init() {
cnt = 0;
rt[0] = build(0,n - 1);
for(int i = 1;i<n;i++) {
int k = __lg(i);
rt[i] = update(rt[i ^ (1 << k)],0,n - 1,i);
}
}
}
int v,lst;
void Reverse() {
int x = rd();
x ^= T * lst;
v ^= x;
}
void query() {
int l = rd(),r = rd();
l ^= T * lst,r ^= T * lst;
if(l > r) swap(l,r);
lst = sgt::query(rt[v],0,n - 1,l,r).ans;
wt(lst);
putchar('\n');
}
signed main() {
T = rd(),k = rd(),m = rd(),n = (1 << k);
for(int i = 0;i<n;i++) a[i] = rd();
sgt::init();
v = 0,lst = 0;
while(m--) {
int opt = rd();
switch(opt) {
case 1:
Reverse();
break;
case 2:
query();
break;
default:
puts("Error");
exit(0);
break;
}
}
return 0;
}