大了就 MLE,小了就 RE。
#include<bits/stdc++.h>
#define LL int
#define LF long double
#define pLL pair<LL,LL>
#define pb push_back
#define LowBound lower_bound
#define UpBound upper_bound
#define Fi first
#define Se second
using namespace std;
//const LL Inf;
const int N=5e4+5;
const int M=5e4;
const long long Mod=1e9+7;
const int MM=1e7+5;
//const LF eps;
//const LL P;
namespace ST
{
int tot,Ls[MM],Rs[MM],Sz[MM];
long long S[MM];
void Up(LL Rt)
{
S[Rt]=(S[Ls[Rt]]+S[Rs[Rt]])%Mod;
Sz[Rt]=Sz[Ls[Rt]]+Sz[Rs[Rt]];
}
void Upd(LL &Rt,LL L,LL R,LL x,LL k,LL Flg)
{
if(!Rt)Rt=++tot;
if(L==R)
{
S[Rt]=(S[Rt]+k+Mod)%Mod;
Sz[Rt]+=Flg;
return;
}
LL Mid=L+R>>1;
if(x<=Mid)Upd(Ls[Rt],L,Mid,x,k,Flg);
else Upd(Rs[Rt],Mid+1,R,x,k,Flg);
Up(Rt);
}
pLL Qry(LL Rt,LL L,LL R,LL l,LL r)
{
if(!Rt||R<l||r<L)return {0,0};
if(l<=L&&R<=r)return {S[Rt],Sz[Rt]};
LL Mid=L+R>>1;
pLL X=Qry(Ls[Rt],L,Mid,l,r),Y=Qry(Rs[Rt],Mid+1,R,l,r);
return {(X.Fi+Y.Fi)%Mod,(X.Se+Y.Se)%Mod};
}
}
#define Ls(x) (x<<1)
#define Rs(x) (x<<1|1)
LL rt[N<<2];
LL n,m,A[N],B[N];
void Ins(LL Rt,LL L,LL R,LL x,LL i)
{
// cout<<"Ins"<<L<<' '<<R<<' '<<i<<endl;
ST::Upd(rt[Rt],1,M,A[i],B[i],1);
if(L==R)return;
LL Mid=L+R>>1;
if(x<=Mid)Ins(Ls(Rt),L,Mid,x,i);
else Ins(Rs(Rt),Mid+1,R,x,i);
}
void Del(LL Rt,LL L,LL R,LL x,LL i)
{
// cout<<"Del"<<L<<' '<<R<<' '<<i<<endl;
ST::Upd(rt[Rt],1,M,A[i],-B[i],-1);
if(L==R)return;
LL Mid=L+R>>1;
if(x<=Mid)Del(Ls(Rt),L,Mid,x,i);
else Del(Rs(Rt),Mid+1,R,x,i);
}
pLL Qry(LL Rt,LL L,LL R,LL l,LL r,LL x,LL y)
{
if(R<l||r<L)return {0,0};
if(l<=L&&R<=r)
{
pLL X=ST::Qry(rt[Rt],1,M,x,y);
// cout<<L<<' '<<R<<' '<<x<<' '<<y<<' '<<X.Fi<<' '<<X.Se<<endl;
return {X.Fi,X.Se};
}
LL Mid=L+R>>1;
pLL X=Qry(Ls(Rt),L,Mid,l,r,x,y),Y=Qry(Rs(Rt),Mid+1,R,l,r,x,y);
return {(X.Fi+Y.Fi)%Mod,(X.Se+Y.Se)%Mod};
}
long long Ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&A[i],&B[i]);
pLL t=Qry(1,1,n,1,i-1,A[i]+1,M);
Ans=(Ans+t.Se*B[i]%Mod+t.Fi)%Mod;
Ins(1,1,n,i,i);
}
for(int i=1;i<=m;i++)
{
LL x,y;
scanf("%d%d",&x,&y);
if(x==y)
{
printf("%lld\n",Ans);
continue;
}
if(x>y)swap(x,y);
if(A[x]>A[y])Ans-=(B[x]+B[y]);
if(A[y]>A[x])Ans+=(B[x]+B[y]);
// cout<<Ans<<endl;
if(x+1<=y-1)
{
pLL t1=Qry(1,1,n,x+1,y-1,1,A[y]-1);// A[y] Add
// cout<<t1.Se<<endl;
Ans=(Ans+t1.Se*B[y]%Mod+t1.Fi)%Mod;
pLL t2=Qry(1,1,n,x+1,y-1,A[y]+1,M);// A[y] Del
Ans=(Ans-t2.Se*B[y]%Mod-t2.Fi+2*Mod)%Mod;
pLL t3=Qry(1,1,n,x+1,y-1,A[x]+1,M);// A[x] Del
Ans=(Ans+t3.Se*B[x]%Mod+t3.Fi)%Mod;
pLL t4=Qry(1,1,n,x+1,y-1,1,A[x]-1);// A[x] Add
Ans=(Ans-t4.Se*B[x]%Mod-t4.Fi+2*Mod)%Mod;
}
Del(1,1,n,x,x);
Del(1,1,n,y,y);
swap(A[x],A[y]);
swap(B[x],B[y]);
Ins(1,1,n,x,x);
Ins(1,1,n,y,y);
printf("%lld\n",Ans);
}
return 0;
}
//RP++