1 solutions
-
0
C++ :
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0' || '9'<ch)ch=getchar(); while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar(); return x; } typedef long long ll; const int M=1e5+9; const int N=50009; const ll md=1e9+7; int n,q; int st[N],ed[N],id[N],a[N]; ll ans,sum[N],v[N],bit1[M],bit2[M]; inline void cal(ll &x){x%=md;if(x<0)x=(x%md+md)%md;} inline bool cmp(int x,int y) { return a[x]<a[y]; } inline void add(ll *bit,int p,ll v) { for(int i=p;i<M;i+=(i&-i)) bit[i]=((bit[i]+v)%md+md)%md; } inline ll query(ll *bit,int p) { ll ret=0; for(int i=p;i;i-=(i&-i)) (ret+=bit[i])%=md; return ret; } int main() { n=read();q=read(); int blk=sqrt(n); for(int i=1;i<=n;i++) { a[i]=read(); v[i]=read()%md; id[i]=i; if(!st[i/blk]) { st[i/blk]=i; if(i-1) ed[(i-1)/blk]=i-1; } } ed[n/blk]=n; for(int i=0,e=n/blk;i<=e;i++) { sort(id+st[i],id+ed[i]+1,cmp); sum[st[i]]=v[id[st[i]]]; for(int j=st[i]+1;j<=ed[i];j++) sum[j]=(sum[j-1]+v[id[j]])%md; } ans=0; for(int i=n;i>=1;i--) { ans=(ans+query(bit1,a[i])+query(bit2,a[i])*v[i]%md)%md; add(bit1,a[i],v[i]);add(bit2,a[i],1); } while(q--) { int x=read(),y=read(); if(x>y)swap(x,y); int lb=x/blk,rb=y/blk; if(lb==rb) { for(int i=x;i<=y;i++) { if(x<i) { if(a[x]<a[i]) cal(ans+=(v[x]+v[i])%md); else cal(ans-=(v[x]+v[i])%md); } if(i!=x && i<y) { if(a[i]<a[y]) cal(ans+=(v[y]+v[i])%md); else cal(ans-=(v[i]+v[y])%md); } } swap(a[x],a[y]); swap(v[x],v[y]); sort(id+st[lb],id+ed[lb]+1,cmp); sum[st[lb]]=v[id[st[lb]]]; for(int j=st[lb]+1;j<=ed[lb];j++) sum[j]=(sum[j-1]+v[id[j]])%md; cal(ans); printf("%lld\n",ans); continue; } for(int i=x+1;i<=ed[lb];i++) if(a[x]<a[i]) cal(ans+=v[x]+v[i]); else cal(ans-=v[x]+v[i]); for(int i=st[rb];i<=y;i++) if(a[x]<a[i]) cal(ans+=v[x]+v[i]); else cal(ans-=v[x]+v[i]); for(int i=x+1;i<=ed[lb];i++) if(a[i]<a[y]) cal(ans+=v[y]+v[i]); else cal(ans-=v[y]+v[i]); for(int i=st[rb];i<y;i++) if(a[i]<a[y]) cal(ans+=v[y]+v[i]); else cal(ans-=v[y]+v[i]); for(int i=lb+1;i<rb;i++) { int l=st[i],r=ed[i],val=st[i]-1,mid; while(l<=r) { mid=l+r>>1; if(a[id[mid]]<a[x]) l=mid+1,val=mid; else r=mid-1; } cal(ans+=sum[ed[i]]-2*sum[val<st[i]?0:val]%md); cal(ans+=v[x]*(ed[i]-2*val+st[i]-1)%md); l=st[i],r=ed[i],val=st[i]-1; while(l<=r) { mid=l+r>>1; if(a[id[mid]]<a[y]) l=mid+1,val=mid; else r=mid-1; } cal(ans+=2*sum[val<st[i]?0:val]%md-sum[ed[i]]); cal(ans+=v[y]*(2*val-ed[i]-st[i]+1)%md); } swap(a[x],a[y]); swap(v[x],v[y]); sort(id+st[lb],id+ed[lb]+1,cmp); sort(id+st[rb],id+ed[rb]+1,cmp); sum[st[lb]]=v[id[st[lb]]]; for(int j=st[lb]+1;j<=ed[lb];j++) sum[j]=(sum[j-1]+v[id[j]])%md; sum[st[rb]]=v[id[st[rb]]]; for(int j=st[rb]+1;j<=ed[rb];j++) sum[j]=(sum[j-1]+v[id[j]])%md; cal(ans); printf("%lld\n",ans); } return 0; }
- 1
Information
- ID
- 18800
- Time
- 5000ms
- Memory
- 256MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By