动态逆序

思路与复杂度

先用树状数组计算初始逆序对。树状数组每个桶再维护可求秩的有序集合，支持位置区间内小于某值的数量查询。交换前后只计算两个位置参与的逆序对贡献，二者之间的逆序对被重复计算，需减去一次。删除旧值、交换并插入新值，再累计贡献差。时间 O((n+m) log² n)，空间 O(n log n)。提供的参考实现依赖 GNU PBDS，保留其必要头文件。

正确性与边界

未涉及交换位置的数对相对关系不变，贡献差只需处理两位置与其余元素的关系。

参考代码

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;using namespace __gnu_pbds;using ll=long long;using O=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;int n,m;vector<int>a;vector<O>b;
void add(int p,int v,int in){for(;p<=n;p+=p&-p)if(in)b[p].insert(v);else b[p].erase(v);}int pre(int p,int v){int z=0;for(;p;p-=p&-p)z+=b[p].order_of_key(v);return z;}int lr(int l,int r,int v){return l>r?0:pre(r,v)-pre(l-1,v);}ll con(int p,int v){return (p-1-lr(1,p-1,v+1))+lr(p+1,n,v);}
int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;a.resize(n+1);b.resize(n+1);vector<int>f(n+1);ll inv=0;for(int i=1;i<=n;i++){cin>>a[i];int le=0;for(int x=a[i];x;x-=x&-x)le+=f[x];inv+=i-1-le;for(int x=a[i];x<=n;x+=x&-x)f[x]++;add(i,a[i],1);}cout<<inv<<"\n";while(m--){int x,y;cin>>x>>y;if(x==y){cout<<inv<<"\n";continue;}if(x>y)swap(x,y);ll o=con(x,a[x])+con(y,a[y])-(a[x]>a[y]);add(x,a[x],0);add(y,a[y],0);swap(a[x],a[y]);add(x,a[x],1);add(y,a[y],1);ll z=con(x,a[x])+con(y,a[y])-(a[x]>a[y]);inv+=z-o;cout<<inv<<"\n";}}