ZOJ2112 有点大材小用了。 替罪羊树套splay的话，可以在线搞，而且支持插入删除等操作。 本题只有查询和修改操作。 完全可以把替罪羊树换成树状数组或者线段树了。 其实这里用替罪羊树，也没啥作用，重构操作都没有。就是当成线段树用的。 比较容易MLE。
Dynamic Rankings
Time Limit: 10 Seconds Memory Limit: 32768 KB
The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], …, a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], …, a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same. Your task is to write a program for this computer, which - Reads N numbers from the input (1 <= N <= 50,000) - Processes M instructions of the input (1 <= M <= 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], …, a[j] and change some a[i] to t. Input The first line of the input is a single number X (0 < X <= 4), the number of the test cases of the input. Then X blocks each represent a single test case. The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format Q i j k or C i t It represents to query the k-th number of a[i], a[i+1], …, a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000. There’re NO breakline between two continuous test cases. Output For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],…, a[j]) There’re NO breakline between two continuous test cases. Sample Input 2 5 3 3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3 5 3 3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3 Sample Output 3 6 3 6
/* ***
Author :kuangbin
Created Time :2014/10/2 8:59:47
File Name :ZOJ2112.cpp
************************************************ */
#include <stdio.h>
#include <string.h>
#include
#include
#include
#include
#include
#include
#include
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
using namespace std;
const int MAXN = 50010;
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\15],*tail;
Node bc[MAXN];
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
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
if(l == r)return null;
int mid = (l+r)/2;
Node
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
Travel(p,v);
p = divide(v,0,v.size());
}
//将第id个值修改为val
int Modify(Node
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 = 1000000000;
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;
}
void debug(Node p){
if(p == null)return;
debug(p->ch[0]);
printf(“%d key %d lc %d rc %d size %d\n”,p-pool,p->key,p->ch[0]-pool,p->ch[1]-pool,p->root->size);
debug(p->ch[1]);
}
};
int a[MAXN];
int main()
{
int T;
int n,m;
scanf(“%d”,&T);
while(T–){
scanf(“%d%d”,&n,&m);
Splay::init();
ScapeGoatTree::init();
for(int i = 0;i < n;i++)scanf(“%d”,&a[i]);
ScapeGoatTree::root = ScapeGoatTree::buildTree(a,0,n);
//ScapeGoatTree::debug(ScapeGoatTree::root);
char op[10];
while(m–){
scanf(“%s”,op);
if(op[0] == ‘Q’){
int x,y,k;
scanf(“%d%d%d”,&x,&y,&k);
int ans = ScapeGoatTree::query(x,y,k);
printf(“%d\n”,ans);
}
else if(op[0] == ‘C’){
int x,val;
scanf(“%d%d”,&x,&val);
ScapeGoatTree::Modify(ScapeGoatTree::root,x,val);
}
}
}
return 0;
}
