BZOJ 3065 带插入区间K小值 （替罪羊树套splay）

BZOJ3065 带插入、修改的区间k小值在线查询。 网上看的别人的做法确实没看懂， 然后自己想了一下，用替罪羊树套上splay去搞。 替罪羊树维护相对位置信息，然后每个子树用splay去维护值。 这样就可以查询一个区间 <= val的出现了几次。 替罪羊树重要的是不会旋转，维护起来很好维护。 就是代码比较长了，splay+替罪羊， 300+行代码， 1A了，怕不怕！

3065: 带插入区间K小值

Time Limit: 60 Sec Memory Limit: 512 MB Submit: 810 Solved: 184 [Submit][Status]

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

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

Sample Input

10 10 5 8 28 0 19 2 31 1 22 30 I 6 9 M 1 11 I 8 17 M 1 31 M 6 26 Q 2 7 6 I 23 30 M 31 7 I 22 27 M 26 18 Q 26 17 31 I 5 2 I 18 13 Q 3 3 3 I 27 19 Q 23 23 30 Q 5 13 5 I 3 0 M 15 27 Q 0 28 13 Q 3 29 11 M 2 8 Q 12 5 7 I 30 19 M 11 19 Q 17 8 29 M 29 4 Q 3 0 12 I 7 18 M 29 27

Sample Output

28 2 31 0 14 15 14 27 15 14

HINT

此题作为一个小小的研究来搞吧～做法有很多～不知道这题究竟有多少种做法。 请自觉O(log^2n)，我故意卡块状链表，块链A了的请受我深情一拜…… A掉的同学请在Discuss里面简要说下自己的做法吧～ 原序列长度 <= 35000 插入个数 <= 35000，修改个数 <= 70000，查询个数 <= 70000 ,0 <= 每时每刻的权值 <= 70000 由于是OJ上的题，所以数据无梯度。为了防止卡OJ，本题只有4组数据。

Source

作者 vfleaking

题目限定值的范围是 0~70000.  我用splay的做法的话，这个值的范围可以很大了。

/* ***************

Author        :kuangbin

Created Time  :2014/10/1 22:05:45

File Name     :E:\2014ACM\专题学习\数据结构\ScapeGoatTree\BZOJ3065.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 70010;

namespace Splay{

	struct Node *null;

	struct Node{

		Node *ch[2],*fa;

		int size,key,cnt;

		inline void setc(Node *p,int d){

			ch[d] = p;

			p->fa = this;

		}

		inline bool d(){

			return fa->ch[1] == this;

		}

		inline void push_up(){

			size = ch[0]->size + ch[1]->size + cnt;

		}

		void clear(int _key){

			size = cnt = 1;

			key = _key;

			ch[0] = ch[1] = fa = null;

		}

		inline bool isroot(){

			return fa == null || this != fa->ch[0] && this != fa->ch[1];

		}

	};

	Node pool[MAXN*20],*tail;

	Node *bc[MAXN*20];

	int bc_top;//内存回收

	void init(){

		tail = pool;

		bc_top = 0;

		null = tail++;

		null->size = null->cnt = 0;

		null->ch[0] = null->ch[1] = null->fa = null;

	}

	inline void rotate(Node *x){

		Node *f = x->fa, *ff = x->fa->fa;

		int c = x->d(), cc = f->d();

		f->setc(x->ch[!c],c);

		x->setc(f,!c);

		if(ff->ch[cc] == f)ff->setc(x,cc);

		else x->fa = ff;

		f->push_up();

	}

	inline void splay(Node* &root,Node* x,Node* goal){

		while(x->fa != goal){

			if(x->fa->fa == goal)rotate(x);

			else {

				bool f = x->fa->d();

				x->d() == f ? rotate(x->fa) : rotate(x);

				rotate(x);

			}

		}

		x->push_up();

		if(goal == null)root = x;

	}

	//找到r子树里面的最左边那个

	Node* get_left(Node* r){

		Node* x = r;

		while(x->ch[0] != null)x = x->ch[0];

		return x;

	}

	//在root的树中删掉x

	void erase(Node* &root,Node* x){

		splay(root,x,null);

		Node* t = root;

		if(t->ch[1] != null){

			root = t->ch[1];

			splay(root,get_left(t->ch[1]),null);

			root->setc(t->ch[0],0);

		}

		else root = root->ch[0];

		bc[bc_top++] = x;

		root->fa = null;

		if(root != null)root->push_up();

	}

	Node* newNode(int key){

		Node* p;

		if(bc_top)p = bc[--bc_top];

		else p = tail++;

		p->clear(key);

		return p;

	}

	//插入一个值key

	void insert(Node* &root,int key){

		if(root == null){

			root = newNode(key);

			return;

		}

		Node* now = root;

		Node* pre = root->fa;

		while(now != null){

			if(now->key == key){

				now->cnt++;

				splay(root,now,null);

				return;

			}

			pre = now;

			now = now->ch[key >= now->key];

		}

		Node *x = newNode(key);

		pre->setc(x,key >= pre->key);

		splay(root,x,null);

	}

	//删除一个值key

	void erase(Node* &root,int key){

		Node* now = root;

		while(now->key != key){

			now = now->ch[key >= now->key];

		}

		now->cnt--;

		if(now->cnt == 0)erase(root,now);

		else splay(root,now,null);

	}

	void Travel(Node* r){

		if(r == null)return;

		Travel(r->ch[0]);

		bc[bc_top++] = r;

		Travel(r->ch[1]);

	}

	void CLEAR(Node* &root){

		Travel(root);

		root = null;

	}

	//查询小于等于val的个数

	int query(Node *root,int val){

		int ans = 0;

		Node *x = root;

		while(x != null){

			if(val < x->key)x = x->ch[0];

			else{

				ans += x->ch[0]->size + x->cnt;

				x = x->ch[1];

			}

		}

		return ans;

	}

};

namespace ScapeGoatTree{

	const double alpha = 0.75;

	struct Node{

		Node *ch[2];

		int size,nodeCount,key;

		Splay::Node *root;

		bool isBad(){

			return ch[0]->nodeCount > alpha*nodeCount+5 || ch[1]->nodeCount > alpha*nodeCount+5;

		}

		void push_up(){

			size = 1+ch[0]->size+ch[1]->size;

			nodeCount = 1+ch[0]->nodeCount+ch[1]->nodeCount;

		}

	};

	Node pool[MAXN];

	Node *tail,*root,*null;

	Node *bc[MAXN];

	int bc_top;

	void init(){

		tail = pool;

		null = tail++;

		null->ch[0] = null->ch[1] = null;

		null->size = null->nodeCount = 0;

		null->root = Splay::null;

		bc_top = 0;

	}

	inline Node* newNode(int key){

		Node *p;

		if(bc_top)p = bc[--bc_top];

		else p = tail++;

		p->key = key;

		p->ch[0] = p->ch[1] = null;

		p->size = p->nodeCount = 1;

		p->root = Splay::null;

		return p;

	}

	Node *buildTree(int *a,int l,int r){

		if(l >= r)return null;

		int mid = (l+r)/2;

		Node *p = newNode(a[mid]);

		for(int i = l;i < r;i++)

			Splay::insert(p->root,a[i]);

		p->ch[0] = buildTree(a,l,mid);

		p->ch[1] = buildTree(a,mid+1,r);

		p->push_up();

		return p;

	}

	void Travel(Node *p,vector<int>&v){

		if(p == null)return;

		Travel(p->ch[0],v);

		v.push_back(p->key);

		Splay::CLEAR(p->root);

		bc[bc_top++] = p;

		Travel(p->ch[1],v);

	}

	Node *divide(vector<int>&v,int l,int r){

		if(l == r)return null;

		int mid = (l+r)/2;

		Node *p = newNode(v[mid]);

		for(int i = l;i < r;i++)

			Splay::insert(p->root,v[i]);

		p->ch[0] = divide(v,l,mid);

		p->ch[1] = divide(v,mid+1,r);

		p->push_up();

		return p;

	}

	inline void rebuild(Node *&p){

		vector<int>v;

		Travel(p,v);

		p = divide(v,0,v.size());

	}

	//将第id个值修改为val

	int Modify(Node *p,int id,int val){

		if(id == p->ch[0]->size+1){

			int v = p->key;

			Splay::erase(p->root,v);

			Splay::insert(p->root,val);

			p->key = val;

			return v;

		}

		int res;

		if(p->ch[0]->size >= id)

			res = Modify(p->ch[0],id,val);

		else res = Modify(p->ch[1],id-p->ch[0]->size-1,val);

		Splay::erase(p->root,res);

		Splay::insert(p->root,val);

		return res;

	}

	Node **insert(Node *&p,int id,int val){

		if(p == null){

			p = newNode(val);

			Splay::insert(p->root,val);

			return &null;

		}

		else {

			p->size++;

			p->nodeCount++;

			Splay::insert(p->root,val);

			Node ** res;

			if(id <= p->ch[0]->size+1)

				res = insert(p->ch[0],id,val);

			else res = insert(p->ch[1],id-p->ch[0]->size-1,val);

			if(p->isBad())res = &p;

			return res;

		}

	}

	void insert(int id,int val){

		Node **p = insert(root,id,val);

		if(*p != null)rebuild(*p);

	}

	//查询在[l,r]区间，值小于等于val的个数

	int query(Node *p,int l,int r,int val){

		if(p == null)return 0;

		if(l <= 1 && p->size <= r)

			return Splay::query(p->root,val);

		else {

			int ans = 0;

			if(l <= p->ch[0]->size)

				ans += query(p->ch[0],l,r,val);

			if(r > p->ch[0]->size+1)

				ans += query(p->ch[1],l-p->ch[0]->size-1,r-p->ch[0]->size-1,val);

			if(p->key <= val && l <= p->ch[0]->size+1 && p->ch[0]->size+1 <= r)

				ans++;

			return ans;

		}

	}

	int query(int L,int R,int k){

		int ans;

		int l = 0, r = 100000;

		while(l <= r){

			int mid = (l+r)/2;

			if(query(root,L,R,mid) >= k){

				ans = mid;

				r = mid-1;

			}

			else l = mid+1;

		}

		return ans;

	}

};

int a[MAXN];

int main()

{

    int n;

	while(scanf("%d",&n) == 1){

		Splay::init();

		ScapeGoatTree::init();

		for(int i = 0;i < n;i++)scanf("%d",&a[i]);

		ScapeGoatTree::root = ScapeGoatTree::buildTree(a,0,n);

		int m;

		char op[10];

		scanf("%d",&m);

		int ans = 0;

		while(m--){

			scanf("%s",op);

			if(op[0] == 'Q'){

				int x,y,k;

				scanf("%d%d%d",&x,&y,&k);

				x ^= ans; y ^= ans; k ^= ans;

				ans = ScapeGoatTree::query(x,y,k);

				printf("%d\n",ans);

			}

			else if(op[0] == 'M'){

				int x,val;

				scanf("%d%d",&x,&val);

				x ^= ans; val ^= ans;

				ScapeGoatTree::Modify(ScapeGoatTree::root,x,val);

			}

			else if(op[0] == 'I'){

				int x,val;

				scanf("%d%d",&x,&val);

				x ^= ans; val ^= ans;

				ScapeGoatTree::insert(x,val);

			}

		}

	}

    return 0;

}