带修改， 维护全局逆序对数。
翻译成另一种风格:
有 n 个点， 每个点两个属性 ai，bi， 每次修改一个点的 bi， 维护全局有多少个点对满足 ai<aj && bi>bj。
将修改换成先删除后插入， 逆序对的变动就看得很清楚了， 总体上还是要二维数点。
树套树轻松搞。
写两道例题。
TJOI2017 不勤劳的图书管理员
把题面翻译成人话。
很多点 (x,y,z)， x 是坐标， y 是应在的位置， z 是页数。
若两个点 (x,y,z)，(a,b,c) 满足 x<a && y>b， 则贡献 z+c。
每次选两个点 (x,y,z)，(a,b,c)， 交换 x,a，求所有有贡献的点对的贡献和。
仔细分析一下 ， 还是一个二维偏序和问题， 树套树维护即可。
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 5e4 + 3, mo = 1e9 + 7, SZ = N * 2 * 20 + 2333;
const LL INF = 1e18;
int n, m, a[N], v[N];
LL ans = 0ll;
struct BIT {
LL t[N];
BIT() {
memset(t, 0, sizeof t);
}
void ins(int x, int v) {
for(; x<=n; x += (x & (-x))) t[x] += v;
}
LL ask_(int x) {
LL res = 0ll;
for(; x; x -= (x & (-x))) res += t[x];
return res;
}
LL ask(int l, int r) {
if(l > r) return 0ll;
return ask_(r) - ask_(l - 1);
}
} bit1, bit2;
int cnt;
#define newnode(s1, s2, v, a, b) (&(*pool[cnt++] = node(s1, s2, v, a, b)))
#define merge(a, b) newnode(a->siz+b->siz, a->sum+b->sum, b->val, a, b)
#define upd(me) if(me->ls->siz) me->siz=me->ls->siz+me->rs->siz, me->sum=me->ls->sum+me->rs->sum, me->val=me->rs->val
struct node{
LL siz, sum, val;
node *ls, *rs;
node(LL s1, LL s2, LL v, node *a, node *b) : siz(s1), sum(s2), val(v), ls(a), rs(b) {
}
node() {
}
} *emp, *root[N], t[SZ], *pool[SZ];
inline void maintain(node *me) {
if(me->ls->siz > me->rs->siz * 4)
me->rs = merge(me->ls->rs, me->rs), pool[--cnt] = me->ls, me->ls = me->ls->ls;
if(me->rs->siz > me->ls->siz * 4)
me->ls = merge(me->ls, me->rs->ls), pool[--cnt] = me->rs, me->rs = me->rs->rs;
}
void ins(LL x, LL v, node *me) {
if(me->siz == 1)
{
node *A = newnode(1, v, x, emp, emp), *B = newnode(1, me->sum, me->val, emp, emp);
if(A->val > B->val) swap(A, B);
me->ls = A, me->rs = B;
// me->ls = newnode(1, x<me->val ? v : me->sum , min(x, me->val), emp, emp),
// me->rs = newnode(1, x<me->val ? me->sum : v, max(x, me->val), emp, emp);
// if(x <= me->val)
// me = merge(newnode(1, v, x, emp, emp), me);
// else
// me = merge(me, newnode(1, v, x, emp, emp));
}
else
ins(x, v, x>me->ls->val ? me->rs : me->ls), maintain(me);
upd(me);
}
void era(LL x, node *me) {
if(me->siz == 1) return;
if(me->ls->siz == 1 && me->ls->val == x)
pool[--cnt] = me->ls, pool[--cnt] = me->rs, *me = *me->rs;
else if(me->rs->siz == 1 && me->rs->val == x)
pool[--cnt] = me->ls, pool[--cnt] = me->rs, *me = *me->ls;
else era(x, x>me->ls->val ? me->rs : me->ls), maintain(me);
upd(me);
}
LL num(int x, node *me) {
if(me->siz == 1) return (me->val <= x);
else return x>=me->ls->val ? me->ls->siz + num(x, me->rs) : num(x, me->ls);
}
LL sum(int x, node *me) {
if(me->siz == 1) return (me->val <= x) * me->sum;
else return x>=me->ls->val ? me->ls->sum + sum(x, me->rs) : sum(x, me->ls);
}
namespace nbBIT {
void ins(int x, int y, int v) {
for(; x<=n; x += (x&(-x))) ins(y, v, root[x]);
}
void del(int x, int y) {
for(; x<=n; x += (x&(-x))) era(y, root[x]);
}
LL num_(int p, int x, int y) {
LL res = 0ll;
for(; p; p -= (p&(-p))) res += (num(y, root[p]) - num(x-1, root[p]));
return res;
}
LL sum_(int p, int x, int y) {
LL res = 0ll;
for(; p; p -= (p&(-p))) res += (sum(y, root[p]) - sum(x-1, root[p]));
return res;
}
LL num(int l, int r, int x, int y) {
if(x>y) return 0ll;
return num_(r, x, y) - num_(l-1, x, y);
}
LL sum(int l, int r, int x, int y) {
if(x>y) return 0ll;
return sum_(r, x, y) - sum_(l-1, x, y);
}
}
int main() {
emp = new node(0, 0, 0, NULL, NULL);
for(int i=0; i<SZ; ++i) pool[i] = &t[i];
scanf("%d%d", &n, &m);
for(int i=1; i<=n; ++i) root[i] = newnode(1, 0, INF, emp, emp);
for(int i=1; i<=n; ++i) {
scanf("%d%d", &a[i], &v[i]);
ans += bit1.ask(a[i]+1, n) * v[i] % mo;
ans %= mo;
ans += bit2.ask(a[i]+1, n) % mo;
ans %= mo;
bit1.ins(a[i], 1);
bit2.ins(a[i], v[i]);
nbBIT::ins(i, a[i], v[i]);
}
//// cout << "# " << ans << '\n';
// // suck it up
// // suck, it, up
while(m--)
{
int x, y;
scanf("%d%d", &x, &y);
if(x>y) swap(x,y);
if(x == y) {
cout << ans << '\n';
continue;
}
int l = x+1, r = y-1;
if(l<=r)
{
// 减去以 x 为首的逆序对
ans -= nbBIT::num(l, r, 1, a[x]-1) * v[x] % mo;
ans -= nbBIT::sum(l, r, 1, a[x]-1) % mo;
ans %= mo;
// 加上以 x 为尾的逆序对
ans += nbBIT::num(l, r, a[x]+1, n) * v[x] % mo;
ans += nbBIT::sum(l, r, a[x]+1, n);
ans %= mo;
// 减去以 y 为尾的逆序对
ans -= nbBIT::num(l, r, a[y]+1, n) * v[y] % mo;
ans -= nbBIT::sum(l, r, a[y]+1, n) % mo;
ans %= mo;
// 加上以 y 为首的逆序对
ans += nbBIT::num(l, r, 1, a[y]-1) * v[y] % mo;
ans += nbBIT::sum(l, r, 1, a[y]-1) % mo;
ans %= mo;
}
if(a[x] > a[y]) ans -= (v[x] + v[y]) % mo;
else ans += (v[x] + v[y]) % mo;
nbBIT::del(x, a[x]), nbBIT::del(y, a[y]);
swap(a[x], a[y]), swap(v[x], v[y]);
nbBIT::ins(x, a[x], v[x]), nbBIT::ins(y, a[y], v[y]);
ans = (ans%mo + mo) % mo;
cout << ans << '\n';
}
// this is life ( wow )
return 0;
}
CQOI2011 动态逆序对
上面那道题的弱化版， 直接写。
开玩笑的， 那道题只有删除， 且看上去就是个三维偏序， 用 CDQ 应该常数小写， 以后写吧（x