小J是国家图书馆的一位图书管理员，他的工作是管理一个巨大的书架。虽然他很能吃苦耐劳，但是由于这个书架十分巨大，所以他的工作效率总是很低，以致他面临着被解雇的危险，这也正是他所郁闷的。
具体说来，书架由N个书位组成，编号从1到N。每个书位放着一本书，每本书有一个特定的编码。
小J的工作有两类：
- 图书馆经常购置新书，而书架任意时刻都是满的，所以只得将某位置的书拿掉并换成新购的书。
- 小J需要回答顾客的查询，顾客会询问某一段连续的书位中某一特定编码的书有多少本。
例如，共5个书位，开始时书位上的书编码为1，2，3，4，5
一位顾客询问书位1到书位3中编码为“2”的书共多少本，得到的回答为：1
一位顾客询问书位1到书位3中编码为“1”的书共多少本，得到的回答为：1
此时，图书馆购进一本编码为“1”的书，并将它放到2号书位。
一位顾客询问书位1到书位3中编码为“2”的书共多少本，得到的回答为：0
一位顾客询问书位1到书位3中编码为“1”的书共多少本，得到的回答为：2
……
你的任务是写一个程序来回答每个顾客的询问。
输入
第一行两个整数N，M，表示一共N个书位，M个操作。
接下来一行共N个整数数A1,A2…AN，Ai表示开始时位置i上的书的编码。
接下来M行，每行表示一次操作，每行开头一个字符
若字符为‘C’，表示图书馆购进新书，后接两个整数A(1<=A<=N)，P，表示这本书被放在位置A上，以及这本书的编码为P。
若字符为‘Q’，表示一个顾客的查询，后接三个整数A，B，K(1<=A<=B<=N)，表示查询从第A书位到第Ｂ书位（包含Ａ和Ｂ）中编码为Ｋ的书共多少本。
（1<=N,M<=100000，所有出现的书的编码为不大于2147483647的正数。）
输出
对每一个顾客的查询，输出一个整数，表示顾客所要查询的结果。
这是一道平衡树的题目。只是为了练习一下主席树，顺便写了一下。内存占用比平衡树大多了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1000005
struct node
{
int val,ch[],cnt;
}rec[MAXN<<];
int root[MAXN],num[MAXN],v[MAXN],vsz,tot=,n,m;
struct opt
{
char ops[];
int l,r,k;
}opz[MAXN];
#define lowbit(x) (x&-x)
void insert(int &now,int pos,int l,int r,int flag)//不要last参数了。
{
rec[++tot]=rec[now];
now=tot;
int temp=now;
while(l<r)
{
int mid=(l+r)>>;
if(pos<=mid)
{
rec[++tot]=rec[rec[temp].ch[]];
rec[temp].ch[]=tot;
temp=tot;
r=mid;
}
else
{
rec[++tot]=rec[rec[temp].ch[]];
rec[temp].ch[]=tot;
temp=tot;
l=mid+;
}
}
rec[tot].cnt+=flag;
}
int query(int now,int pos,int l,int r)
{
while(l!=r)
{
int mid=(l+r)>>;
if(pos<=mid)
{
r=mid;
now=rec[now].ch[];
}
else
{
now=rec[now].ch[];
l=mid+;
}
}
return rec[now].cnt;
}
int getans(int x,int pos)
{
int ans=;
while(x>)
{
ans+=query(root[x],pos,,vsz);
x-=lowbit(x);
}
return ans;
}
void upd(int x,int pos,int flag)
{
while(x<=n)
{
insert(root[x],pos,,vsz,flag);
x+=lowbit(x);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
{
scanf("%d",&num[i]);
v[i]=num[i];
}
vsz=n;
for(int i=;i<=m;i++)
{
scanf("%s",opz[i].ops);
if(opz[i].ops[]=='C')
{scanf("%d %d",&opz[i].l,&opz[i].k);
v[vsz++]=opz[i].k;
}
else scanf("%d %d %d",&opz[i].l,&opz[i].r,&opz[i].k);
}
sort(v,v+vsz);
vsz=unique(v,v+vsz)-v;
for(int i=;i<n;i++)
{
int pos=lower_bound(v,v+vsz,num[i])-v+;
upd(i+,pos,);
}
int t1,t2,t3;
for(int i=;i<=m;i++)
{
if(opz[i].ops[]=='C')
{
t1=opz[i].l,t2=num[t1-];
t2=lower_bound(v,v+vsz,t2)-v+;
upd(t1,t2,-);
t2=opz[i].k;
num[t1-]=t2;
t2=lower_bound(v,v+vsz,t2)-v+;
upd(t1,t2,);
}
else
{
t1=opz[i].l,t2=opz[i].r,t3=opz[i].k;
t3=lower_bound(v,v+vsz,t3)-v+;
printf("%d\n",getans(t2,t3)-getans(t1-,t3));
}
}
return ;
}