IX.[TJOI2017]不勤劳的图书管理员
我要举报……出题人语文明显不太好……
首先，这题就是上一题的带权版。
然后，这题带了权后和上一题就不太一样了。
当你交换位置\(x,y\)的书后，（默认\(x<y\)）
位置在\(x\)前或在\(y\)后的书不受影响；
位置在\(x,y\)之间，且\(val_z\in(val_x,val_y)\)的书\(z\)，效果和之前一样。只不过，这次还要算上\(x\)和\(y\)的贡献。
位置在\(x,y\)之间，且\(val_z\in(1,val_x)\)的书\(z\)，虽然它自己的贡献没变，但是它对\(x,y\)的贡献却改变了；具体的说，改变了\(val_y-val_x\)。
位置在\(x,y\)之间，且\(val_z\in(val_y,n)\)的书\(z\)，类似的，改变了\(val_x-val_y\)。
然后因为出题人语文不好，我整整在错误的方向上努力了一晚上……
代码（比第一篇暴力的题解还要慢……）：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define mid ((l+r)>>1)
#define pii pair<int,int>
pii operator +(const pii &x,const pii &y){
return make_pair((x.first+y.first)%mod,(x.second+y.second)%mod);
}
void operator +=(pii &x,const pii &y){
(x.first+=y.first)%=mod,(x.second+=y.second)%=mod;
}
pii operator -(const pii &x,const pii &y){
return make_pair((x.first-y.first+mod)%mod,(x.second-y.second+mod)%mod);
}
typedef long long ll;
int n,m,root[50100],cnt,val[50100],bok[50100],pos[50100],res;
struct node{
int lson,rson;
pii sum;
}seg[10010000];
void add(int &x,int l,int r,int P,int val){
if(l>P||r<P)return;
if(!x)x=++cnt;
(seg[x].sum.first+=(val+mod)%mod)%=mod;
(seg[x].sum.second+=(val>0?1:-1)+mod)%=mod;
if(l!=r)add(seg[x].lson,l,mid,P,val),add(seg[x].rson,mid+1,r,P,val);
}
void ADD(int x,int y,int k){
while(x<=n)add(root[x],1,n,y,k),x+=x&-x;
}
pii ask(int x,int l,int r,int L,int R){
if(!x||l>R||r<L)return make_pair(0,0);
if(L<=l&&r<=R)return seg[x].sum;
return ask(seg[x].lson,l,mid,L,R)+ask(seg[x].rson,mid+1,r,L,R);
}
pii ASK(int x,int L,int R){
pii ret=make_pair(0,0);
while(x)ret+=ask(root[x],1,n,L,R),x-=x&-x;
return ret;
}
int SWAP(int x,int y){
if(x==y)return res;
if(x>y)swap(x,y);
ADD(x,bok[x],-val[x]),ADD(y,bok[y],-val[y]);
if(bok[x]<bok[y]){
pii tmp;
tmp=ASK(y-1,bok[x],bok[y])-ASK(x,bok[x],bok[y]);
(res+=(tmp.first<<1)%mod)%=mod;
(res+=1ll*(tmp.second+1)*(val[x]+val[y])%mod)%=mod;
tmp=ASK(y-1,1,bok[x])-ASK(x,1,bok[x]);
(res+=1ll*(val[y]-val[x]+mod)%mod*tmp.second%mod)%=mod;
tmp=ASK(y-1,bok[y],n)-ASK(x,bok[y],n);
(res+=1ll*(val[x]-val[y]+mod)%mod*tmp.second%mod)%=mod;
}
else{
pii tmp;
tmp=ASK(y-1,bok[y],bok[x])-ASK(x,bok[y],bok[x]);
(res+=mod-(tmp.first<<1)%mod)%=mod;
(res+=mod-1ll*(tmp.second+1)*(val[x]+val[y])%mod)%=mod;
tmp=ASK(y-1,1,bok[y])-ASK(x,1,bok[y]);
(res+=1ll*(val[y]-val[x]+mod)%mod*tmp.second%mod)%=mod;
tmp=ASK(y-1,bok[x],n)-ASK(x,bok[x],n);
(res+=1ll*(val[x]-val[y]+mod)%mod*tmp.second%mod)%=mod;
}
swap(bok[x],bok[y]),swap(val[x],val[y]);
ADD(x,bok[x],val[x]),ADD(y,bok[y],val[y]);
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&bok[i],&val[i]);
pii tmp=ASK(i,bok[i],n);
(res+=tmp.first)%=mod;
(res+=1ll*tmp.second*val[i]%mod)%=mod;
ADD(i,bok[i],val[i]);
}
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),printf("%d\n",SWAP(x,y));
return 0;
}