动态逆序对 CDQ 分治
传送门: https://www.luogu.org/problemnew/show/P3157
题意:
对于序列 A, 它的逆序对数定义为满足 i<j, 且 Ai>Aj 的数对 (i,j) 的个数. 给 1 到 n 的一个排列, 按照某种顺序依次删除 m 个元素, 你的任务是在每次删除一个元素之前统计整个序列的逆序对数.
题解:
这个题是告诉你如何将一个问题转换为三维偏序问题
首先, 求解逆序对, 那么 a.val>b.val, 删除一个元素的时间是 t,a.t<b.t, 这个元素对应的原序列中的位置为 pos, 那么 a.pos<b.pos, 这样我们就可以转换为一个三维偏序的问题
对于这个三维偏序问题, 我们就可以采用 cdq 分治给解决, 逆序对的统计可以套一个树状数组解决
代码:
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- using namespace std;
- typedef long long LL;
- typedef pair<int, int> pii;
- typedef unsigned long long uLL;
- #define ls rt<<1
- #define rs rt<<1|1
- #define lson l,mid,rt<<1
- #define rson mid+1,r,rt<<1|1
- #define bug printf("*********\n")
- #define FIN freopen("input.txt","r",stdin);
- #define FON freopen("output.txt","w+",stdout);
- #define IO iOS::sync_with_stdio(false),cin.tie(0)
- #define debug1(x) cout<<"["<<#x<<""<<(x)<<"]\n"#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
- const int maxn = 3e5 + 5;
- const int INF = 0x3f3f3f3f;
- int lowbit(int x) {
- return x & (-x);
- }
- int bit[maxn];
- void add(int pos, int val) {
- while(pos <maxn) {
- bit[pos] += val;
- pos += lowbit(pos);
- }
- }
- int sum(int pos) {
- int res = 0;
- while(pos) {
- res += bit[pos];
- pos -= lowbit(pos);
- }
- return res;
- }
- int n, m;
- struct node {
- int m, v, d, id, t;
- } a[maxn];
- LL ans[maxn];
- bool cmpd(node a, node b) {
- return a.d <b.d;
- }
- void CDQ(int l, int r) {
- if(l == r) return;
- int mid = (l + r)>> 1;
- CDQ(l, mid);
- CDQ(mid + 1, r);
- sort(a + l, a + mid + 1, cmpd);
- sort(a + mid + 1, a + r + 1, cmpd);
- int j = l;
- for(int i = mid + 1; i <= r; ++i) {
- while(j <= mid && a[j].d <= a[i].d) {
- add(a[j].v, a[j].m);
- j++;
- }
- ans[a[i].id] += a[i].m * (sum(n) - sum(a[i].v));
- }
- for(int i = l; i <j; i++) {
- add(a[i].v, -a[i].m);
- }
- j = mid;
- for(int i = r; i> mid; i--) {
- while(j>= l && a[j].d>= a[i].d) {
- add(a[j].v, a[j].m);
- j--;
- }
- ans[a[i].id] += a[i].m * sum(a[i].v - 1);
- }
- for(int i = mid; i> j; i--) {
- add(a[i].v, -a[i].m);
- }
- }
- int match[maxn];
- int main() {
- #ifndef ONLINE_JUDGE
- FIN
- #endif
- scanf("%d%d", &n, &m);
- int tot = 0;
- for(int i = 1, x; i <= n; i++) {
- scanf("%d", &x);
- match[x] = i;
- a[++tot].m = 1;
- a[tot].v = x;
- a[tot].d = i;
- a[tot].id = 0;
- a[tot].t = tot;
- }
- for(int i = 1, x; i <= m; i++) {
- scanf("%d", &x);
- a[++tot].m = -1;
- a[tot].v = x;
- a[tot].d = match[x];
- a[tot].id = i;
- a[tot].t = tot;
- }
- CDQ(1, tot);
- for(int i = 1; i <= m; i++) {
- ans[i] += ans[i - 1];
- }
- for(int i = 0; i < m; i++) {
- printf("%lld\n", ans[i]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3122910.html