UVA 11990 “Dynamic‘‘ Inversion 区域树 + 树状数组

一、题目大意

我们有 1 2 3 ... n 这些数字组成的一个排列数组 a ，需要从这个排列中取出m个数字，要求计算出出每次取出数字之前，数组中的逆序数（逆序数就是 i < j，但是 ai > aj的数）

二、解题思路

我们以数组为基础构建一颗区域树，每个节点保存下标在 [l , r)的元素，并按照元素的值排序。

针对于题目的开始，我们可以计算 0<=i<n 的所有ai，j < i 但 aj > ai的个数，这个数量求和即最初的逆序数，计算的方式就是去区域树上查到 [0 , i)区间内的节点，每个节点 lower_bound计数，求出sum。（因为每个元素都循环，所以仅考虑它前面的元素即可，后面的元素会在循环时计算到）

然后针对每次要移除的数字 ai，只需要去 [0 , i)区间的树节点依次进行二分即可知道 j < i，且 aj > ai的个数 x，然后去 [i+1 , n)的数节点进行二分，即可知道 j > i，且aj < ai的个数 y，sum=sum-x-y

每次移除数字之前，输出sum

同时数字被移除了，下次要避免重复计算，所以可以对区域上每个节点建立一个树状数组，每次移除一个数字时，需要去当前数字的节点和它的父节点上，用过二分找到这个数组的下标，将下标+1的位置更新1（树状数组的有效下标从1开始），注意也要循环更新父节点 ( p = (p - 1)/2)

这样每次去区域树上lower_bound得到idx时，通过树状数组求和两次（[1,idx],[1,l-r])，去掉那些已经被移除的数字，即可避免重复计算。

三、代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int *bit[524288];
int *dat[524288];
int datL[524288], datR[524288];
int n, m, num[200007], seq[200007], num2Idx[200007];
int _current, _currentLt, _currentGt;
char opType;
void input()
{for (int i = 0; i < n; i++){scanf("%d", &num[i]);num2Idx[num[i]] = i;}for (int i = 0; i < m; i++){scanf("%d", &seq[i]);}
}
int calcSize(int _size)
{int size = 1;while (size < _size){size = size * 2;}return size;
}
void build(int i, int l, int r)
{if (r - l == 1){dat[i] = new int[1];dat[i][0] = num[l];}else{int lch = i * 2 + 1;int rch = i * 2 + 2;int mid = (l + r) / 2;build(lch, l, mid);build(rch, mid, r);dat[i] = new int[r - l];merge(dat[lch], dat[lch] + (mid - l), dat[rch], dat[rch] + (r - mid), dat[i]);}datL[i] = l;datR[i] = r;int size = calcSize(r - l);bit[i] = new int[size + 1];for (int j = 0; j <= size; j++){bit[i][j] = 0;}
}
int sum(int idx, int i)
{int res = 0;for (int j = i; j > 0; j = j - (j & (-j))){res = res + bit[idx][j];}return res;
}
void update(int idx, int i, int x, int size)
{if (i <= 0){return;}for (int j = i; j <= size; j = j + (j & (-j))){bit[idx][j] = bit[idx][j] + x;}
}
void queryCnt(int i, int l, int r)
{int lt = lower_bound(dat[i], dat[i] + (r - l), _current) - dat[i];int size = calcSize(r - l);int realLt = lt - sum(i, lt);int realAll = (r - l) - sum(i, size);int realGt = realAll - realLt;_currentLt = _currentLt + realLt;_currentGt = _currentGt + realGt;
}
void updateTree(int i)
{update(i, 1, 1, 1);int j = i;while (j > 0){j = (j - 1) / 2;int idx = lower_bound(dat[j], dat[j] + (datR[j] - datL[j]), _current) - dat[j];int size = calcSize(datR[j] - datL[j]);update(j, idx + 1, 1, size);}
}
void query(int _l, int _r, int i, int l, int r, char opType)
{if (_l >= r || _r <= l){}else if (l >= _l && r <= _r){if (opType == 'q'){queryCnt(i, l, r);}if (opType == 'u'){updateTree(i);}}else{query(_l, _r, i * 2 + 1, l, (l + r) / 2, opType);query(_l, _r, i * 2 + 2, (l + r) / 2, r, opType);}
}
void solve()
{ll val = 0LL;for (int i = 0; i < n; i++){_current = num[i];_currentLt = 0, _currentGt = 0;query(0, i, 0, 0, n, 'q');val = val + _currentGt;}for (int i = 0; i < m; i++){printf("%lld\n", val);_current = seq[i];_currentLt = 0, _currentGt = 0;query(0, num2Idx[seq[i]], 0, 0, n, 'q');val = val - _currentGt;_currentLt = 0, _currentGt = 0;query(num2Idx[seq[i]] + 1, n, 0, 0, n, 'q');val = val - _currentLt;query(num2Idx[seq[i]], num2Idx[seq[i]] + 1, 0, 0, n, 'u');}
}
int main()
{while (~scanf("%d%d", &n, &m)){input();build(0, 0, n);solve();}return 0;
}