BZOJ3065: 带插入区间K小值
树套树 工业 替罪羊树 Trie树    2017-01-06 12:43:39    292    1    0

3065: 带插入区间K小值

Time Limit: 60 Sec  Memory Limit: 512 MB
Submit: 2857  Solved: 881
[Submit][Status][Discuss]

Description

从前有n只跳蚤排成一行做早操,每只跳蚤都有自己的一个弹跳力a[i]。跳蚤国王看着这些跳蚤国欣欣向荣的情景,感到非常高兴。这时跳蚤国王决定理性愉悦一下,查询区间k小值。他每次向它的随从伏特提出这样的问题: 从左往右第x个到第y个跳蚤中,a[i]第k小的值是多少。
这可难不倒伏特,他在脑袋里使用函数式线段树前缀和的方法水掉了跳蚤国王的询问。
这时伏特发现有些跳蚤跳久了弹跳力会有变化,有的会增大,有的会减少。
这可难不倒伏特,他在脑袋里使用树状数组套线段树的方法水掉了跳蚤国王的询问。(orz 主席树)
这时伏特发现有些迟到的跳蚤会插入到这一行的某个位置上,他感到非常生气,因为……他不会做了。
请你帮一帮伏特吧。
快捷版题意:带插入、修改的区间k小值在线查询。

 

Input

第一行一个正整数n,表示原来有n只跳蚤排成一行做早操。
第二行有n个用空格隔开的非负整数,从左至右代表每只跳蚤的弹跳力。
第三行一个正整数q,表示下面有多少个操作。
下面一共q行,一共三种操作对原序列的操作:(假设此时一共m只跳蚤)
1. Q x y k: 询问从左至右第x只跳蚤到从左至右第y只跳蚤中,弹跳力第k小的跳蚤的弹跳力是多少。
    (1 <= x <= y <= m, 1 <= k <= y - x + 1)
2. M x val: 将从左至右第x只跳蚤的弹跳力改为val。
    (1 <= x <= m)
3. I x val: 在从左至右第x只跳蚤的前面插入一只弹跳力为val的跳蚤。即插入后从左至右第x只跳蚤是我刚插入的跳蚤。
    (1 <= x <= m + 1)

为了体现在线操作,设lastAns为上一次查询的时候程序输出的结果,如果之前没有查询过,则lastAns = 0。
则输入的时候实际是:
Q _x _y _k ------> 表示 Q _x^lastAns _y^lastAns _k^lastAns
M _x _val  ------> 表示 M _x^lastAns _val^lastAns
I _x _val  ------> 表示 I _x^lastAns _val^lastAns
简单来说就是操作中输入的整数都要异或上一次询问的结果进行解码。

(祝Pascal的同学早日转C++,就不提供pascal版的描述了。)

 

Output

对于每个询问输出回答,每行一个回答。

 

Solution

千万不要在不清醒的时候码工业题T_T

被数组越界坑飞了。。编译器连warning都不给。。直接访问到了其他数组。。

调一天系列

 

替罪羊树套Trie

询问的时候先把每层的节点记录下来,和线段树一样,每层的节点数是O(1)级别的,然后把这些节点一起二分

 

会爆内存,要垃圾回收

 

Source code

/*{{{*/
//#pragma GCC optimize("O3")

#include <bits/stdc++.h>

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

typedef long long ll;
typedef std::pair<int, int> pii;

std::string Name = __FILE__;
std::string iput = Name.substr(0, Name.length() - 4) + ".in";
std::string oput = Name.substr(0, Name.length() - 4) + ".out";

template <class T> inline bool chkmin(T &x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T &x, T y) { return x < y ? x = y, true : false; }

template <class T> inline T &read(T &x)
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) {
        if (c == '-')
            f = -1;
    }
    for (x = 0; isdigit(c); c = getchar()) {
        x = x * 10 + c - 48;
    }
    return x *= f;
}

template <class T> inline void write(T x, const char p = '\n')
{
    static int top;
    static int s[30];
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    do s[++ top] = x % 10 + 48;
    while (x /= 10);
    while (top)
        putchar(s[top --]);
    putchar(p);
}
/*}}}*/
 
const int maxn = 70000 + 5;
const int Log = 16;
const int maxsize = 1e7;

struct Node { int l, r, size; } node[maxsize];

int a[maxn];

namespace ScapegoatTree
{
    int root;
    int val[maxsize];
    int Root[maxsize];

    std::queue<int> memory;

    inline int newnode()
    {
    	static int tot;
    	if (memory.empty())
            return ++ tot;
        else {
            int it = memory.front();
            memory.pop();
            return it;
        }
    }

    void insert(int &x, int v, int t = Log)
    {
        if (!x) x = newnode();
        ++ node[x].size;
        if (t == -1) return;
        if (v & (1 << t))
            insert(node[x].r, v, t - 1);
        else
            insert(node[x].l, v, t - 1);
    }

    void Delete(int &x, int v, int t = Log)
    {
        if (t != -1) {
            if (v & (1 << t))
                Delete(node[x].r, v, t - 1);
            else
                Delete(node[x].l, v, t - 1);
        }
        if (-- node[x].size == 0) {
            memory.push(x);
            x = 0;
        }
    }

    void build(int &x, int l, int r)
    {
        if (l > r) return;
        x = newnode();
        node[x].size = r - l + 1;
        for (int i = l; i <= r; ++ i) {
            insert(Root[x], a[i]);
        }
        int mid = (l + r) >> 1;
        val[x] = a[mid];
        build(node[x].l, l, mid - 1);
        build(node[x].r, mid + 1, r);
    }

    void Modify(int x, int v)
    {
        int top = 0;
        int now = root;
        static int s[maxn];

        for (; ; ) {
            s[++ top] = now;
            int lsize = node[node[now].l].size;
            if (x <= lsize)
                now = node[now].l;
            else if (x == lsize + 1)
                break;
            else
                now = node[now].r, x -= lsize + 1;
        }

        for (int i = 1; i <= top; ++ i) {
            insert(Root[s[i]], v);
            Delete(Root[s[i]], val[now]);
        }

        val[now] = v;
    }

    void DFS2(int x)
    {
        if (node[x].l) DFS2(node[x].l), node[x].l = 0;
        if (node[x].r) DFS2(node[x].r), node[x].r = 0;
        node[x].size = 0;
        memory.push(x);
    }

    int TOP;

    void DFS(int x)
    {
        if (node[x].l) DFS(node[x].l);
        a[++ TOP] = val[x];
        if (node[x].r) DFS(node[x].r);
        //Delete
        node[x] = (Node){0, 0, 0};
        memory.push(x);
        DFS2(Root[x]);
        Root[x] = 0;
    }

    void rebuild(int &x)
    {
        TOP = 0;
        DFS(x);
        build(x, 1, TOP);
    }

    const double delta = 0.8;

    void Insert(int x, int v)
    {
        int top = 0;
        int now = root;
        static int s[maxn];

        for (; ; ) {
            s[++ top] = now;
            int lsize = node[node[now].l].size;
            if (x <= lsize) {
                if (node[now].l == 0) {
                    node[now].l = newnode();
                    now = node[now].l;
                    s[++ top] = now;
                    break;
                }
                now = node[now].l;
            } else {
                x -= lsize + 1;
                if (node[now].r == 0) {
                    node[now].r = newnode();
                    now = node[now].r;
                    s[++ top] = now;
                    break;
                }
                now = node[now].r;
            }
        }

        for (int i = top; i; -- i) {
            ++ node[s[i]].size;
            insert(Root[s[i]], v);
        }

        val[now] = v;

        //rebuild
        for (int i = 1; i <= top; ++ i) {
        	if (node[node[s[i]].l].size > delta * node[s[i]].size || node[node[s[i]].r].size > delta * node[s[i]].size) {
        		if (i == 1)
        			rebuild(root);
        		else {
        			int father = s[i - 1];
        			if (node[father].l == s[i])
        				rebuild(node[father].l);
        			else
        			    rebuild(node[father].r);
        		}
        		break;
        	}
        }

    }

    int stack[maxn], top;    // +
    int stack2[maxn], top2;  // -

    void getl(int x, int r)
    {
        if (r == 0) return;
        if (node[x].size <= r) {
            stack2[++ top2] = Root[x];
            return;
        }

        int lsize = node[node[x].l].size;

        if (r <= lsize) {
            getl(node[x].l, r);
        } else {
            stack2[++ top2] = Root[x];
            if (node[x].r) 
                stack[++ top] = Root[node[x].r];
            getl(node[x].r, r - lsize - 1);
        }
    }

    void getr(int x, int r)
    {
        if (r == 0) return;
        if (node[x].size <= r) {
            stack[++ top] = Root[x];
            return;
        }

        int lsize = node[node[x].l].size;

        if (r <= lsize) {
            getr(node[x].l, r);
        } else {
            stack[++ top] = Root[x];
            if (node[x].r)
                stack2[++ top2] = Root[node[x].r];
            getr(node[x].r, r - lsize - 1);
        }
    }

    int query(int l, int r, int k)
    {
        top = top2 = 0;
        getl(root, l - 1);
        getr(root, r);
        int t = Log, ret = 0;
        while (~t) {
            int size = 0;

            for (int i = 1; i <= top; ++ i)
                size += node[node[stack[i]].l].size;
            for (int i = 1; i <= top2; ++ i)
                size -= node[node[stack2[i]].l].size;

            if (k <= size) {
                for (int i = 1; i <= top; ++ i)
                    stack[i] = node[stack[i]].l;
                for (int i = 1; i <= top2; ++ i)
                    stack2[i] = node[stack2[i]].l;
            } else {
                k -= size;
                ret |= (1 << t);
                for (int i = 1; i <= top; ++ i)
                    stack[i] = node[stack[i]].r;
                for (int i = 1; i <= top2; ++ i)
                    stack2[i] = node[stack2[i]].r;
            }
            -- t;
        }
        return ret;
    }

}

int n;
int q;

void exec()
{
    read(n);
    for (int i = 1; i <= n; ++ i) {
        read(a[i]);
    }

    ScapegoatTree::build(ScapegoatTree::root, 1, n);

    int ans = 0;

    read(q);
    while (q --) {
        static char s[100];
        static int x, y, v;
        scanf("%s", s);
        if (s[0] == 'Q') {
            read(x), read(y), read(v);
            x ^= ans; y ^= ans; v ^= ans;
            ans = ScapegoatTree::query(x, y, v);
            write(ans);
        } else if (s[0] == 'M') {
            read(x), read(v);
            x ^= ans; v ^= ans;
            ScapegoatTree::Modify(x, v);
        } else {
            read(x), read(v);
            x ^= ans; v ^= ans;
            ScapegoatTree::Insert(x - 1, v);
        }
    }
}

/*{{{*/
int main() 
{
    if (fopen(iput.c_str(), "r") != NULL) {
        freopen(iput.c_str(), "r", stdin);
        freopen(oput.c_str(), "w", stdout);
    }

    exec();

    fclose(stdin);
    fclose(stdout);

    return 0;
}
/*}}}*/

 

一般图最大匹配
292 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航