读入优化
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
平衡树
#include<bits/stdc++.h>
using namespace std;
int n,rd,root,size[100001],cnt[100001],ch[100001][2],val[100001],sum,fa[100001],op;
void update(int x)
{
size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];
}
int rela(int x)
{
return ch[fa[x]][1]==x;
}
void rotate(int x)
{
int p=fa[x],g=fa[p],k=rela(x),son=ch[x][k^1];
ch[p][k]=son,fa[son]=p;
ch[g][rela(p)]=x,fa[x]=g;
ch[x][k^1]=p,fa[p]=x;
update(x),update(p);
}
void splay(int x,int goal=0)
{
while(fa[x]!=goal)
{
int p=fa[x],g=fa[p];
if(g!=goal)
{
if(rela(x)==rela(p))
rotate(p);
else
rotate(x);
}
rotate(x);
}
if(!goal)
root=x;
}
void mov(int x)
{
int cur=root;
while(ch[cur][x>val[cur]]&&x!=val[cur])
cur=ch[cur][x>val[cur]];
splay(cur);
}
void insert(int x)
{
int cur=root,p=0;
while(cur&&val[cur]!=x)
{
p=cur;
cur=ch[cur][x>val[cur]];
}
if(cur)
cnt[cur]++;
else
{
cur=++sum;
if(p)
ch[p][x>val[p]]=cur;
ch[cur][0]=ch[cur][1]=0;
val[cur]=x,fa[cur]=p;
cnt[cur]=size[cur]=1;
}
splay(cur);
}
int kth(int k)
{
int cur=root;
while(1)
{
if(ch[cur][0]&&k<=size[ch[cur][0]])
cur=ch[cur][0];
else if(k>size[ch[cur][0]]+cnt[cur])
{
k-=size[ch[cur][0]]+cnt[cur];
cur=ch[cur][1];
}
else
return cur;
}
}
int rank(int x)
{
mov(x);
return size[ch[root][0]];
}
int pre(int x)
{
mov(x);
if(val[root]<x)
return root;
int cur=ch[root][0];
while(ch[cur][1])
cur=ch[cur][1];
return cur;
}
int fwer(int x)
{
mov(x);
if(val[root]>x)
return root;
int cur=ch[root][1];
while(ch[cur][0])
cur=ch[cur][0];
return cur;
}
void remove(int x)
{
int last=pre(x),next=fwer(x);
splay(last),splay(next,last);
int del=ch[next][0];
if(cnt[del]>1)
{
cnt[del]--;
splay(del);
}
else
ch[next][0]=0;
}
int main()
{
cin>>n;
insert(0x3f3f3f3f);
insert(0xcfcfcfcf);
for(int i=1;i<=n;i++)
{
cin>>op>>rd;
switch(op)
{
case 1:{
insert(rd);
break;
}
case 2:{
remove(rd);
break;
}
case 3:{
cout<<rank(rd)<<endl;
break;
}
case 4:{
cout<<val[kth(rd+1)]<<endl;
break;
}
case 5:{
cout<<val[pre(rd)]<<endl;
break;
}
case 6:{
cout<<val[fwer(rd)]<<endl;
break;
}
}
}
return 0;
}
树链剖分
#include<bits/stdc++.h>
using namespace std;
long long n,m,val[100001],op,ra,rb,rc,s[100001],cnt,num,root,mod,x,f,id[10001];
long long h[100001],dep[100001],fa[100001],size[100001],son[10001],top[10001];
struct node{
long long le,ri,sum,mark;
}tr[400001];
struct edge{
long long to,next;
}e[400001];
void add(int a,int b)
{
e[++cnt].to=b;
e[cnt].next=h[a];
h[a]=cnt;
}
void pushup(int p)
{
tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
}
void pushdown(int p)
{
if(!tr[p].mark)
return;
int mid=tr[p].le+tr[p].ri>>1;
tr[p<<1].sum+=(mid-tr[p].le+1)*tr[p].mark;
tr[p<<1|1].sum+=(tr[p].ri-mid)*tr[p].mark;
tr[p<<1].mark+=tr[p].mark;
tr[p<<1|1].mark+=tr[p].mark;
tr[p].mark=0;
}
void build(int v,int l,int r)
{
tr[v].le=l,tr[v].ri=r;
if(l==r)
{
tr[v].sum=val[l];
return;
}
int mid=l+r>>1;
build(v<<1,l,mid);
build(v<<1|1,mid+1,r);
pushup(v);
}
void add(int v,int l,int r,int val)
{
if(tr[v].le>=l&&tr[v].ri<=r)
{
tr[v].sum+=(tr[v].ri-tr[v].le+1)*val;
tr[v].mark+=val;
return;
}
pushdown(v);
int mid=tr[v].le+tr[v].ri>>1;
if(l<=mid) add(v<<1,l,r,val);
if(r>mid) add(v<<1|1,l,r,val);
pushup(v);
}
long long ask(int v,int l,int r)
{
if(tr[v].le>=l&&tr[v].ri<=r)
return tr[v].sum;
long long ret=0;
int mid=tr[v].le+tr[v].ri>>1;
pushdown(v);
if(mid>=l) ret+=ask(v<<1,l,r);
if(mid<r) ret+=ask(v<<1|1,l,r);
return ret;
}
void dfs(int v,int f)
{
dep[v]=dep[f]+1;
fa[v]=f;
size[v]=1;
int maxson=-1;
for(int i=h[v];i;i=e[i].next)
{
int u=e[i].to;
if(u==f)
continue;
dfs(u,v);
size[v]+=size[u];
if(size[u]>maxson)
{
maxson=size[u];
son[v]=u;
}
}
}
void dfst(int v,int topf)
{
id[v]=++num;
val[num]=s[v];
top[v]=topf;
if(!son[v])
return;
dfst(son[v],topf);
for(int i=h[v];i;i=e[i].next)
{
int u=e[i].to;
if(u==fa[v]||u==son[v])
continue;
dfst(u,u);
}
}
long long range(int x,int y)
{
long long ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
ans+=ask(1,id[top[x]],id[x]);
ans%=mod;
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
ans+=ask(1,id[x],id[y]);
return ans%mod;
}
long long askson(int x)
{
return ask(1,id[x],id[x]+size[x]-1)%mod;
}
void updrange(int x,int y,int k)
{
k%=mod;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
add(1,id[top[x]],id[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
add(1,id[x],id[y],k);
}
void updson(int x,int k)
{
add(1,id[x],id[x]+size[x]-1,k);
}
int main()
{
cin>>n>>m>>root>>mod;
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<n;i++)
{
cin>>ra>>rb;
add(ra,rb);
add(rb,ra);
}
dfs(root,0);dfst(root,0);
build(1,1,n);
for(int i=1;i<=m;i++)
{
cin>>op;
if(op==1)
{
cin>>ra>>rb>>rc;
updrange(ra,rb,rc);
}
else if(op==2)
{
cin>>ra>>rb;
cout<<range(ra,rb)<<endl;
}
else if(op==3)
{
cin>>ra>>rb;
updson(ra,rb);
}
else
{
cin>>ra;
cout<<askson(ra)<<endl;
}
}
return 0;
}
线段树
#include<bits/stdc++.h>
using namespace std;
long long n,m,val[100001],op,ra,rb,rc;
struct tree{
int le,ri;
long long sum,mark;
}tr[400001];
void pushup(int p)
{
tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
}
void pushdown(int p)
{
if(!tr[p].mark)
return;
int mid=tr[p].le+tr[p].ri>>1;
tr[p<<1].sum+=(mid-tr[p].le+1)*tr[p].mark;
tr[p<<1|1].sum+=(tr[p].ri-mid)*tr[p].mark;
tr[p<<1].mark+=tr[p].mark;
tr[p<<1|1].mark+=tr[p].mark;
tr[p].mark=0;
}
void build(int l,int r,int v)
{
tr[v].le=l,tr[v].ri=r;
if(l==r)
{
tr[v].sum=val[l];
return;
}
int mid=l+r>>1;
build(l,mid,v<<1);
build(mid+1,r,v<<1|1);
pushup(v);
}
void add(int l,int r,int val,int v)
{
if(tr[v].le>=l&&tr[v].ri<=r)
{
tr[v].sum+=(tr[v].ri-tr[v].le+1)*val;
tr[v].mark+=val;
return;
}
pushdown(v);
int mid=tr[v].le+tr[v].ri>>1;
if(l<=mid) add(l,r,val,v<<1);
if(r>mid) add(l,r,val,v<<1|1);
pushup(v);
}
long long ask(int l,int r,int v)
{
if(l<=tr[v].le&&tr[v].ri<=r)
return tr[v].sum;
long long ret=0;
int mid=tr[v].le+tr[v].ri>>1;
pushdown(v);
if(mid>=l) ret+=ask(l,r,v<<1);
if(mid<r) ret+=ask(l,r,v<<1|1);
return ret;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>val[i];
build(1,n,1);
for(int i=1;i<=m;i++)
{
cin>>op;
if(op==1)
{
cin>>ra>>rb>>rc;
add(ra,rb,rc,1);
}
else
{
cin>>ra>>rb;
cout<<ask(ra,rb,1)<<endl;
}
}
return 0;
}
AC自动机
#include<bits/stdc++.h>
using namespace std;
long long n,l,now,cnt,val[500001],ch[500001][27],fail[500001],ans;
char s[1000001];
queue<int>q;
void insert()
{
l=strlen(s+1),now=0;
for(int i=1;i<=l;i++)
{
int v=s[i]-'a'+1;
if(!ch[now][v])
ch[now][v]=++cnt;
now=ch[now][v];
}
val[now]++;
}
void build()
{
for(int i=1;i<=26;i++)
if(ch[0][i])
{
fail[ch[0][i]]=0;
q.push(ch[0][i]);
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=1;i<=26;i++)
if(ch[u][i])
{
fail[ch[u][i]]=ch[fail[u]][i];
q.push(ch[u][i]);
}
else
ch[u][i]=ch[fail[u]][i];
}
}
void quary()
{
l=strlen(s+1),now=0;
for(int i=1;i<=l;i++)
{
now=ch[now][s[i]-'a'+1];
for(int t=now;t&&val[t];t=fail[t])
{
ans+=val[t];
val[t]=0;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s+1;
insert();
}
fail[0]=0;
build();
cin>>s+1;
quary();
cout<<ans<<endl;
return 0;
}