| 记录编号 |
366845 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
黑白树的操作 |
最终得分 |
100 |
| 用户昵称 |
 AntiLeaf |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
25.775 s |
| 提交时间 |
2017-01-26 09:15:45 |
内存使用 |
198.12 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int maxn=100010;
const double alpha=0.7;
void link(int,int,int);
void modify(int);
long long query(int);
void dfs_merge(int,int,int);
void addnode(int,int);
void rebuild(int,int,int);
void dfs_getcenter(int,int,int&);
void dfs_getdis(int,int,int);
void dfs_destroy(int,int);
vector<int>G[maxn],W[maxn];
int size[maxn]={0},son[maxn],siz[maxn][50];
int depth[maxn]={0},p[maxn]={0},d[maxn][50]={0},id[maxn][50]={0},ca[maxn]={0},cb[maxn][50]={{0}};
long long a[maxn]={0},b[maxn][50]={{0}},ans=0;
bool vis[maxn]={false},col[maxn]={false};
int n,m,x,y,z;
char c;
signed main(){
freopen("MD5.in","r",stdin);
freopen("MD5.out","w",stdout);
int __size__=256<<20;
char *__p__=(char*)malloc(__size__)+__size__;
__asm__("movl %0, %%esp\n"::"r"(__p__));
scanf("%lld%lld",&n,&m);
fill(vis,vis+n+1,true);
while(m--){
ans%=n;
if(ans<0)ans+=n;
scanf(" %c%lld",&c,&x);
x^=ans;
if(c=='A'){
scanf("%lld%lld",&y,&z);
y^=ans;z^=ans;
link(x,y,z);
}
else if(c=='C')modify(x);
else if(c=='Q')printf("%lld\n",ans=query(x));
}
return 0;
}
void link(int x,int y,int z){
G[x].push_back(y);
W[x].push_back(z);
G[y].push_back(x);
W[y].push_back(z);
int rx=x,ry=y;
while(p[rx])rx=p[rx];
while(p[ry])ry=p[ry];
if(size[rx]<size[ry]){
swap(rx,ry);
swap(x,y);
}
p[y]=x;
dfs_merge(y,z,x);
}
void modify(int x){
if(col[x])ca[x]--;
else ca[x]++;
for(int u=p[x],k=depth[x]-1;u;u=p[u],k--){//printf("u=%d k=%d id[x][k]=%d d[x][k]=%d\n",u,k,id[x][k],d[x][k]);
if(col[x]){
a[u]-=d[x][k];
b[id[x][k]][k]-=d[x][k];
ca[u]--;
cb[id[x][k]][k]--;
}
else{
a[u]+=d[x][k];
b[id[x][k]][k]+=d[x][k];
ca[u]++;
cb[id[x][k]][k]++;
}//printf("u=%d k=%d a[u]=%d b[id[x][k]][k]=%d ca[u]=%d cb[id[x][k]][k]=%d id[x][k]=%d d[x][k]=%d\n",u,k,(int)a[u],(int)b[id[x][k]][k],ca[u],cb[id[x][k]][k],id[x][k],d[x][k]);
}
col[x]^=true;
}
long long query(int x){
long long ans=a[x];//printf("a[x]=%lld\n",a[x]);
for(int u=p[x],k=depth[x]-1;u;u=p[u],k--){
ans+=a[u]-b[id[x][k]][k]+(ca[u]-cb[id[x][k]][k])*d[x][k];
//printf("u=%d k=%d a[u]=%d b[id[x][k]][k]=%d ca[u]=%d cb[id[x][k]][k]=%d id[x][k]=%d d[x][k]=%d\n",u,k,(int)a[u],(int)b[id[x][k]][k],ca[u],cb[id[x][k]][k],id[x][k],d[x][k]);
}
return ans;
}
void dfs_merge(int x,int z,int pr){//printf("dfs_merge(%d,%d,%d)\n",x,z,pr);
for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=pr)depth[G[x][i]]=-1;
addnode(x,z);//printf("p[x]=%d\n",p[x]);
for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=pr)dfs_merge(G[x][i],W[x][i],p[G[x][i]]=x);
}
void addnode(int x,int z){//printf("x=%d z=%d p[x]=%d\n",x,z,p[x]);
memset(id[x],0,sizeof(id[x]));
size[x]=1;
ca[x]=col[x];
depth[x]=depth[p[x]]+1;
a[x]=0;
memset(b[x],0,sizeof(b[x]));
memset(cb[x],0,sizeof(cb[x]));
memset(siz[x],0,sizeof(siz[x]));
int rt=0;
for(int u=p[x],k=depth[p[x]];u;u=p[u],k--){
if(u==p[x]){
id[x][k]=x;
d[x][k]=z;
}
else{
id[x][k]=id[p[x]][k];
d[x][k]=d[p[x]][k]+z;
}//printf("u=%d k=%d id[x][k]=%d d[x][k]=%d\n",u,k,id[x][k],d[x][k]);
if(col[x]){
a[u]+=d[x][k];
b[id[x][k]][k]+=d[x][k];
ca[u]++;cb[id[x][k]][k]++;
}
size[u]++;
siz[id[x][k]][k]++;
if(siz[id[x][k]][k]>size[u]*alpha+5)rt=u;
//printf("u=%d k=%d a[u]=%d b[id[x][k]][k]=%d ca[u]=%d cb[id[x][k]][k]=%d id[x][k]=%d d[x][k]=%d\n",u,k,(int)a[u],(int)b[id[x][k]][k],ca[u],cb[id[x][k]][k],id[x][k],d[x][k]);
}
if(rt){//printf("%d needs rebuild\n",rt);
dfs_destroy(rt,depth[rt]);
rebuild(rt,size[rt],p[rt]);
}
}
void rebuild(int x,int s,int pr){
int u=0;
dfs_getcenter(x,s,u);
vis[x=u]=true;
p[x]=pr;
depth[x]=depth[p[x]]+1;
size[x]=s;
ca[x]=col[x];
a[x]=0;//printf("rebuild(%d,%d,%d)\ndepth[x]=%d\n",x,s,pr,depth[x]);
for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
p[G[x][i]]=x;
d[G[x][i]][depth[x]]=W[x][i];
b[G[x][i]][depth[x]]=cb[G[x][i]][depth[x]]=siz[G[x][i]][depth[x]]=0;
dfs_getdis(G[x][i],G[x][i],depth[x]);
a[x]+=b[G[x][i]][depth[x]];
ca[x]+=cb[G[x][i]][depth[x]];
}
for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]])rebuild(G[x][i],siz[G[x][i]][depth[x]],x);
}
void dfs_getcenter(int x,int s,int &u){
size[x]=1;
son[x]=0;
for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&G[x][i]!=p[x]){
p[G[x][i]]=x;
dfs_getcenter(G[x][i],s,u);
size[x]+=size[G[x][i]];
if(size[G[x][i]]>size[son[x]])son[x]=G[x][i];
}
if(!u||max(s-size[x],size[son[x]])<max(s-size[u],size[son[u]]))u=x;
}
void dfs_getdis(int x,int rt,int k){
cb[rt][k]+=col[x];
if(col[x])b[rt][k]+=d[x][k];
siz[rt][k]++;
id[x][k]=rt;
for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&G[x][i]!=p[x]){
p[G[x][i]]=x;
d[G[x][i]][k]=d[x][k]+W[x][i];
dfs_getdis(G[x][i],rt,k);
}
}
void dfs_destroy(int x,int k){
vis[x]=false;//printf("dfs_destroy(%d,%d)\n",x,k);
for(int i=0;i<(int)G[x].size();i++)if(depth[G[x][i]]>=k&&G[x][i]!=p[x]){
p[G[x][i]]=x;
dfs_destroy(G[x][i],k);
}
}
/*
连接两个点可以启发式合并，类似紫荆花之恋的做法，
把小的那个逐个加入大的点分治树里面，失衡了就暴力重构成完全平衡的点分治树。
也许链分治可以做，那么LCT裸上?我太弱了只会写点分治......
*/