题目地址：洛谷：【P3759】[TJOI2017]不勤劳的图书管理员 – 洛谷、BZOJ：Problem 4889. — [Tjoi2017]不勤劳的图书管理员

题目描述

加里敦大学有个帝国图书馆，小豆是图书馆阅览室的一个书籍管理员。他的任务是把书排成有序的，所以无序的书让他产生厌烦，两本乱序的书会让小豆产生这两本书页数的和的厌烦度。现在有n本被打乱顺序的书，在接下来m天中每天都会因为读者的阅览导致书籍顺序改变位置。因为小豆被要求在接下来的m天中至少要整理一次图书。小豆想知道，如果他前i天不去整理，第i天他的厌烦度是多少，这样他好选择厌烦度最小的那天去整理。

题意简述

给一个数组，数组中一对逆序对的贡献是逆序对代表的数字的权值和，现在有m次操作，每次操作交换数组中两个位置的数字，要求输出每次交换完成后的上述贡献总和。

输入输出格式

输入格式：
第一行会有两个数，n，m分别表示有n本书，m天
接下来n行，每行两个数，ai和vi，分别表示第i本书本来应该放在ai的位置，这本书有vi页，保证不会有放置同一个位置的书
接下来m行，每行两个数，xj和yj，表示在第j天的第xj本书会和第yj本书会因为读者阅读交换位置

输出格式：
一共m行，每行一个数，第i行表示前i天不去整理，第i天小豆的厌烦度，因为这个数可能很大，所以将结果模10^9 +7后输出

输入输出样例

输入样例#1：

5 5
1 1
2 2
3 3
4 4
5 5
1 5
1 5
2 4
5 3
1 3

输出样例#1：

42
0
18
28
48

说明

对于20%的数据，1 ≤ ai; xj; yj ≤ n ≤ 5000, m ≤ 5000, vi ≤ 10^5
对于100%的数据，1 ≤ ai; xj; yj ≤ n ≤ 50000, m ≤ 50000, vi ≤ 10^5

题解

动态逆序对？我们想到了这个题[CQOI2011]动态逆序对。其实可以照搬这个题的树套树。
下面的内容默认你会用树套树解决上面那个题了。
我们考虑带权逆序对怎么解决。我们可以把权值也塞进线段树中，每次查询查找区间比某个数大/小的数字的个数以及权值和，个数*该数权值+权值和就是这个数与其他数字能产生的权值总和。
交换一对数字的时候，我们考虑先把这两个数字对答案的贡献减掉，然后从线段树里面抹去，再重新插入，加入贡献。注意如果先操作线段树再计算会造成重复计算，因此要操作一个加减一次，详细见代码。
总复杂度为O(n \log^2 n)。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 50005, MO = 1e9 + 7;

struct Node {
    int lch, rch, cnt; LL sum;
    inline Node operator+(const Node &rhs) const {
        Node res = *this;
        res.cnt += rhs.cnt;
        res.sum += rhs.sum;
        return res;
    }
    inline Node& operator+=(const Node &rhs) {
        return *this = *this + rhs;
    }
    inline Node operator-(const Node &rhs) const {
        Node res = *this;
        res.cnt -= rhs.cnt;
        res.sum -= rhs.sum;
        return res;
    }
    inline Node& operator-=(const Node &rhs) {
        return *this = *this - rhs;
    }
} tr[MAXN * 200];
int rt[MAXN], tot;

int sta[MAXN], stop;

inline int newnode() {
    if(!stop) return ++tot;
    int p = sta[--stop];
    memset(tr + p, 0, sizeof(Node));
    return p;
}

inline void delnode(int p) {
    if(!p) return;
    sta[stop++] = p;
}

inline void insert(int &o, int l, int r, int x, LL v) {
    int p = newnode(); tr[p] = tr[o]; delnode(o); o = p;
    tr[o].cnt++; tr[o].sum += v;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) insert(tr[o].lch, l, mid, x, v);
    else insert(tr[o].rch, mid + 1, r, x, v);
}

inline void erase(int &o, int l, int r, int x, LL v) {
    int p = newnode(); tr[p] = tr[o]; delnode(o); o = p;
    tr[o].cnt--; tr[o].sum -= v;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) erase(tr[o].lch, l, mid, x, v);
    else erase(tr[o].rch, mid + 1, r, x, v);
}

inline Node querylar(int o, int l, int r, int x) {
    if(l == r) return Node {0, 0, 0, 0};
    int mid = (l + r) >> 1;
    if(x <= mid) return tr[tr[o].rch] + querylar(tr[o].lch, l, mid, x);
    else return querylar(tr[o].rch, mid + 1, r, x);
}

inline Node querysma(int o, int l, int r, int x) {
    if(l == r) return Node {0, 0, 0, 0};
    int mid = (l + r) >> 1;
    if(x <= mid) return querysma(tr[o].lch, l, mid, x);
    else return tr[tr[o].lch] + querysma(tr[o].rch, mid + 1, r, x);
}

int n, m;

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int x, int a, LL p) {
    for(int i = x; i <= n; i += lowbit(i)) {
        insert(rt[i], 1, n, a, p);
    }
}

inline void erase(int x, int a, LL p) {
    for(int i = x; i <= n; i += lowbit(i)) {
        erase(rt[i], 1, n, a, p);
    }
}

inline LL query(int x, int a, LL p) {
    LL res = 0; Node tmp;
    for(int i = x; i; i -= lowbit(i)) {
        tmp = querylar(rt[i], 1, n, a);
        res += tmp.sum + tmp.cnt * p;
        res %= MO;
    }
    x += 0;
    for(int i = n; i; i -= lowbit(i)) {
        tmp = querysma(rt[i], 1, n, a);
        res += tmp.sum + tmp.cnt * p;
        res %= MO;
    }
    x += 0;
    for(int i = x; i; i -= lowbit(i)) {
        tmp = querysma(rt[i], 1, n, a);
        res -= tmp.sum + tmp.cnt * p;
        res = (res % MO + MO) % MO;
    }
    x += 0;
    return res;
}

int a[MAXN], v[MAXN], x, y;

int main() {
    n = readint(); m = readint();
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        a[i] = readint(); v[i] = readint();
        add(i, a[i], v[i]);
        ans += query(i, a[i], v[i]); ans %= MO;
    }
    while(m--) {
        x = readint(); y = readint();
        ans -= query(x, a[x], v[x]); ans = (ans % MO + MO) % MO;
        erase(x, a[x], v[x]);
        ans -= query(y, a[y], v[y]); ans = (ans % MO + MO) % MO;
        erase(y, a[y], v[y]);
        std::swap(a[x], a[y]);
        std::swap(v[x], v[y]);
        add(x, a[x], v[x]);
        ans += query(x, a[x], v[x]); ans %= MO;
        add(y, a[y], v[y]);
        ans += query(y, a[y], v[y]); ans %= MO;
        printf("%lld\n", ans);
    }
    return 0;
}