比赛链接：https://codeforces.com/gym/104077
A题 Bridge
题意
完整题意见上方链接。
转换之后的题意可以理解为：有$n$条链，每条链上有$m+1$个点，标号从$1$到$m+1$，每个点可以用$(a,b)$表示，意为第$a$条链上第$b$个点。存在两种操作：
- 交换点$(a, b)$与点$(a + 1, b)$的指向。
- 查询第$a$条链最终指向的终点$(i,m+1)$，输出$i$。
tags：分块/无旋treap
题解
分块做法
每个点维护它的下一个点与上一个点，但这样对于一次查询是$O(m)$复杂度的，显然很慢。对于链上查找终点的题，显然存在三种做法：
- 维护每个点的终点，直接$O(1)$访问终点
- 考虑倍增，维护每个点跳$2^i$步之后到达的点，$O(\log m)$访问终点
- 维护每个点跳$\sqrt m$步到达的点，$O(\sqrt m)$访问终点
再考虑操作1的交换操作，相当于将两条链断开，再交换断开的后半部分重新拼接成两条链。则两条链断开时链的前半部分的终点都会发生改变，不太方便维护（当然，下面用无旋treap维护这种做法）。
再考虑倍增，同样的，断链的前半部分的倍增点因为拼接上新的链都会发生改变，所以不好维护。
最后考虑根号步数的跳跃，可以发现断链前半部分只有后$\sqrt m$的点需要修改跳跃点，其它点的跳跃都没有影响，于是可以在$\sqrt m$的时间复杂度内完成修改操作。
时间复杂度：$O(m\sqrt m)$
/*************************************************************************
> File Name: 1.cpp
> Author: Knowledge_llz
> Mail: 925538513@qq.com
> Blog: https://www.cnblogs.com/Knowledge-Pig/
************************************************************************/
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 5e5 + 10;
int n, m, B, Q, cnt, a[maxx], to[maxx], pre[maxx], jump[maxx];
struct query{
int t, a, b;
}q[maxx];
vector<int> vec[maxx];
map<pair<int, int>, int> id;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt","w", stdout);
#endif
auto st = clock();
cin >> n >> m >> Q;
for(int i = 1; i <= n; ++i) vec[i].push_back(0);
for(int i = 1; i <= Q; ++i){
cin >> q[i].t >> q[i].a;
if(q[i].t & 1){
cin >> q[i].b;
vec[q[i].a].push_back(q[i].b);
vec[q[i].a].push_back(q[i].b + 1);
vec[q[i].a + 1].push_back(q[i].b);
vec[q[i].a + 1].push_back(q[i].b + 1);
}
}
for(int i = 1; i <= n; ++i){
sort(vec[i].begin(), vec[i].end());
auto it = unique(vec[i].begin(), vec[i].end());
vec[i].erase(it, vec[i].end());
B = max(B, (int)vec[i].size());
}
B = sqrt(B / 2) + 1;
for(int i = 1; i <= n; ++i){
int x = 0;
for(auto j : vec[i]){
id[make_pair(i, j)] = ++cnt;
a[cnt] = i;
if(x) to[x] = cnt;
pre[cnt] = x;
x = cnt;
}
x = id[make_pair(i, 0)];
for(int j = 1; j <= B; ++j) x = to[x];
for(auto j : vec[i]){
jump[id[make_pair(i, j)]] = x;
x = to[x];
if(!x) break;
}
}
// cout << "Times : " << (double)(clock() - st) / CLOCKS_PER_SEC * 1000 << endl;
for(int i = 1; i <= Q; ++i){
if(q[i].t & 1){
int idx = id[make_pair(q[i].a, q[i].b)], idy = id[make_pair(q[i].a + 1, q[i].b)];
pre[to[idx]] = idy;
pre[to[idy]] = idx;
swap(to[idx], to[idy]);
int jx = jump[idx], jy = jump[idy];
for(int k = 0, x = idx; k <= B && x; ++k, jy = pre[jy], x = pre[x]) jump[x] = jy;
for(int k = 0, y = idy; k <= B && y; ++k, jx = pre[jx], y = pre[y]) jump[y] = jx;
}
else{
int x = id[make_pair(q[i].a, 0)];
while(jump[x]) x = jump[x];
while(to[x]) x = to[x];
cout << a[x] << endl;
}
}
// cout << "Times : " << (double)(clock() - st) / CLOCKS_PER_SEC * 1000 << endl;
return 0;
}开始将分块设置在300左右，一直TLE。最后将B按照最长的链长除以2再开根号，终于在842ms通过本题。
无旋treap解法
链的切开，再交换重组，非常符合无旋treap中的split与merge操作。
因为有$n$条链，就建$n$个无旋treap，以$b$作为treap上的$key$值。每次按照题意模拟即可。
还剩下一个问题：现在有$n$棵平衡树，每次修改操作时我只知道两个点的编号，我怎么知道它们在哪棵平衡树上？
于是，我们还要用treap上维护每个点$father$，对于一次修改来说，直接暴力找$father$，找到根节点即可。再维护每个根节点的节点标号与第几棵平衡树的对应关系。
时间复杂度：$O(n\log n)$。最终只用233ms就可以通过，但是代码比上述分块长了很多。
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 4e5 + 10;
int n, m, Q, num, rt[maxx], rt_id[maxx], to[maxx];
struct query{
int t, a, b;
}q[maxx];
struct node{
int key, l, r, fa, rd;
}tr[maxx << 2];
set<int> s[maxx];
vector<int> vec[maxx], id[maxx];
int get_id(int x, int y){
int pos = lower_bound(vec[x].begin(), vec[x].end(), y) - vec[x].begin();
return id[x][pos];
}
int get_rt(int x){
while(tr[x].fa) x = tr[x].fa;
return x;
}
int add(int val){
tr[++num].key = val;
tr[num].rd = rand();
return num;
}
void push_up(int p){
tr[p].fa = 0;
tr[tr[p].l].fa = tr[tr[p].r].fa = p;
}
void split(int p, int &x, int &y, int val){
if(!p){
x = y = 0;
return ;
}
if(tr[p].key <= val){
x = p;
split(tr[p].r, tr[p].r, y, val);
}
else{
y = p;
split(tr[p].l, x, tr[p].l, val);
}
push_up(p);
}
void merge(int &p, int x, int y){
if(!x || !y){
p = x + y;
return;
}
if(tr[x].rd < tr[y].rd){
p = x;
merge(tr[p].r, tr[p].r, y);
}
else{
p = y;
merge(tr[p].l, x, tr[p].l);
}
push_up(p);
}
void ins(int &p, int val){
int l = 0, r = 0, new_node = add(val);
split(p, l, r, val);
merge(l, l, new_node);
merge(p, l, r);
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt","w", stdout);
#endif
cin >> n >> m >> Q;
srand(n);
for(int i = 1; i <= Q; ++i){
cin >> q[i].t >> q[i].a;
if(q[i].t & 1){
cin >> q[i].b;
s[q[i].a].insert(q[i].b);
s[q[i].a + 1].insert(q[i].b);
s[q[i].a].insert(q[i].b + 1);
s[q[i].a + 1].insert(q[i].b + 1);
}
}
for(int i = 1; i <= n; ++i){
for(auto u : s[i]){
ins(rt[i], u);
vec[i].push_back(u);
id[i].push_back(num);
// cout << i << " " << u << " " << num << endl;
}
rt_id[rt[i]] = to[i] = i;
}
// for(int i = 1; i <= num; ++i) cout << i << " " << tr[i].fa << endl;
for(int i = 1; i <= Q; ++i){
if(q[i].t & 1){
int node1_id = get_id(q[i].a, q[i].b), node2_id = get_id(q[i].a + 1, q[i].b);
int id1 = rt_id[get_rt(node1_id)], id2 = rt_id[get_rt(node2_id)];
// cout << node1_id << " --- " << id1 << endl;
// cout << node2_id << " === " << id2 << endl;
int l1 = 0, r1 = 0, l2 = 0, r2 = 0;
swap(to[id1], to[id2]);
split(rt[id1], l1, r1, q[i].b);
split(rt[id2], l2, r2, q[i].b);
// cout << l2 << " " << r2 << endl;
merge(rt[id1], l1, r2);
merge(rt[id2], l2, r1);
rt_id[rt[id1]] = id1;
rt_id[rt[id2]] = id2;
// for(int i = 1; i <= num; ++i) cout << i << " " << tr[i].fa << " " << tr[i].key << endl;
}
else cout << to[q[i].a] << endl;
}
return 0;
}
