Portal
Description
给出一个\(1..n(n\leq5\times10^4)\)的排列\(\{a_n\}\)和数列\(\{w_n\}(w_i\leq10^5)\)，进行\(m(m\leq5\times10^4)\)次操作：
交换\(a_{p_1},a_{p_2}\)，并求\(\sum_{i=1}^n \sum_{j=i+1}^n [a_i>a_j](w_{a_i}+w_{a_j})\)。
Solution
树套树/CDQ分治，想锻炼一下代码能力所以写了树套树。
首先这是一个求逆序对的问题，那么我们考虑交换\(a_{p_1},a_{p_2}\)对答案有什么影响。易知只有\(i\in[p_1+1,p_2-1]\)对答案造成影响：
若\(a_i<a_{p_1}\)，那么答案减\(a_i+a_{p_1}\)；若\(a_i>a_{p_1}\)，那么答案加\(a_i+a_{p_1}\)。
若\(a_i<a_{p_2}\)，那么答案加\(a_i+a_{p_2}\)；若\(a_i>a_{p_2}\)，那么答案减\(a_i+a_{p_2}\)。
那么求出\(\{c_1,s_1,c_2,s_2\}\)分别表示区间\([p_1+1,p_2-1]\)内小于/大于\(x\)的\(i\)的个数/\(w_i\)的和，然后就可以根据上两行计算答案的变化。而这可以用树套树来做。
时间复杂度\(O(mlog^2n)\)。
Code
//[TJOI2017]不勤劳的图书管理员
#include <algorithm>
#include <cstdio>
using std::swap;
typedef long long lint;
inline char gc()
{static char now[1<<16],*s,*t;if(s==t) {t=(s=now)+fread(now,1,1<<16,stdin); if(s==t) return EOF;}return *s++;
}
inline int read()
{int x=0; char ch=gc();while(ch<'0'||'9'<ch) ch=gc();while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();return x;
}
const int N=5e4+10;
const int P=1e9+7;
int n,m,a[N],w[N];
namespace init
{int tr1[N],tr2[N];void add(int x,int v) {while(x<=n) tr1[x]++,tr2[x]=(tr2[x]+v)%P,x+=x&(-x);}int sum1(int x) {int r=0; while(x) r+=tr1[x],x-=x&(-x); return r;}int sum2(int x) {int r=0; while(x) r=(r+tr2[x])%P,x-=x&(-x); return r;}int calc(){int res=0;for(int i=1;i<=n;i++){res=(res+(lint)sum1(n-a[i]+1)*w[a[i]])%P;res=(res+sum2(n-a[i]+1))%P;add(n-a[i]+1,w[a[i]]);}return res;}
}
const int N1=2e6;
struct info
{int c1,s1,c2,s2;info(int _c1=0,int _s1=0,int _c2=0,int _s2=0) {c1=_c1,s1=_s1,c2=_c2,s2=_s2;};friend info operator +(info x,info y){int c1=x.c1+y.c1,s1=x.s1+y.s1,c2=x.c2+y.c2,s2=x.s2+y.s2;return info(c1,s1%P,c2,s2%P);}
};
namespace inTr
{int cnt,fa[N1],ch[N1][2],siz[N1]; int val[N1],sum[N1];inline void update(int p){siz[p]=siz[ch[p][0]]+1+siz[ch[p][1]];sum[p]=((sum[ch[p][0]]+sum[ch[p][1]])%P+w[val[p]])%P;}inline int wh(int p) {return p==ch[fa[p]][1];}inline void rotate(int p){int q=fa[p],r=fa[q],w=wh(p);fa[p]=r; if(r) ch[r][wh(q)]=p;fa[ch[q][w]=ch[p][w^1]]=q;fa[ch[p][w^1]=q]=p;update(q),update(p);}void splay(int &rt,int p){for(int q=fa[p];q;rotate(p),q=fa[p]) if(fa[q]) rotate(wh(p)^wh(q)?p:q);update(rt=p);}int pre(int rt,int x){int r=0;for(int p=rt;p;p=ch[p][val[p]<x]) if(val[p]<x) r=p;return r;}void ins(int &rt,int p){if(!rt) {rt=p; return;}int q=rt;while(ch[q][val[q]<val[p]]) q=ch[q][val[q]<val[p]];fa[ch[q][val[q]<val[p]]=p]=q;update(q); splay(rt,p);}int del(int &rt,int x){if(x==0||!rt) return 0;int p=pre(rt,x+1); if(val[p]!=x) return 0;splay(rt,p);int chCnt=(ch[p][0]>0)+(ch[p][1]>0);if(chCnt==0) {rt=0; return p;}if(chCnt==1) {rt=ch[p][ch[p][1]>0],fa[rt]=0; return p;}int q=ch[p][0]; while(ch[q][1]) q=ch[q][1];splay(rt,q);fa[ch[q][1]=ch[p][1]]=q;fa[p]=ch[p][0]=ch[p][1]=0;update(q);return p;}inline void change(int &rt,int x1,int x2){int p=del(rt,x1); if(!p) p=++cnt;fa[p]=ch[p][0]=ch[p][1]=0,siz[p]=1;val[p]=x2,sum[p]=w[x2];ins(rt,p);}info query(int rt,int x){int c1=0,s1=0;for(int p=rt;p;p=ch[p][val[p]<x])if(val[p]<x) c1+=siz[p]-siz[ch[p][1]],s1=(s1+sum[p]-sum[ch[p][1]]+P)%P;return info(c1,s1,siz[rt]-c1,sum[rt]-s1);}
}
namespace outTr
{#define Ls (p<<1)#define Rs (p<<1|1)int rt[N<<2];int in(int L,int R,int p1,int p2) {return ((L<=p2&&p2<=R)<<1)|(L<=p1&&p1<=R);}void change(int p,int L0,int R0,int p1,int p2){int inP=in(L0,R0,p1,p2);if(inP==1) inTr::change(rt[p],a[p1],a[p2]);else if(inP==2) inTr::change(rt[p],a[p2],a[p1]);if(L0==R0) return;int mid=L0+R0>>1;if(in(L0,mid,p1,p2)) change(Ls,L0,mid,p1,p2);if(in(mid+1,R0,p1,p2)) change(Rs,mid+1,R0,p1,p2);}int optL,optR;info query(int p,int L0,int R0,int x){if(optL<=L0&&R0<=optR) return inTr::query(rt[p],x);int mid=L0+R0>>1; info res=info(0,0,0,0);if(optL<=mid) res=res+query(Ls,L0,mid,x);if(mid<optR) res=res+query(Rs,mid+1,R0,x);return res;}
}
inline void change(int p1,int p2) {outTr::change(1,1,n,p1,p2);}
inline info query(int L,int R,int x)
{outTr::optL=L,outTr::optR=R;return outTr::query(1,1,n,x);
}
int main()
{n=read(),m=read();for(int i=1;i<=n;i++){a[0]=read(),w[a[0]]=read();change(0,i); swap(a[0],a[i]);}int ans=init::calc();for(int i=1;i<=m;i++){int p1=read(),p2=read();if(p1>p2) swap(p1,p2); else if(p1==p2) {printf("%d\n",ans); continue;}int x=a[p1],y=a[p2];info r1=query(p1+1,p2-1,x),r2=query(p1+1,p2-1,y);ans-=((lint)r1.c1*w[x]%P+r1.s1)%P; ans=(ans+P)%P;ans+=((lint)r1.c2*w[x]%P+r1.s2)%P; ans=ans%P;ans+=((lint)r2.c1*w[y]%P+r2.s1)%P; ans=ans%P;ans-=((lint)r2.c2*w[y]%P+r2.s2)%P; ans=(ans+P)%P;if(x<y) ans=(ans+w[x]+w[y])%P; else ans=(ans-w[x]-w[y]+P)%P;printf("%d\n",ans);change(p1,p2); swap(a[p1],a[p2]);}return 0;
}
