luogu3759 不勤劳的图书管理员 (树状数组套线段树)

交换的话，只有它们中间的书会对答案产生影响

树状数组记位置，套线段树记书的编号 它对应的页数和书的个数

然后就是减掉中间那些原来是逆序对的，再把交换以后是逆序对的加上

别忘了考虑这两个自己交换以后是不是逆序的

最重要的一步：开个O2

 #include<bits/stdc++.h>

 #define CLR(a,x) memset(a,x,sizeof(a))

 using namespace std;

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<ll,ll> pa;

 const int maxn=5e4+,lg2n=2e7+,P=1e9+;

 inline ll rd(){

     ll x=;char c=getchar();int neg=;

     while(c<''||c>''){if(c=='-') neg=-;c=getchar();}

     while(c>=''&&c<='') x=x*+c-'',c=getchar();

     return x*neg;

 }

 namespace SegT{

     int ch[lg2n][],pct;

     ll sum[lg2n],cnt[lg2n];

     inline void update(int x){sum[x]=sum[ch[x][]]+sum[ch[x][]],cnt[x]=cnt[ch[x][]]+cnt[ch[x][]];}

     inline void add(int &p,int l,int r,int x,int v){

         if(!p) p=++pct;

         if(l==r) sum[p]+=v,cnt[p]+=(v>?:-);

         else{

             int m=l+r>>;

             if(x<=m) add(ch[p][],l,m,x,v);

             else add(ch[p][],m+,r,x,v);

             update(p);

         }

     }

     inline pa query(int p,int l,int r,int x,int y){

         if(!p) return make_pair(,);

         if(x<=l&&r<=y) return make_pair(sum[p],cnt[p]);

         else{

             int m=l+r>>;pa r1=make_pair(,),r2=make_pair(,);

             if(x<=m) r1=query(ch[p][],l,m,x,y);

             if(y>=m+) r2=query(ch[p][],m+,r,x,y);

             return make_pair(r1.first+r2.first,r1.second+r2.second);

         }

     }

 }

 int N,M,rt[maxn];

 int pg[maxn],a[maxn];

 inline int lowbit(int x){return x&(-x);}

 inline void add(int x,int y,int v){

     for(;x<=N;x+=lowbit(x)) SegT::add(rt[x],,N,y,v);

 }

 inline pa query(int xl,int xr,int yl,int yr){

     pa re=make_pair(,);

     for(;xr;xr-=lowbit(xr)){

         pa x=SegT::query(rt[xr],,N,yl,yr);

         re.first+=x.first,re.second+=x.second;

     }

     for(xl--;xl;xl-=lowbit(xl)){

         pa x=SegT::query(rt[xl],,N,yl,yr);

         re.first-=x.first,re.second-=x.second;

     }

     return re;

 }

 int main(){

     //freopen("","r",stdin);

     int i,j,k;

     N=rd(),M=rd();

     for(i=;i<=N;i++) a[i]=rd(),pg[i]=rd();

     ll ans=;

     for(i=;i<=N;i++){

         pa re=query(,i-,a[i]+,N);

         ans+=re.first+re.second*pg[i],ans%=P;

         add(i,a[i],pg[i]);

     }

     // printf("%d\n",ans);

     for(i=;i<=M;i++){

         int x=rd(),y=rd();

         if(x>y) swap(x,y);

         pa re=query(x+,y-,,a[x]-);

         ans-=re.first+re.second*pg[x],ans%=P;

         re=query(x+,y-,a[y]+,N);

         ans-=re.first+re.second*pg[y],ans%=P;

         if(a[x]>a[y]) ans-=pg[x]+pg[y],ans%=P;

         re=query(x+,y-,,a[y]-);

         ans+=re.first+re.second*pg[y],ans%=P;

         re=query(x+,y-,a[x]+,N);

         ans+=re.first+re.second*pg[x],ans%=P;

         if(a[x]<a[y]) ans+=pg[x]+pg[y];

         add(x,a[x],-pg[x]);add(x,a[y],pg[y]);

         add(y,a[y],-pg[y]);add(y,a[x],pg[x]);

         swap(a[x],a[y]);swap(pg[x],pg[y]);

         printf("%lld\n",(ans+P)%P);

     }

     return ;

 }