[TJOI2017] 不勤劳的图书管理员

有 (n) 个元素构成的序列，每个元素有属性 (a[i],v[i])，有 (m) 次操作，每次给定 (x,y)，交换这两个元素的位置。你需要在每次操作后输出序列的混乱度。如果 (i<j and a[i]>a[j]) 就会贡献 (v[i]+v[j]) 的混乱度。

Solution

丢到二维平面上，(x) 表示顺序，(y) 表示 (a)，外层普通线段树，内层权值线段树，维护和即可

需要垃圾回收，日常卡常

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 100005;
const int M = 1.5e7;
const int mod = 1e+9+7;

int n,m,a[N],v[N],ans;

inline int prot(int x) {
    if(x>mod) return x-mod;
    return x;
}

struct node {
    int sum; signed cnt;
    node operator + (const node &b) const {
        return {prot(this->sum+b.sum), prot(this->cnt+b.cnt)};
    }
    bool empty() {
        return sum==0 && cnt==0;
    }
};

namespace iseg {
    node tr[M]; signed ch[M][2];
    signed s[M+1], top;
    void init() {
        for(int i=1;i<M;i++) s[++top]=i;
    }
    int newnode() {
        signed tmp=s[top--];
        return tmp;
    }
    void modify(int p,int l,int r,int pos,node val) {
        tr[p]=tr[p]+val;
        if(l<r) {
            if(pos<=(l+r)/2) {
                if(ch[p][0]==0) ch[p][0]=newnode();
                modify(ch[p][0],l,(l+r)/2,pos,val);
                if(tr[ch[p][0]].empty()) {
                    s[++top]=ch[p][0];
                    ch[p][0]=0;
                }
            }
            else {
                if(ch[p][1]==0) ch[p][1]=newnode();
                modify(ch[p][1],(l+r)/2+1,r,pos,val);
                if(tr[ch[p][1]].empty()) {
                    s[++top]=ch[p][1];
                    ch[p][1]=0;
                }
            }
        }
    }
    node query(int p,int l,int r,int ql,int qr) {
        if(l>qr||r<ql||!p) return {0,0};
        if(l>=ql&&r<=qr) return tr[p];
        return query(ch[p][0],l,(l+r)/2,ql,qr)+query(ch[p][1],(l+r)/2+1,r,ql,qr);
    }
}

namespace oseg {
    int tr[N*4];
    void modify(int p,int l,int r,int x,int y,node v) {
        if(tr[p]==0) tr[p]=iseg::newnode();
        iseg::modify(tr[p],1,n,y,v);
        if(l<r) {
            if(x<=(l+r)/2) modify(p*2,l,(l+r)/2,x,y,v);
            else modify(p*2+1,(l+r)/2+1,r,x,y,v);
        }
    }
    void modify(int x,int y,node v) {
        modify(1,1,n,x,y,v);
    }
    node query(int p,int l,int r,int ql,int qr,int vl,int vr) {
        if(l>qr||r<ql) return {0,0};
        if(l>=ql&&r<=qr) return iseg::query(tr[p],1,n,vl,vr);
        return query(p*2,l,(l+r)/2,ql,qr,vl,vr)+query(p*2+1,(l+r)/2+1,r,ql,qr,vl,vr);
    }
    node query(int ql,int qr,int vl,int vr) {
        return query(1,1,n,ql,qr,vl,vr);
    }
}

void modify(int x,int y,node v) {
    oseg::modify(x,y,v);
}

node query(int ql,int qr,int vl,int vr) {
    return oseg::query(ql,qr,vl,vr);
}

int calc(int i,int l,int r) {
    node tmp = query(i+1,r,1,a[i]-1) + query(l,i-1,a[i]+1,n);
    //cout<<"calc "<<i<<"  "<<tmp.cnt<<","<<tmp.sum<<endl;
    return (tmp.cnt*v[i]+tmp.sum)%mod;
}

signed main() {
    ios::sync_with_stdio(false);
    iseg::init();
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i]>>v[i];
    for(int i=1;i<=n;i++) {
        modify(i,a[i],{v[i],1});
        ans+=calc(i,1,n);
    }
    for(int i=1;i<=m;i++) {
        int x,y;
        cin>>x>>y;
        ans-=calc(x,min(x,y),max(x,y));
        modify(x,a[x],{-v[x],-1});
        ans-=calc(y,min(x,y),max(x,y));
        modify(y,a[y],{-v[y],-1});
        swap(a[x],a[y]);
        swap(v[x],v[y]);
        modify(x,a[x],{v[x],1});
        ans+=calc(x,min(x,y),max(x,y));
        modify(y,a[y],{v[y],1});
        ans+=calc(y,min(x,y),max(x,y));
        cout<<ans%mod<<endl;
    }
}