![题解：P14768 [ICPC 2024 Seoul R] Ladder Update](http://pic.xiahunao.cn/yaotu/题解：P14768 [ICPC 2024 Seoul R] Ladder Update)
更差的阅读体验
写了一大坨，调了一天，也总算是过了。
爬梯子问题应该是一个非常经典的模型。
首先我们知道最后到达梯子底端的时候每个竖杆上人的编号序列 \(p\) 是 \(1 \sim n\) 的一个排列。如果没有横杆，那么最后的序列一定是 \([1, 2, \cdots, n]\)。
定义高度为 \(1\) 的一端称为上端。我们先考虑从上往下依次添加横杆，假设添加在 \(i, i+1\) 之间，则由于底下没有其他横杆阻挡，所以就相当于 \(i\) 上的人会爬到 \(i+1\)，\(i+1\) 上的人会爬到 \(i\)，所以操作等价于交换 \(p_i, p_{i+1}\)。
题目还有删除操作。但是仔细想想会发现删除操作其实相当于在原来的地方再添加一个横杆。所以我们只需要支持加入的操作。
现在考虑假设我们得到最后的排列了，我们现在想要求等价的最少横杆个数，那也就是把一个排列，通过交换相邻两项还原成 \([1, 2, \cdots, n]\) 的操作次数。不难发现这个就是冒泡排序的交换次数，也就是逆序对数量。
所以现在的一个问题就是找到我每次交换的是哪两个数。假设横杆的端点被称为关键点，我们可以维护出来每个人的移动路径上的关键点，也就是一条链状物。由于每个关键点最多两个人走，所以 \(n\) 条路径的点数之和是 \(O(n)\) 的。
那么我们只要知道当前关键点属于哪个路径，也就是找到链的上端，就能判断当前这个点上的人是谁。至于交换两个人的后续路径，实际上就是将这两个人的路径从横杆的位置断开，然后将两个人的路径的下半部分交换。
维护拼接、断开操作，不难使用平衡树维护！我写的是 Treap。注意由于我们需要支持找根的操作，所以我们的根不能换，为了达到这个目的我们可以先把根的优先级设为一个很小的数，这样合并的时候永远会把这个优先级很小的根放在最上面。
然后问题就变成的一个很简单的形式：支持交换两个数，查询全局逆序对数量。交换两个数也就是单点修改。
一开始写了树套树，在洛谷被卡常了。但是发现这个东西是一个偏序的形式。具体地，我们可以把一次单点修改变成两个事件，分别是删除原来的值，加入新的值。一个事件可以描述为 \((t_i, k_i, x_i, v_i)\)，\(t_i\) 是这个事件的时间戳，\(k_i\) 是操作的位置，\(v_i\) 是操作的种类（删除为 \(-1\)，加入为 \(1\)）。那么一个事件 \(i\) 对全局逆序对的贡献，可以看做：
注意前面要乘 \(v_i\)，因为删除一个数字会产生负的贡献。
所以对着这个东西 cdq 分治即可。
然后这道题就做完了。假设 \(n, m, q\) 同阶，复杂度 \(O(n \log^2 n)\)。
#include<bits/stdc++.h>
#define endl '\n'
#define N 500006
using namespace std;
using i64=long long;
int n,m,q,flag[N],ans,tot,p[N],inv[N];
set<pair<i64,int> > s[N];
unordered_map<int,int> mp;
inline int read()
{int ret=0,f=1;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();return ret*f;
}
inline void write(int k)
{if(k<0)putchar('-'),k=-k;static int nnum[10],ttp=0;while(k)nnum[++ttp]=k%10,k/=10;if(!ttp)nnum[++ttp]=0;while(ttp)putchar(nnum[ttp--]^48);
}
struct BIT {int tree[N];void update(int k,int x){for(;k<=n;k+=k&-k)tree[k]+=x;}int query(int k){int ret=0; for(;k;k-=k&-k)ret+=tree[k]; return ret;}
} T1;
struct Treap {int ls[N],rs[N],fa[N],pri[N]; i64 val[N];inline void push_up(int p){if(ls[p])fa[ls[p]]=p; if(rs[p])fa[rs[p]]=p;}int find(int p){return !fa[p]?p:find(fa[p]);}void split(int p,i64 k,int &u,int &v){if(!p)return u=v=0,(void)0;if(val[p]<=k)u=p,split(rs[p],k,rs[p],v);else v=p,split(ls[p],k,u,ls[p]);push_up(p);}int merge(int p,int q){if(!p||!q)return p|q;if(pri[p]<pri[q])return rs[p]=merge(rs[p],q),push_up(p),p;return ls[q]=merge(p,ls[q]),push_up(q),q;}
} T2;
int c;
struct Node {int t,k,x,v,ans;} a[N];
int newNode(i64 h){return T2.pri[++tot]=rand(),T2.val[tot]=h,tot;}
pair<int,int> solve(i64 h,int i)
{auto it1=s[i].upper_bound({h,0}),it2=s[i+1].upper_bound({h,0});int pl=(--it1)->second,pr=(--it2)->second;int rtl=T2.find(pl),rtr=T2.find(pr),x=inv[rtl],y=inv[rtr];swap(inv[p[x]],inv[p[y]]),swap(p[x],p[y]);int lu,ld,ru,rd; T2.split(rtl,h,lu,ld),T2.split(rtr,h,ru,rd);T2.fa[lu]=T2.fa[ld]=T2.fa[ru]=T2.fa[rd]=0;rtl=T2.merge(T2.merge(lu,newNode(h)),rd),s[i+1].insert({h,tot});rtr=T2.merge(T2.merge(ru,newNode(h)),ld),s[i].insert({h,tot});return {x,y};
}
void cdq(int l,int r)
{if(l==r)return;int mid=l+r>>1; cdq(l,mid),cdq(mid+1,r);vector<pair<int,int> > change;for(int i=mid+1,j=l;i<=r;i++){for(;j<=mid&&a[j].k<a[i].k;j++)T1.update(a[j].x,a[j].v),change.push_back({a[j].x,a[j].v});a[i].ans+=T1.query(n)-T1.query(a[i].x);}for(auto i:change)T1.update(i.first,-i.second); change.clear();for(int i=r,j=mid;i>mid;i--){for(;j>=l&&a[j].k>a[i].k;j--)T1.update(a[j].x,a[j].v),change.push_back({a[j].x,a[j].v});a[i].ans+=T1.query(a[i].x-1);}for(auto i:change)T1.update(i.first,-i.second);sort(a+l,a+r+1,[](Node x,Node y) {return x.k<y.k;});
}
main()
{n=read(),m=read(),q=read(),srand(time(0));for(int i=1;i<=n;i++)s[i].insert({0,newNode(0)}),T2.pri[tot]=-1,p[i]=inv[i]=i;for(int h,i;m--;)h=read(),i=read(),solve(1000000ll*h+(mp[h]++),i);for(int i=1;i<=n;i++)c++,a[c]={c,i,p[i],1};for(int h,i;q--;){h=read(),i=read(); auto r=solve(1000000ll*h+(mp[h]++),i);int x=r.first,y=r.second;c++,a[c]={c,x,p[y],-1};c++,a[c]={c,x,p[x],1};c++,a[c]={c,y,p[x],-1};c++,a[c]={c,y,p[y],1};flag[c]=1;}cdq(1,c);sort(a+1,a+1+c,[](Node x,Node y) {return x.t<y.t;});for(int i=1;i<=c;i++){a[i].ans=a[i].ans*a[i].v+a[i-1].ans;if(flag[i])printf("%d\n",a[i].ans);}return 0;
}