国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

BZOJ 1014, 火星人

2019-11-10 17:27:33
字體:
來源:轉載
供稿:網友

PRoblem

傳送門

Mean

給定一僅有小寫字母組成的字符串,要求支持單字符修改、插入和查詢不同起始位置的最長公共前綴長度。

Analysis

用Splay維護字符串,二分+Hash查詢。 反反復復WA了很多次,就因為Hash的操作順序不太對……也算是買了個教訓。

Code

#include<cstdio>#include<cstring>typedef long long ll;const int x=31,L=110005,MOD=1000173169;int o,m,a,b,len,cnt,sz[L],f[L],v[L],son[L][2],p[L],h[L];char c,s[L];void up(int o){ int l=son[o][0],r=son[o][1]; sz[o]=sz[l]+sz[r]+1; h[o]=(h[l]+(ll)v[o]*p[sz[l]]%MOD+(ll)h[r]*p[sz[l]+1]%MOD)%MOD;}void read(int &x){ char c; while((c=getchar())<'0' || c>'9'); x=c-'0'; while((c=getchar())>='0' && c<='9') x=x*10+c-'0';}void read(char &c){while(((c=getchar())<'A' || c>'Z') && (c<'a' || c>'z'));}int build(int l,int r,int fa){ int x=++cnt,mid=l+r>>1; f[x]=fa,v[x]=s[mid]-'a'+1; if(l<mid) son[x][0]=build(l,mid-1,x); if(r>mid) son[x][1]=build(mid+1,r,x); up(x); return x;}int kth(int k){ for(int x=o,tmp;;){ tmp=sz[son[x][0]]+1; if(tmp==k) return x; if(tmp>k) x=son[x][0]; else x=son[x][1],k-=tmp; }}void rotate(int x){ int y=f[x],w=son[y][1]==x; if(son[y][w]=son[x][w^1]) f[son[x][w^1]]=y; if(f[x]=f[y]) son[f[y]][son[f[y]][1]==y]=x; son[x][w^1]=y,f[y]=x; up(y);}void splay(int x,int w){ while(f[x]!=w){ int y=f[x]; if(f[y]!=w){ if((son[f[y]][0]==y)^(son[y][0]==x)) rotate(x); else rotate(y); } rotate(x); } if(!w) o=x; up(x);}int query(int x,int l){ int a=kth(x),b=kth(x+l+1); splay(a,0),splay(b,a); return h[son[b][0]];}int solve(int x,int y){ int l=1,r=cnt-y-1,ans=0; while(l<=r){ int mid=l+r>>1; if(query(x,mid)==query(y,mid)) ans=mid,l=mid+1; else r=mid-1; } return ans;}int main(){ scanf("%s",s+1); len=strlen(s+1); p[0]=1; for(int i=1;i<L;i++) p[i]=(ll)p[i-1]*x%MOD; o=build(0,len+1,0); read(m); while(m--){ read(c),read(a); if(c=='Q'){ read(b); printf("%d/n",a<b?solve(a,b):solve(b,a)); }else if(c=='R'){ a=kth(a+1); splay(a,0); read(c); v[a]=c-'a'+1; up(a); }else{ a=kth(a+1); splay(a,0); read(c); f[++cnt]=a,v[cnt]=c-'a'+1; son[cnt][1]=son[a][1],f[son[a][1]]=cnt,son[a][1]=cnt; up(cnt),up(a); } } return 0;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 高邑县| 法库县| 隆子县| 台南县| 新余市| 锡林郭勒盟| 余姚市| 阿克苏市| 永泰县| 县级市| 扶余县| 金川县| 宜川县| 潮安县| 新巴尔虎左旗| 镇坪县| 东乡县| 镇雄县| 拜泉县| 黄陵县| 彰武县| 十堰市| 青铜峡市| 分宜县| 海安县| 远安县| 芦山县| 青海省| 德令哈市| 聂拉木县| 锦屏县| 肃北| 师宗县| 徐闻县| 平陆县| 揭西县| 沅江市| 揭西县| 怀集县| 将乐县| 井冈山市|