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;
}