据说正解线段树套平衡树
然而网上参考（抄）了一个树状数组套动态开点线段树的
思路比较清楚，看代码应该就明白了
//minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=,mod=1e9+;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(ll x){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
int n,m,a[N],b[N],c[N],cntt[N];
ll ans;
inline void add(int x,int y){
for(;x<=n;x+=x&-x) c[x]+=y,++cntt[x];
}
inline ll sum_v(int x){
ll res=;
for(;x;x-=x&-x) res+=c[x];return res;
}
inline ll sum_cnt(int x){
ll res=;
for(;x;x-=x&-x) res+=cntt[x];return res;
}
int tot,rt[N],cnt[N<<],L[N<<],R[N<<];ll v[N<<];
void insert(int &p,int l,int r,int x,int k,int t){
if(!p) p=++tot;v[p]+=k,cnt[p]+=t;
if(l==r) return;int mid=l+r>>;
if(x<=mid) insert(L[p],l,mid,x,k,t);
else insert(R[p],mid+,r,x,k,t);
}
inline void add(int x,int y,int k,int t){
for(;x<=n;x+=x&-x) insert(rt[x],,n,y,k,t);
}
int query_v(int p,int l,int r,int ql,int qr){
if(!p) return ;
if(ql<=l&&qr>=r) return v[p];int mid=l+r>>;
int res=;
if(ql<=mid) res+=query_v(L[p],l,mid,ql,qr);
if(qr>mid) res+=query_v(R[p],mid+,r,ql,qr);
return res;
}
int query_cnt(int p,int l,int r,int ql,int qr){
if(!p) return ;
if(ql<=l&&qr>=r) return cnt[p];int mid=l+r>>;
int res=;
if(ql<=mid) res+=query_cnt(L[p],l,mid,ql,qr);
if(qr>mid) res+=query_cnt(R[p],mid+,r,ql,qr);
return res;
}
ll Q_v(int l,int r,int ql,int qr){
if(l>r||ql>qr) return ;
ll res=;
for(;r;r-=r&-r) res+=query_v(rt[r],,n,ql,qr);
for(--l;l;l-=l&-l) res-=query_v(rt[l],,n,ql,qr);return res;
}
ll Q_cnt(int l,int r,int ql,int qr){
if(l>r||ql>qr) return ;
ll res=;
for(;r;r-=r&-r) res+=query_cnt(rt[r],,n,ql,qr);
for(--l;l;l-=l&-l) res-=query_cnt(rt[l],,n,ql,qr);return res;
}
inline void dec(ll &x,ll y){
while(x<y) x+=mod;x-=y;
}
int main(){
//freopen("testdata.in","r",stdin);
n=read(),m=read();
for(int i=;i<=n;++i) a[i]=read(),b[i]=read();
for(int i=n;i;--i) add(a[i],b[i]),(ans+=sum_v(a[i]-)+sum_cnt(a[i]-)*b[i])%=mod;
for(int i=;i<=n;++i) add(i,a[i],b[i],);
while(m--){
int l=read(),r=read();
if(l>r) swap(l,r);
if(l==r) {print(ans);continue;}
(ans+=Q_v(l+,r-,,a[r]-))%=mod;
(ans+=Q_cnt(l+,r-,,a[r]-)*b[r])%=mod;
dec(ans,Q_v(l+,r-,a[r]+,n));
dec(ans,Q_cnt(l+,r-,a[r]+,n)*b[r]);
(ans+=Q_v(l+,r-,a[l]+,n))%=mod;
(ans+=Q_cnt(l+,r-,a[l]+,n)*b[l])%=mod;
dec(ans,Q_v(l+,r-,,a[l]-));
dec(ans,Q_cnt(l+,r-,,a[l]-)*b[l]);
if(a[l]>a[r]) dec(ans,b[l]+b[r]);
else (ans+=b[l]+b[r])%=mod;
add(l,a[l],-b[l],-),add(l,a[r],b[r],);
add(r,a[r],-b[r],-),add(r,a[l],b[l],);
swap(a[l],a[r]),swap(b[l],b[r]);
print(ans);
}
Ot();
return ;
}