[bzoj1902][zoj2112]zju2112 dynamic rankings（树状数组 + 主席树）

终于学会了主席树，写了高贵冷艳的带修改区间第K大（虽然二逼平衡树我是用分块水的），关于不带修改的区间第K大参见我的上一篇博客[POJ2104]K-th Number（主席树），其实这个跟树状数组维护前缀和基本是一样的，只是修改时树状数组只需修改(log_2n)个节点，而现在需要修改(log_2n)棵线段树，一共(log_2^2n)个节点。这题在八中上妥妥A了，ZOJ被卡内存（内存小，数据规模还大，还有多组数据，改了半天），到现在都没卡过去，真是不开心。

八中：

//ZJU 2112.cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>

//#define LOCAL
//#define READ_FILE
#define READ_FREAD
//#define VISUAL_STUDIO

const int MAXN = 10010;
const int MAXTMP = 100;
const int MAXTREE = 600000;

#ifdef LOCAL
#define LOCAL_TIME
#define LOCAL_DEBUG
//#define STD_DEBUG
//#define LOCAL_SIMP
#endif

#ifdef VISUAL_STUDIO
#pragma warning(disable: 4996)
#endif

#ifdef LOCAL_TIME
#include<ctime>
#endif

#ifdef READ_FREAD
char fread_char;

inline void fread_init()
{
    fread_char = getchar();
}

inline int get_int()
{
    int ret = 0;
    while ((fread_char < '0') || (fread_char > '9'))
    {
        fread_char = getchar();
    }
    while ((fread_char >= '0') && (fread_char <= '9'))
    {
        ret = ret * 10 + fread_char - '0';
        fread_char = getchar();
    }
    return ret;
}

inline char get_char()
{
    while ((fread_char == ' ') || (fread_char == 'n'))
    {
        fread_char = getchar();
    }
    char ret = fread_char;
    fread_char = getchar();
    return ret;
}
#endif

inline void read(int &a)
{
#ifdef READ_FREAD
    a = get_int();
#else
    scanf("%d", &a);
#endif
}

inline void read(char &a)
{
#ifdef READ_FREAD
    a = get_char();
#else
    scanf("%c", &a);
#endif
}

struct discre_node
{
    int val, id;
    inline bool operator < (const discre_node &b) const
    {
        return val < b.val;
    }
};

struct tree_node
{
    int tot;
    tree_node *l_child, *r_child;
    inline tree_node *init()
    {
        l_child = r_child = 0;
        return this;
    }
};

tree_node recover_tree_node[MAXTREE];
tree_node *stack_recover_tree_node[MAXTREE];
int top_stack_recover_tree_node = MAXTREE;

inline void init_recover_tree_node()
{
    for (int i = 0; i < MAXTREE; i++)
    {
        stack_recover_tree_node[i] = recover_tree_node + i;
    }
}

inline tree_node *new_node()
{
    return stack_recover_tree_node[--top_stack_recover_tree_node]->init();
}

inline void delete_node(tree_node *del_node)
{
    stack_recover_tree_node[top_stack_recover_tree_node++] = del_node;
}

int n, m;
discre_node discre_tmp[2 * MAXN];
int tot_discre;
int discre_to_num[2 * MAXN];
int max_discre;
char op_string;
int discre[MAXN];
int op[MAXN], op_i[MAXN], op_j[MAXN], op_k[MAXN];
tree_node *interval[MAXN];

inline void tree_insert(int root, const int val)
{
    tree_node *tmp = interval[root];
    tree_node **last_tmp = interval + root;
    int l = 1, r = max_discre, mid;
    while (l < r)
    {
        if (tmp == NULL)
        {
            *last_tmp = tmp = new_node();
            tmp->tot = 1;
        }
        else
        {
            tmp->tot++;
        }
        mid = (l + r) >> 1;
        if (val <= mid)
        {
            last_tmp = &tmp->l_child;
            tmp = tmp->l_child;
            r = mid;
        }
        else
        {
            last_tmp = &tmp->r_child;
            tmp = tmp->r_child;
            l = mid + 1;
        }
    }
    if (tmp == NULL)
    {
        *last_tmp = tmp = new_node();
        tmp->tot = 1;
    }
    else
    {
        tmp->tot++;
    }
}

inline void tree_delete(int root, const int val)
{
    tree_node *tmp = interval[root];
    if (tmp == NULL)
    {
        return;
    }
    tree_node **last_tmp = interval + root;
    int l = 1, r = max_discre, mid;
    while (l < r)
    {
        tmp->tot--;
        if (tmp->tot == 0)
        {
            delete_node(tmp);
            *last_tmp = NULL;
        }
        mid = (l + r) >> 1;
        if (val <= mid)
        {
            last_tmp = &tmp->l_child;
            tmp = tmp->l_child;
            r = mid;
        }
        else
        {
            last_tmp = &tmp->r_child;
            tmp = tmp->r_child;
            l = mid + 1;
        } //我知道这样写不好。。但是不管了
    }
    tmp->tot--;
    if (tmp->tot == 0)
    {
        delete_node(tmp);
        *last_tmp = NULL;
    }
}

inline int tree_left_size(tree_node *query_node)
{
    if (query_node == NULL)
    {
        return 0;
    }
    if (query_node->l_child == NULL)
    {
        return 0;
    }
    return query_node->l_child->tot;
}

inline int lowerbit(const int x)
{
    return x & (-x);
}

inline void interval_insert(int l, const int val)
{
    while (l <= n)
    {
        tree_insert(l, val);
        l += lowerbit(l);
    }
}

inline void interval_delete(int l, const int val)
{
    while (l <= n)
    {
        tree_delete(l, val);
        l += lowerbit(l);
    }
}

tree_node *tmp_add[MAXTMP];
int tot_tmp_add;
tree_node *tmp_minus[MAXTMP];
int tot_tmp_minus;

inline int interval_query(int l, int r, const int k)
{
    tot_tmp_add = tot_tmp_minus = 0;
    while (r > 0)
    {
        tmp_add[tot_tmp_add++] = interval[r];
        r -= lowerbit(r);
    }
    l--;
    while (l > 0)
    {
        tmp_minus[tot_tmp_minus++] = interval[l];
        l -= lowerbit(l);
    }
    int binary_l = 1, binary_r = max_discre, mid, tot_left;
    int tot_length = 0;
    while (binary_l < binary_r)
    {
        mid = (binary_l + binary_r) >> 1;
        tot_left = 0;
        for (int i = 0; i < tot_tmp_add; i++)
        {
            tot_left += tree_left_size(tmp_add[i]);
        }
        for (int i = 0; i < tot_tmp_minus; i++)
        {
            tot_left -= tree_left_size(tmp_minus[i]);
        }
        if (tot_length + tot_left >= k)
        {
            for (int i = 0; i < tot_tmp_minus; i++)
            {
                if (tmp_minus[i] != NULL)
                {
                    tmp_minus[i] = tmp_minus[i]->l_child;
                }
            }
            for (int i = 0; i < tot_tmp_add; i++)
            {
                if (tmp_add[i] != NULL)
                {
                    tmp_add[i] = tmp_add[i]->l_child;
                }
            }
            binary_r = mid;
        }
        else
        {
            for (int i = 0; i < tot_tmp_minus; i++)
            {
                if (tmp_minus[i] != NULL)
                {
                    tmp_minus[i] = tmp_minus[i]->r_child;
                }
            }
            for (int i = 0; i < tot_tmp_add; i++)
            {
                if (tmp_add[i] != NULL)
                {
                    tmp_add[i] = tmp_add[i]->r_child;
                }
            }
            binary_l = mid + 1;
            tot_length += tot_left;
        }
    }
    return binary_l;
}

#ifndef LOCAL_SIMP
int main()
{
#ifdef LOCAL_TIME
    long long start_time_ = clock();
#endif
#ifdef READ_FILE
    freopen("1901.in", "r", stdin);
#ifndef STD_DEBUG
    freopen("1901.out", "w", stdout);
#endif
#endif
#ifdef READ_FREAD
    fread_init();
#endif
    init_recover_tree_node();
    read(n);
    read(m);
    for (int i = 0; i < n; i++)
    {
        read(discre_tmp[i].val);
        discre_tmp[i].id = i;
    }
    tot_discre = n;
    for (int i = 0; i < m; i++)
    {
        read(op_string);
        if (op_string == 'Q')
        {
            op[i] = 1;
            read(op_i[i]);
            read(op_j[i]);
            read(op_k[i]);
        }
        else
        {
            op[i] = 2;
            read(op_i[i]);
            read(discre_tmp[tot_discre].val);
            discre_tmp[tot_discre++].id = n + i;
        }
    }
    std::sort(discre_tmp, discre_tmp + tot_discre);
    max_discre = 0;
    for (int i = 0; i < tot_discre; i++)
    {
        if ((i == 0) || (discre_tmp[i - 1] < discre_tmp[i]))
        {
            discre_to_num[++max_discre] = discre_tmp[i].val;
        }
        if (discre_tmp[i].id < n)
        {
            discre[discre_tmp[i].id] = max_discre;
        }
        else
        {
            op_k[discre_tmp[i].id - n] = max_discre;
        }
    }
    for (int i = 0; i < n; i++)
    {
        interval_insert(i + 1, discre[i]);
    }
    for (int i = 0; i < m; i++)
    {
#ifdef LOCAL_DEBUG
        if (i == 6)
        {
            printf("");
        }
#endif
        if (op[i] == 1)
        {
            printf("%dn", discre_to_num[interval_query(op_i[i], op_j[i], op_k[i])]);
        }
        else if (op[i] == 2)
        {
            interval_delete(op_i[i], discre[op_i[i] - 1]);
            interval_insert(op_i[i], op_k[i]);
            discre[op_i[i] - 1] = op_k[i];
        }
    }
#ifdef LOCAL_TIME
    printf("run time: %lld msn", clock() - start_time_);
#endif
#ifdef READ_FILE
    fclose(stdin);
#ifndef STD_DEBUG
    fclose(stdout);
#endif
#endif
    return 0;
}
#else
int a[MAXN];
int sort_tmp[MAXN];
//int op[MAXN], op_i[MAXN], op_j[MAXN], op_k[MAXN];
int main()
{
    const int N = 5;
    const int M = 10;
    const int RAND_BASE = 234;
    freopen("1901.in", "w", stdout);
    srand(RAND_BASE);
    printf("%d %dn", N, M);
    for (int i = 0; i < N; i++)
    {
        printf("%d ", a[i] = rand());
    }
    printf("n");
    for (int i = 0; i < M; i++)
    {
        op[i] = rand() % 2;
        if (op[i] == 0)
        {
            printf("Q ");
            op_i[i] = rand() % N + 1;
            op_j[i] = op_i[i] + rand() % (N - op_i[i] + 1);
            op_k[i] = rand() % (op_j[i] - op_i[i] + 1) + 1;
            printf("%d %d %dn", op_i[i], op_j[i], op_k[i]);
        }
        else if (op[i] == 1)
        {
            printf("C ");
            op_i[i] = rand() % N + 1;
            op_k[i] = rand();
            printf("%d %dn", op_i[i], op_k[i]);
        }
    }
    fclose(stdout);
    freopen("1901std.out", "w", stdout);
    for (int i = 0; i < M; i++)
    {
        if (op[i] == 1)
        {
            a[op_i[i] - 1] = op_k[i];
        }
        else if (op[i] == 0)
        {
            memcpy(sort_tmp, a + op_i[i] - 1, (op_j[i] - op_i[i] + 1) * sizeof(int));
            std::sort(sort_tmp, sort_tmp + op_j[i] - op_i[i] + 1);
            printf("%dn", sort_tmp[op_k[i] - 1]);
        }
    }
    fclose(stdout);
}
#endif

POJ版（MLE）：

//ZJU 2112.cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>

//#define LOCAL
//#define READ_FILE
#define READ_FREAD
//#define VISUAL_STUDIO

const int MAXN = 50010;
const int MAXM = 10000;
const int MAXTMP = 100;
const int MAXTREE = 3500000;

#ifdef LOCAL
#define LOCAL_TIME
#define LOCAL_DEBUG
//#define STD_DEBUG
//#define LOCAL_SIMP
#endif

#ifdef VISUAL_STUDIO
#pragma warning(disable: 4996)
#endif

#ifdef LOCAL_TIME
#include<ctime>
#endif

#ifdef READ_FREAD
char fread_char;

inline void fread_init()
{
    fread_char = getchar();
}

inline int get_int()
{
    int ret = 0;
    while ((fread_char < '0') || (fread_char > '9'))
    {
        fread_char = getchar();
    }
    while ((fread_char >= '0') && (fread_char <= '9'))
    {
        ret = ret * 10 + fread_char - '0';
        fread_char = getchar();
    }
    return ret;
}

inline char get_char()
{
    while ((fread_char == ' ') || (fread_char == 'n'))
    {
        fread_char = getchar();
    }
    char ret = fread_char;
    fread_char = getchar();
    return ret;
}
#endif

inline void read(int &a)
{
#ifdef READ_FREAD
    a = get_int();
#else
    scanf("%d", &a);
#endif
}

inline void read(char &a)
{
#ifdef READ_FREAD
    a = get_char();
#else
    scanf("%c", &a);
#endif
}

struct discre_node
{
    int val, id;
    inline bool operator < (const discre_node &b) const
    {
        return val < b.val;
    }
};

struct tree_node
{
    int tot;
    tree_node *l_child, *r_child;
    inline tree_node *init()
    {
        l_child = r_child = 0;
        return this;
    }
};

tree_node recover_tree_node[MAXTREE];
tree_node *stack_recover_tree_node[MAXTREE];
int top_stack_recover_tree_node = MAXTREE;

inline void init_recover_tree_node()
{
    for (int i = 0; i < MAXTREE; i++)
    {
        stack_recover_tree_node[i] = recover_tree_node + i;
    }
}

inline tree_node *new_node()
{
    return stack_recover_tree_node[--top_stack_recover_tree_node]->init();
}

inline void delete_node(tree_node *del_node)
{
    stack_recover_tree_node[top_stack_recover_tree_node++] = del_node;
}

int n, m;
discre_node discre_tmp[MAXN + MAXM];
int tot_discre;
int discre_to_num[MAXN + MAXM];
int max_discre;
char op_string;
int discre[MAXN];
int cases;
int op[MAXN], op_i[MAXM], op_j[MAXM], op_k[MAXM];
tree_node *interval[MAXN];

inline void tree_insert(int root, const int val)
{
    tree_node *tmp = interval[root];
    tree_node **last_tmp = interval + root;
    int l = 1, r = max_discre, mid;
    while (l < r)
    {
        if (tmp == NULL)
        {
            *last_tmp = tmp = new_node();
            tmp->tot = 1;
        }
        else
        {
            tmp->tot++;
        }
        mid = (l + r) >> 1;
        if (val <= mid)
        {
            last_tmp = &tmp->l_child;
            tmp = tmp->l_child;
            r = mid;
        }
        else
        {
            last_tmp = &tmp->r_child;
            tmp = tmp->r_child;
            l = mid + 1;
        }
    }
    if (tmp == NULL)
    {
        *last_tmp = tmp = new_node();
        tmp->tot = 1;
    }
    else
    {
        tmp->tot++;
    }
}

inline void tree_delete(int root, const int val)
{
    tree_node *tmp = interval[root];
    if (tmp == NULL)
    {
        return;
    }
    tree_node **last_tmp = interval + root;
    int l = 1, r = max_discre, mid;
    while (l < r)
    {
        tmp->tot--;
        if (tmp->tot == 0)
        {
            delete_node(tmp);
            *last_tmp = NULL;
        }
        mid = (l + r) >> 1;
        if (val <= mid)
        {
            last_tmp = &tmp->l_child;
            tmp = tmp->l_child;
            r = mid;
        }
        else
        {
            last_tmp = &tmp->r_child;
            tmp = tmp->r_child;
            l = mid + 1;
        } //我知道这样写不好。。但是不管了
    }
    if (tmp != NULL)
    {
        tmp->tot--;
        if (tmp->tot == 0)
        {
            delete_node(tmp);
            *last_tmp = NULL;
        }
    }
}

inline int tree_left_size(tree_node *query_node)
{
    if (query_node == NULL)
    {
        return 0;
    }
    if (query_node->l_child == NULL)
    {
        return 0;
    }
    return query_node->l_child->tot;
}

inline int lowerbit(const int x)
{
    return x & (-x);
}

inline void interval_insert(int l, const int val)
{
    while (l <= n)
    {
        tree_insert(l, val);
        l += lowerbit(l);
    }
}

inline void interval_delete(int l, const int val)
{
    while (l <= n)
    {
        tree_delete(l, val);
        l += lowerbit(l);
    }
}

tree_node *tmp_add[MAXTMP];
int tot_tmp_add;
tree_node *tmp_minus[MAXTMP];
int tot_tmp_minus;

inline int interval_query(int l, int r, const int k)
{
    tot_tmp_add = tot_tmp_minus = 0;
    while (r > 0)
    {
        tmp_add[tot_tmp_add++] = interval[r];
        r -= lowerbit(r);
    }
    l--;
    while (l > 0)
    {
        tmp_minus[tot_tmp_minus++] = interval[l];
        l -= lowerbit(l);
    }
    int binary_l = 1, binary_r = max_discre, mid, tot_left;
    int tot_length = 0;
    while (binary_l < binary_r)
    {
        mid = (binary_l + binary_r) >> 1;
        tot_left = 0;
        for (int i = 0; i < tot_tmp_add; i++)
        {
            tot_left += tree_left_size(tmp_add[i]);
        }
        for (int i = 0; i < tot_tmp_minus; i++)
        {
            tot_left -= tree_left_size(tmp_minus[i]);
        }
        if (tot_length + tot_left >= k)
        {
            for (int i = 0; i < tot_tmp_minus; i++)
            {
                if (tmp_minus[i] != NULL)
                {
                    tmp_minus[i] = tmp_minus[i]->l_child;
                }
            }
            for (int i = 0; i < tot_tmp_add; i++)
            {
                if (tmp_add[i] != NULL)
                {
                    tmp_add[i] = tmp_add[i]->l_child;
                }
            }
            binary_r = mid;
        }
        else
        {
            for (int i = 0; i < tot_tmp_minus; i++)
            {
                if (tmp_minus[i] != NULL)
                {
                    tmp_minus[i] = tmp_minus[i]->r_child;
                }
            }
            for (int i = 0; i < tot_tmp_add; i++)
            {
                if (tmp_add[i] != NULL)
                {
                    tmp_add[i] = tmp_add[i]->r_child;
                }
            }
            binary_l = mid + 1;
            tot_length += tot_left;
        }
    }
    return binary_l;
}

#ifndef LOCAL_SIMP
int main()
{
#ifdef LOCAL_TIME
    long long start_time_ = clock();
#endif
#ifdef READ_FILE
    freopen("1901.in", "r", stdin);
#ifndef STD_DEBUG
    freopen("1901.out", "w", stdout);
#endif
#endif
#ifdef READ_FREAD
    fread_init();
#endif
    init_recover_tree_node();
    read(cases);
    while (cases--)
    {
        top_stack_recover_tree_node = MAXTREE;
        init_recover_tree_node();
        memset(interval, 0, sizeof(interval));
        read(n);
        read(m);
        for (int i = 0; i < n; i++)
        {
            read(discre_tmp[i].val);
            discre_tmp[i].id = i;
        }
        tot_discre = n;
        for (int i = 0; i < m; i++)
        {
            read(op_string);
            if (op_string == 'Q')
            {
                op[i] = 1;
                read(op_i[i]);
                read(op_j[i]);
                read(op_k[i]);
            }
            else
            {
                op[i] = 2;
                read(op_i[i]);
                read(discre_tmp[tot_discre].val);
                discre_tmp[tot_discre++].id = n + i;
            }
        }
        std::sort(discre_tmp, discre_tmp + tot_discre);
        max_discre = 0;
        for (int i = 0; i < tot_discre; i++)
        {
            if ((i == 0) || (discre_tmp[i - 1] < discre_tmp[i]))
            {
                discre_to_num[++max_discre] = discre_tmp[i].val;
            }
            if (discre_tmp[i].id < n)
            {
                discre[discre_tmp[i].id] = max_discre;
            }
            else
            {
                op_k[discre_tmp[i].id - n] = max_discre;
            }
        }
        for (int i = 0; i < n; i++)
        {
            interval_insert(i + 1, discre[i]);
        }
        for (int i = 0; i < m; i++)
        {
#ifdef LOCAL_DEBUG
            if (i == 6)
            {
                printf("");
            }
#endif
            if (op[i] == 1)
            {
                printf("%dn", discre_to_num[interval_query(op_i[i], op_j[i], op_k[i])]);
            }
            else if (op[i] == 2)
            {
                interval_delete(op_i[i], discre[op_i[i] - 1]);
                interval_insert(op_i[i], op_k[i]);
                discre[op_i[i] - 1] = op_k[i];
            }
        }
    }
#ifdef LOCAL_TIME
    printf("run time: %lld msn", clock() - start_time_);
#endif
#ifdef READ_FILE
    fclose(stdin);
#ifndef STD_DEBUG
    fclose(stdout);
#endif
#endif
    return 0;
}
#else
int a[MAXN];
int sort_tmp[MAXN];
//int op[MAXN], op_i[MAXN], op_j[MAXN], op_k[MAXN];
int main()
{
    const int N = 50000;
    const int M = 10000;
    const int BASE = 4;
    const int RAND_BASE = 23104;
    freopen("1901.in", "w", stdout);
    srand(RAND_BASE);
    printf("%dn", BASE);
    for (int j = 0; j < BASE; j++)
    {
        printf("%d %dn", N, M);
        for (int i = 0; i < N; i++)
        {
            printf("%d ", a[i] = rand());
        }
        printf("n");
        for (int i = 0; i < M; i++)
        {
            op[i] = rand() % 2;
            if (op[i] == 0)
            {
                printf("Q ");
                op_i[i] = rand() % N + 1;
                op_j[i] = op_i[i] + rand() % (N - op_i[i] + 1);
                op_k[i] = rand() % (op_j[i] - op_i[i] + 1) + 1;
                printf("%d %d %dn", op_i[i], op_j[i], op_k[i]);
            }
            else if (op[i] == 1)
            {
                printf("C ");
                op_i[i] = rand() % N + 1;
                op_k[i] = rand();
                printf("%d %dn", op_i[i], op_k[i]);
            }
        }
    }
    fclose(stdout);
    /*freopen("1901std.out", "w", stdout);
    for (int i = 0; i < M; i++)
    {
        if (op[i] == 1)
        {
            a[op_i[i] - 1] = op_k[i];
        }
        else if (op[i] == 0)
        {
            memcpy(sort_tmp, a + op_i[i] - 1, (op_j[i] - op_i[i] + 1) * sizeof(int));
            std::sort(sort_tmp, sort_tmp + op_j[i] - op_i[i] + 1);
            printf("%dn", sort_tmp[op_k[i] - 1]);
        }
    }
    fclose(stdout);*/
}
#endif

心情好的话再写个分块试试能不能水过。

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Link to this article: https://www.shenxn.io/zoj2112.html