已经找到错误
by Chlience @ 2018-01-04 22:03:56
你在Q操作时若A==B则会陷入死循环，特判即可@[League丶翎](/space/show?uid=20601)
```cpp
#include <bits/stdc++.h>
using namespace std;
#define inf 21000000
#define maxn 400100
#define mod 400009
int ch[maxn][2],key[maxn],f[maxn],size[maxn],cnt[maxn];
int root[maxn],book[maxn];
int n,m,sz;
int data[maxn];
bool use[maxn];
int read() {
int ans=0,flag=1;
char c=getchar();
while( (c>'9' || c<'0') && c!='-' ) c=getchar();
if(c=='-') flag=-1,c=getchar();
while(c>='0' && c<='9') ans=ans*10+c-'0',c=getchar();
return ans*flag;
}
int hash(int x) {
int now=x%mod;
while(use[now] && data[now]!=x)
now+=17,now%=mod;
use[now]=1;
data[now]=x;
return now;
}
bool get(int x) {return ch[f[x]][1]==x;}
void clear(int x) {ch[x][0]=ch[x][1]=f[x]=size[x]=cnt[x]=key[x]=0;}
void update(int x) {size[x]=cnt[x]+size[ch[x][0]]+size[ch[x][1]];}
void rotate(int x) {
int old=f[x],oldf=f[old],w=get(x);
ch[old][w]=ch[x][w^1],f[ch[old][w]]=old;
ch[x][w^1]=old,f[old]=x;
f[x]=oldf;
if(oldf)
ch[oldf][ch[oldf][1]==old]=x;
update(old);
update(x);
return ;
}
void splay(int w,int x,int tar) {
for(int fa;(fa=f[x])!=tar;rotate(x))
if(f[fa]!=tar)
rotate(get(x)==get(fa)?fa:x);
if(!tar)
root[w]=x;
return ;
}
int find(int w,int x) {
int now=root[w],ans=0;
while(1) {
if(x<key[now])
now=ch[now][0];
else {
ans+=(ch[now][0]?size[ch[now][0]]:0);
if(x==key[now]) {
splay(w,now,0);
return ans+1;
}
ans+=cnt[now];
now=ch[now][1];
}
}
}
int findx(int w,int x) {
int now=root[w];
while(1) {
if(ch[now][0] && x<=size[ch[now][0]])
now=ch[now][0];
else {
int tmp=(ch[now][0]?size[ch[now][0]]:0)+cnt[now];
if(x<=tmp) return now;
x-=tmp;
now=ch[now][1];
}
}
}
void insert(int w,int x) {
if(root[w]==0) {
sz++;
ch[sz][0]=ch[sz][1]=f[sz]=0;
root[w]=sz;
size[sz]=cnt[sz]=1;
key[sz]=x;
return ;
}
int now=root[w],fa=0;
while(1) {
if(x==key[now]) {
cnt[now]++;
update(now);
update(fa);
splay(w,now,0);
return ;
}
fa=now;
now=ch[now][key[now]<x];
if(now==0) {
sz++;
ch[sz][0]=ch[sz][1]=0;
f[sz]=fa;
size[sz]=cnt[sz]=1;
ch[fa][key[fa]<x]=sz;
key[sz]=x;
update(fa);
splay(w,sz,0);
return ;
}
}
}
int pre(int x) {
int now=ch[root[x]][0];
while(ch[now][1]) now=ch[now][1];
return now;
}
void del(int a) {
if(cnt[root[a]]>1) {
cnt[root[a]]--;
update(root[a]);
return ;
}
if(!ch[root[a]][0] && !ch[root[a]][1]) {
clear(root[a]);
root[a]=0;
return ;
}
if(!ch[root[a]][0]) {
int oldroot=root[a];
root[a]=ch[root[a]][1];
f[root[a]]=0;
clear(oldroot);
return ;
}
else if(!ch[root[a]][1]) {
int oldroot=root[a];
root[a]=ch[root[a]][0];
f[root[a]]=0;
clear(oldroot);
return ;
}
int leftbig=pre(a),oldroot=root[a];
splay(a,leftbig,0);
ch[root[a]][1]=ch[oldroot][1];
f[ch[oldroot][1]]=root[a];
clear(oldroot);
update(root[a]);
return ;
}
void Q() {
int a=read(),b=read(),k=hash(read());
if(!root[k]) {
printf("0\n");
return ;
}
insert(k,a);
int A=root[k];
insert(k,b);
int B=root[k];
splay(k,A,0);
if(A==B) {
int ans=cnt[A]-2;
printf("%d\n",ans);
}
else {
splay(k,B,A);
int ans=cnt[A]+cnt[B]+size[ch[B][0]]-2;
printf("%d\n",ans);
}
del(k);
splay(k,B,0);
del(k);
return ;
}
int main() {
n=read(),m=read();
for(int i=1;i<=n;i++) {
int k=hash(read());
book[i]=k;
insert(k,i);
}
for(int i=1;i<=m;i++) {
char str[10];
scanf("%s",str);
if(str[0]=='C') {
int a=read(),k=hash(read());
find(book[a],a);
del(book[a]);
book[a]=k;
insert(k,a);
}
else {
Q();
}
}
return 0;
}
```
by Chlience @ 2018-01-04 22:05:26
谢谢@[Chlience](/space/show?uid=65439)
by League丶翎 @ 2018-01-04 22:06:29