题解：P12539 [XJTUPC 2025] 结束乐队
complexly
·
·
题解
根号连接大脑，分块代替思考。
这道题可以直接用分块创过去。
首先你注意到 k \le 10^5 。
好的，我们可以开始根号了。
我们直接考虑下面这个更强的问题（保证是一个排列）：
- 区间 \operatorname{mex}。
- 交换俩个数（单点修改）。
这有一个很简单的分块做法。
序列分块，值域分块。
维护：
$col_{i,j}$ 表示第序列 $1 \sim i$ 块内在数值为 $j$ 的数的数量。
查询：
先跳值域整块，再跳值域散块。
序列散块暴力，就不多说了。
修改：
由于你维护的是块的前缀和，无论是 $block\_col_{i,j}$ 还是 $col_{i,j}$ 都只有 $\sqrt n$ 个要修改的地方，暴力修改即可。
但是，$n = 5\times 10^5$ ， $col_{i,j}$ 的空间是 $n \sqrt n$ 的，初始化也是 $n\sqrt n$ 的，过不去（其实可以用 bitset）
所以你考虑跳值域散块的时候不用 $col_{i,j}$ 了，你发现只要 $l \le pos_x \le r$，$x$ 就在 $[l , r]$ 中（ $pos_i$ 表示 $i$ 这个值的出现位置）。
所以你维护一下 $pos_i$ 就行了。
所以根本用不到交换的俩个值的性质，就做完了。
总复杂度 $O(n + k\sqrt n)$ 最慢点 313 ms ，没卡常。
```cpp
#include<bits/stdc++.h>
#define f(i , l , r) for(int i = (l);i <= (r);++ i)
#define d(i , l , r) for(int i = (r);i >= (l);-- i)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define sc second
#define lowbit(x) ((x)&-(x))
#define fre(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
const int N = 5e5 + 10 , B = 1024;//1024位运算，方便卡常
int n , k , a[N] , col[N/B+10][N/B+10] , bl[N] , L[N] , R[N] , pos[N] , t[N];
void change(int u,int v){
f(i , bl[u] , bl[n])col[i][bl[a[u]]] -- , col[i][bl[a[v]]] ++;
f(i , bl[v] , bl[n])col[i][bl[a[v]]] -- , col[i][bl[a[u]]] ++;
swap(a[u] , a[v]) , swap(pos[a[v]] , pos[a[u]]);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0) , cout.tie(0);
cin >> n;
f(i , 1 , n)cin >> a[i] , pos[a[i]] = i;
f(i , 1 , n)bl[i] = (i - 1) / B + 1 , R[bl[i]] = i , L[bl[i]] = R[bl[i]-1] + 1;
f(i , 1 , bl[n]){
f(j , 1 , bl[n])col[i][j] = col[i-1][j];
f(j , L[i] , R[i])col[i][bl[a[j]]] ++;
}
cin >> k;
// cerr << "ok\n";
f(i , 1 , k){
int l , r , p = 1;
cin >> l >> r;
if(bl[l] == bl[r]){
f(j , 1 , bl[n])t[j] = 0;
f(j , l , r)t[bl[a[j]]] ++;
// int p = 1;
while(p < bl[n] && t[p] == R[p] - L[p] + 1)p ++;
p = L[p];
while(l <= pos[p] && pos[p] <= r)p ++;
}
else {
int rb = bl[r] , lb = bl[l];
f(j , 1 , bl[n])t[j] = col[rb-1][j] - col[lb][j];
f(j , l , R[lb])t[bl[a[j]]] ++;
f(j , L[rb] , r)t[bl[a[j]]] ++;
// int p = 1;
while(p < bl[n] && t[p] == R[p] - L[p] + 1)p ++;
// cerr << p << "\n";
p = L[p];
while(l <= pos[p] && pos[p] <= r)p ++;
}
if(p >= n)cout << "peace\n";
else cout << p << "\n" , change(pos[p] , pos[p + 1]);
// f(j , 1 , n)cout << a[j] << " ";cout << "\n";
}
}
```