1 solutions

  • 0
    @ 2025-11-5 18:08:46

    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