首页 > 编程语言 > 详细

ZOJ - 2112【Dynamic Rankings】 带修改主席树 + 树状数组

时间:2019-05-27 00:44:03      阅读:82      评论:0      收藏:0      [点我收藏+]

标签:普通   sort   bitset   printf   所有   pac   fopen   sin   个数   

ZOJ - 2112【Dynamic Rankings】 带修改主席树 + 树状数组

https://cn.vjudge.net/contest/304073#problem/E

题意

给定 n 个数和 m 次操作,操作分为两种:

  • Q x y z —— 询问 [x, y] 区间里的第 z 小的数

  • C x y —— 把第 x 个数变成 y

分析

mmp突然想起来可以分块...

这题属于带修改的主席树,需要用到树状数组维护。

如果用普通静态主席树的做法,每次更新都需要把 “该数所在树和之后的所有树” 都进行更新(由于前缀的性质),这样更新的最坏总复杂度为 \(O(n*m)\) 显然不行。

但是可以发现,对于改变 i 位置的值来说,对于 “该数所在树和之后的所有树” 的影响是相同的。因此只要在原来的基础上增加一类树,用于维护更新掉的数,所以我们可以用树状数组来记录更新,每次更新 \(log(n)\) 棵树。

因此我们需要用到离线来做,把题目所给定的所有修改后的值也加入 \(vector\) 中。第一轮建树的时候只需要把修改前的所有值进行建树。

对于更新,我们不改变这些已经建好的树,而是另建一类树S,用来记录更新。用树状数组来维护,也就是树状数组的每个节点都是一颗线段树。初始时,S[0]、S[1]、S[2]、S[3](树状数组的每个节点)这些都与 root[0] 相同(也就是空树 0)。

对于 (C 2 6)操作来说,我们只需要减去 2 ,加上 6 即可。对于减去2(树状数组 \(i+lowbit(i)\) 为 i 的父亲节点, 修改 i,就要把 i 的所有父亲节点都修改了)。因此要更新的是 S[2] 和 S[4] 这两个节点。

当查询的时候, \(sum\) 需要另外再加上 S树 的值之差。

代码

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

const int maxn = 5e4+5;

int n, m, cnt;
int root[maxn];
int a[maxn];
vector<int> v;
int new_n;
int S[maxn];    // 树状数组维护的新树
int use[maxn];  // use记录要操作的线段树下标

struct node {
    int l, r, sum;
}T[maxn*40];

struct Question {
    int f;
    int a, b, c;
}Q[maxn];

void init() {
    v.clear();
    memset(root, 0, sizeof(root));
    for(int i = 0; i <= n*40; i++) {
        T[i].l = T[i].r = T[i].sum = 0;
    }
    cnt = 0;
}

int getid(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

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

void build(int l, int r, int &rt) {
    rt = ++cnt;
    if(l == r) {
        return ;
    }
    int mid = (l+r) / 2;
    build(l, mid, T[rt].l);
    build(mid+1, r, T[rt].r);
}

void update(int l, int r, int &x, int y, int pos, int f) {
    T[++cnt] = T[y];
    T[cnt].sum += f;    // 1 or -1
    x = cnt;
    if(l == r)
        return ;
    int mid = (l+r) / 2;
    if(mid >= pos) {
        update(l, mid, T[x].l, T[y].l, pos, f);
    }
    else {
        update(mid+1, r, T[x].r, T[y].r, pos, f);
    }
}

void Add(int x, int c, int f) {
    while(x <= n) {
        update(1, new_n, S[x], S[x], c, f);
        x += lowbit(x);
    }
}

int Sum(int x) {
    int ans = 0;
    while(x > 0) {
        ans += T[T[use[x]].l].sum;
        x -= lowbit(x);
    }
    return ans;
}

int query(int l, int r, int a, int b, int x, int y, int k) {
    if(l == r) {
        return l;
    }
    int mid = (l+r) / 2;
    int sum = Sum(b) - Sum(a) + T[T[y].l].sum - T[T[x].l].sum;
    if(sum >= k) {
        for(int i = a; i > 0; i -= lowbit(i)) {
            use[i] = T[use[i]].l;
        }
        for(int i = b; i > 0; i -= lowbit(i)) {
            use[i] = T[use[i]].l;
        }
        return query(l, mid, a, b, T[x].l, T[y].l, k);
    }
    else {
        for(int i = a; i > 0; i -= lowbit(i)) {
            use[i] = T[use[i]].r;
        }
        for(int i = b; i > 0; i -= lowbit(i)) {
            use[i] = T[use[i]].r;
        }
        return query(mid+1, r, a, b, T[x].r, T[y].r, k-sum);
    }
}

int main() {
    // fopen("in.txt", "r", stdin);
    // fopen("out.txt", "w", stdout);
    int t;
    scanf("%d", &t);
    while(t--) {
        init();
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            v.push_back(a[i]);
        }
        for(int i = 1; i <= m; i++) {
            char f[10];
            scanf("%s", f);
            if(f[0] == 'Q') {
                int l, r, k;
                scanf("%d%d%d", &l, &r, &k);
                Q[i].f = 0;
                Q[i].a = l;
                Q[i].b = r;
                Q[i].c = k;
            }
            else {
                int x, c;
                scanf("%d%d", &x, &c);
                Q[i].f = 1;
                Q[i].a = x;
                Q[i].b = c;
                v.push_back(c);
            }
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        new_n = (int)v.size();
        for(int i = 1; i <= n; i++) {
            update(1, new_n, root[i], root[i-1], getid(a[i]), 1);
        }
        for(int i = 1; i <= n; i++) {
            S[i] = root[0];
        }
        for(int i = 1; i <= m; i++) {
            if(Q[i].f == 0) {
                for(int j = Q[i].a-1; j > 0; j-= lowbit(j)) {
                    use[j] = S[j];
                }
                for(int j = Q[i].b; j > 0; j -= lowbit(j)) {
                    use[j] = S[j];
                }
                int ans = query(1, new_n, Q[i].a-1, Q[i].b, root[Q[i].a-1], root[Q[i].b], Q[i].c) - 1;
                printf("%d\n", v[ans]);
            }
            else {
                Add(Q[i].a, getid(a[Q[i].a]), -1);  // 减去修改前的值
                Add(Q[i].a, getid(Q[i].b), 1);   // 加上新值
                a[Q[i].a] = Q[i].b;
            }
        }
    }
    return 0;
}

ZOJ - 2112【Dynamic Rankings】 带修改主席树 + 树状数组

标签:普通   sort   bitset   printf   所有   pac   fopen   sin   个数   

原文:https://www.cnblogs.com/Decray/p/10928452.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号