【loj2639】[Tjoi2017]不勤劳的图书管理员

#2639. 「TJOI2017」不勤劳的图书管理员

题目描述

加里敦大学有个帝国图书馆，小豆是图书馆阅览室的一个书籍管理员。
他的任务是把书排成有序的，所以无序的书让他产生厌烦，两本乱序的书会让小豆产生这两本书页数的和的厌烦度。
现在有 nnn 本被打乱顺序的书，在接下来 mmm 天中每天都会因为读者的阅览导致书籍顺序改变位置。因为小豆被要求在接下来的 mmm 天中至少要整理一次图书。
小豆想知道，如果他前 iii 天不去整理，第 iii 天他的厌烦度是多少，这样他好选择厌烦度最小的那天去整理。

输入格式

第一行有两个数 n,mn, mn,m，表示有 nnn 本书和 mmm 天。
接下来 nnn 行，每行两个数，aia_iai​ 和 viv_ivi​，表示第 iii 本书本来应该放在 aia_iai​ 的位置，这本书有 viv_ivi​ 页，保证不会有放置同一个位置的书。
接下来 mmm 行，每行两个数，xjx_jxj​ 和 yjy_jyj​，表示在第 jjj 天的第 xjx_jxj​ 本书会和第 yjy_jyj​ 本书会因为读者阅读交换位置。
保证 1≤ai,xj,yj≤n1 \leq a_i, x_j, y_j \leq n1≤ai​,xj​,yj​≤n。

输出格式

一共 mmm 行，每行一个数，第 iii 行表示前 iii 天不去整理，第 iii 天小豆的厌烦度。因为这个数可能很大，所以将结果模 109+710 ^ 9 + 7109+7 后输出。

样例

样例输入

5 5
1 1
2 2
3 3
4 4
5 5
1 5
1 5
2 4
5 3
1 3

样例输出

42
0
18
28
48

数据范围与提示

对于 20%20\%20% 的数据，保证 1≤n,m≤50001 \leq n, m \leq 50001≤n,m≤5000。
对于 100%100\%100% 的数据，保证 1≤n,m≤50000,0≤vi≤1051 \leq n, m \leq 50000, 0 \leq v_i \leq 10^51≤n,m≤50000,0≤vi​≤105。

题意：每本书有次序和放的位置与权值，两本位置错乱的数会对答案贡献vi+vj , 每次交换两本书的位置，问每次操作之后的权值和；

题解：

将位置也看成次序的权值的话，其实就是维护动态的逆序对，只不过是两对的v都要贡献答案，维护的时候记录v的和 和 个数，交换l,r对[1,l-1]和[r+1,n]没有影响，对于l和r直接判断，l的变化值为减去[l+1,r-1]里面比v[l]小的再加上比v[l]大的，r同理，树状数组套主席树；

直接分块+树状数组的话会好写很多：https://www.cnblogs.com/CQzhangyu/p/7128300.html

 #include<cstdio>
 #include<iostream>
 #include<algorithm>
 #include<cstring>
 #include<queue>
 #include<cmath>
 #include<vector>
 #include<stack>
 #include<map>
 #define Run(i,l,r) for(int i=l;i<=r;i++)
 #define Don(i,l,r) for(int i=l;i>=r;i--)
 #define ll long long
 #define inf 0x3f3f3f3f
 using namespace std;
 const int N=,mod=1e9+;
 int n,m,p[N],w[N],ls[N*],rs[N*],rt[N],Rt[N],p1[N],p2[N],sz,cnt[N*],sum[N*];
 char gc(){
     static char*P1,*P2,s[];
     if(P1==P2)P2=(P1=s)+fread(s,,,stdin);
     return(P1==P2)?EOF:*P1++;
 }//
 int rd(){
     int x=,f=;char c=gc();
     while(c<''||c>''){if(c=='-')f=-;c=gc();}
     while(c>=''&&c<=''){x=x*+c-'',c=gc();}
     return x*f;
 }//
 void ins(int&k,int last,int l,int r,int x,int v,int f){
     sum[k=++sz]=(sum[last]+v)%mod;
     cnt[k]=cnt[last]+f;
     ls[k]=ls[last],rs[k]=rs[last];
     if(l==r)return;
     int mid=(l+r)>>;
     if(x<=mid)ins(ls[k],ls[last],l,mid,x,v,f);
     else ins(rs[k],rs[last],mid+,r,x,v,f);
 }///
 int query(int k,int l,int r,int x,int y,int z){
     if(x>y)return ;
     if(l==x&&r==y)return (sum[k]+1ll*w[z]*cnt[k]%mod)%mod;
     else{
         int mid=(l+r)>>;
         if(y<=mid)return query(ls[k],l,mid,x,y,z);
         else if(x>mid)return query(rs[k],mid+,r,x,y,z);
         else return (query(ls[k],l,mid,x,mid,z) +  query(rs[k],mid+,r,mid+,y,z))%mod;
     }
 }///
 int read(int x,int l,int r,int z){
     int ret = ;
     for(int i=x;i;i-=i&-i){
         ret = (ret + query(Rt[i],,n,l,r,z)) %mod;
     }
     return ret;
 }///
 void add(int x,int y,int v,int f){
     for(int i=x;i<=n;i+=i&-i){
         ins(Rt[i],Rt[i],,n,y,v,f);
     }
 }///
 int Query(int k,int last,int l,int r,int x,int y,int z){
     if(x>y)return ;
     if(l==x&&r==y)return (sum[k]-sum[last]+1ll*w[z]*(cnt[k]-cnt[last])%mod)%mod;
     else{
         int mid=(l+r)>>;
         if(y<=mid)return Query(ls[k],ls[last],l,mid,x,y,z);
         else if(x>mid)return Query(rs[k],rs[last],mid+,r,x,y,z);
         else return (Query(ls[k],ls[last],l,mid,x,mid,z) + Query(rs[k],rs[last],mid+,r,mid+,y,z))%mod;
     }
 }///
 int main(){
 //  freopen("loj1248.in","r",stdin);
 //  freopen("loj1248.out","w",stdout);
     n=rd(),m=rd();
     Run(i,,n)p[i]=rd(),w[i]=rd();
     ll ans = ;
     for(int i=;i<=n;i++){
         ans=(ans+query(rt[i-],,n,p[i]+,n,i))%mod;
         ins(rt[i],rt[i-],,n,p[i],w[i],);
     }
     for(int i=,x,y;i<=m;i++){
         x=rd();y=rd();
         if(x>y)swap(x,y);
         if(x==y){printf("%lld\n",ans);continue;}
         if(p[x]>p[y])ans=(ans-w[x]-w[y])%mod;else ans=(ans+w[x]+w[y])%mod;
         ans -= (ll)Query(rt[y-],rt[x],,n,,p[x]-,x) + read(y-,,p[x]-,x) - read(x,,p[x]-,x);ans%=mod;
         ans += (ll)Query(rt[y-],rt[x],,n,p[x]+,n,x) + read(y-,p[x]+,n,x) - read(x,p[x]+,n,x);ans%=mod;
         ans -= (ll)Query(rt[y-],rt[x],,n,p[y]+,n,y) + read(y-,p[y]+,n,y) - read(x,p[y]+,n,y);ans%=mod;
         ans += (ll)Query(rt[y-],rt[x],,n,,p[y]-,y) + read(y-,,p[y]-,y) - read(x,,p[y]-,y);ans%=mod;
         ans = (ans%mod+mod)%mod;
         printf("%lld\n",ans);
         add(x,p[x],-w[x],-);add(y,p[y],-w[y],-);
         swap(p[x],p[y]);swap(w[x],w[y]);
         add(x,p[x],w[x],);add(y,p[y],w[y],);
     }//
     return ;
 }//by tkys_Austin;