数据结构类题目，赤裸裸的平衡树。
然后我自己写了一个随机函数，经过我自己的测试，用这个函数连续输出10^6个数，其中只有10^3多一点点的数重复次数超过1，有0个数重复次数超过2。所以这是一个不错的随机函数。
![SDOI2008[郁闷的小J]解题报告 - 天之骄子 - 天之骄子的家](https://blog.boleyn.su/wp-content/uploads/2010/07/2283043536101848868.jpg "SDOI2008[郁闷的小J]解题报告 - 天之骄子 - 天之骄子的家")
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-7-27
DESCRIPTION:
山东2008年省选 郁闷的小J
*/
#include <stdio.h>
struct Treap
{
static const int MAXNODE=1000000;
struct struct_node{struct_node* c[1<<1];int p,s,k;};
typedef struct_node* node;
static struct_node pool[MAXNODE];
static node top;
node root,null;
Treap()
{
null=top++;
null->c[0]=null->c[1]=null;
null->p=(~0u)>>1;
null->s=0;
null->k=0;
root=null;
}
int rand()
{
const int a=0x19930309,b=19930309;
static int c,d;
c^=d;
return d=(b*d)+(a^c);
}
void resize(node x)
{
if (x!=null) x->s=x->c[0]->s+x->c[1]->s+1;
}
void rotate(node& x,bool d)
{
node y=x->c[!d];
x->c[!d]=y->c[d];
y->c[d]=x;
resize(x),resize(y);
x=y;
}
void insert(node& x,int k)
{
if (x==null)
{
x=top++;
x->c[0]=x->c[1]=null;
x->p=rand();
x->k=k;
resize(x);
}
else
{
if (x->k==k) return;
bool d=x->k<k;
insert(x->c[d],k);
if (x->c[d]->p<x->p) rotate(x,!d);
else resize(x);
}
}
void remove(node& x,int k)
{
if (x!=null)
{
if (x->k==k)
{
if (x->c[0]==null&&x->c[1]==null) x=null;
else if (x->c[0]==null) x=x->c[1];
else if (x->c[1]==null) x=x->c[0];
else
{
bool d=x->c[0]->p<x->c[1]->p;
rotate(x,d);
remove(x->c[d],k);
}
}
else remove(x->c[x->k<k],k);
resize(x);
}
}
node search(node x,int k)
{
if (x==null) return null;
if (x->k==k) return x;
else return search(x->c[x->k<k],k);
}
node select(node x,int k)
{
if (x==null) return x;
if (x->c[0]->s>=k) return select(x->c[0],k);
k-=x->c[0]->s;
if (k==1) return x;
k-=1;
return select(x->c[1],k);
}
int rank(node x,int k)
{
if (x==null) return 0;
if (k<x->k) return rank(x->c[0],k);
else if (k==x->k) return x->c[0]->s+1;
else return x->c[0]->s+1+rank(x->c[1],k);
}
void for_each(node x,void (*function)(node))
{
if (x==null) return;
for_each(x->c[0],function);
function(x);
for_each(x->c[1],function);
}
void insert(int k)
{
insert(root,k);
}
void remove(int k)
{
remove(root,k);
}
node search(int k)
{
return search(root,k);
}
node select(int k)
{
return select(root,k);
}
int rank(int k)
{
return rank(root,k);
}
void for_each(void (*function)(node))
{
for_each(root,function);
}
};
Treap::struct_node Treap::pool[Treap::MAXNODE];
Treap::node Treap::top=Treap::pool;
const int MAXN=100000+2;
const int MAXM=100000;
typedef Treap::node node;
int N,M;
int a[MAXN];
char order[MAXM];
int A[MAXM],B[MAXM],K[MAXM],P[MAXM];
Treap book;
Treap position[MAXN+MAXM];
void get_id(node x)
{
static int id;
x->s=id++;
}
int main()
{
scanf(“%d%d”,&N,&M);
for (int i=1;i<=N;i++)
scanf(“%d”,a+i);
for (int i=0;i<M;i++)
{
scanf(“\n%c”,&order[i]);
if (order[i]==’C’) scanf(“%d%d”,A+i,P+i);
else scanf(“%d%d%d”,A+i,B+i,K+i);
}
for (int i=1;i<=N;i++)
book.insert(a[i]);
for (int i=0;i<M;i++)
if (order[i]==’C’) book.insert(P[i]);
else book.insert(K[i]);
book.for_each(get_id);
for (int i=1;i<=N;i++)
{
node x=book.search(a[i]);
position[x->s].insert(i);
}
for (int i=0;i<M;i++)
{
if (order[i]==’C’)
{
node x=book.search(a[A[i]]);
position[x->s].remove(A[i]);
node y=book.search(P[i]);
position[y->s].insert(A[i]);
a[A[i]]=P[i];
}
else
{
node x=book.search(K[i]);
printf(“%d\n”,position[x->s].rank(B[i])-position[x->s].rank(A[i]-1));
}
}
}