寒假集训纪要
1.28
KMP算法
匹配
int j;
j=0;
for(int i=1;i<=la;++i)
{
while(j && b[j+1]!=a[i]) j=next[j];
if(b[j+1]==a[j]) j++;
if(j==lb)
{
cout<<i-lb+1<<'\n';
j=next[j];
}
}
处理 next 数组
j=0;
for(int i=2;i<=lb;++i)
{
while(j && b[i]!=b[j+1])
j=next[j];
if(b[j+1]==b[j]) j++;
next[i]=j;
}
洛谷模板
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+50;
int la,lb,next_[N],j;
char a[N],b[N];
signed main()
{
cin>>a+1;
cin>>b+1;
la=strlen(a+1);
lb=strlen(b+1);
for(int i=2;i<=lb;++i)
{
while(j && b[i]!=b[j+1])
j=next_[j];
if(b[j+1]==b[i]) j++;
next_[i]=j;
}
j=0;
for(int i=1;i<=la;++i)
{
while(j>0 && b[j+1]!=a[i]) j=next_[j];
if(b[j+1]==a[i]) j++;
if(j==lb)
{
cout<<i-lb+1<<'\n';
j=next_[j];
}
}
for(int i=1;i<=lb;++i)
cout<<next_[i]<<" ";
}
动物园
有趣的题
预处理串的长度然后 num 数组按题意模拟即可（不是
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+50;
const int p=1e9+7;
int la,lb,next_[N],n;
int sum[N];
char a[N];
signed main()
{
cin>>n;
while(n--)
{
memset(next_,0,sizeof(next_));
memset(sum,0,sizeof(sum));
cin>>a+1;
la=strlen(a+1);
int ans=1;
sum[1]=1,next_[1]=0;
for(int i=2,j=0;i<=la;++i)
{
while(j && a[i]!=a[j+1])
j=next_[j];
if(a[j+1]==a[i]) j++;
next_[i]=j;
sum[i]=sum[j]+1;
}
for(int i=1,j=0;i<=la;++i)
{
while(j>0 && a[j+1]!=a[i]) j=next_[j];
if(a[j+1]==a[i]) j++;
while(j>i/2) j=next_[j];
ans=(ans*(sum[j]+1))%p;
}
cout<<ans<<'\n';
}
}
Censoring S
KMP删除操作，栈模拟，如果匹配到了子串就出栈即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+50;
const int p=1e9+7;
int la,lb,next_[N],n;
int pos[N],top,sta[N];
char a[N],b[N];
signed main()
{
cin>>a+1>>b+1;
int la=strlen(a+1),lb=strlen(b+1);
for(int i=2,j=0;i<=lb;++i)
{
while(j && b[i]!=b[j+1])
j=next_[j];
if(b[j+1]==b[i]) j++;
next_[i]=j;
}
for(int i=1,j=0;i<=la;++i)
{
while(j && a[i]!=b[j+1]) j=next_[j];
if(b[j+1]==a[i]) j++;
pos[i]=j;
sta[++top]=i;
if(j==lb) top-=lb,j=pos[sta[top]];
}
for(int i=1;i<=top;++i)
cout<<a[sta[i]];
}
【XR-3】系统设计
写的最久的题，挑了一下午发现线段树写假了😅😅😅
线段树上哈希（？），看着题解过了，大概算是懂了吧。
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int unsigned long long
#define mid ((l+r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
namespace IO
{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}if(cnt==0)putchar('0');while(cnt>0)putchar(F[--cnt]);putchar(' ');}
}
using namespace std;
using namespace __gnu_pbds;
using namespace IO;
const int N=1e6;
const int base=2e6+3;
int n,m,T,ans,root,fa[N],cur,len,t[N<<2],pri=229,a[N],sx[N],Pow[N];
vector<int> num[N];
cc_hash_table<int,int> q;
int op,x,l,r;
inline void dfs(int x,int fa)
{
q[sx[x]]=x;
for(int i=0,y;i<num[x].size();++i)
if((y=num[x][i])!=fa)
sx[y]=sx[x]*base+i+1+pri,dfs(y,x);
}
inline void pushup(int p,int len)
{
t[p]=t[ls]*Pow[len]+t[rs];
}
void build(int p,int l,int r)
{
if(l==r)
{
t[p]=a[l]+pri;return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(p,r-mid);
}
inline void Update(int p,int l,int r,int k,int d)
{
if(l==r)
{
t[p]=d+pri;
return;
}
k<=mid ? Update(ls,l,mid,k,d) : Update(rs,mid+1,r,k,d);
pushup(p,r-mid);
}
inline int ask(int p,int l,int r)
{
if(l==r) return l;
int x=cur*Pow[mid-l+1]+t[ls];
if(q.find(x)==q.end()) return ask(ls,l,mid);
cur=x;
return ask(rs,mid+1,r);
}
inline int Find(int p,int L,int R,int l,int r,int &o)
{
if(L<=l && r<=R)
{
int x=cur*Pow[r-l+1]+t[p];
if(q.find(x)==q.end())
{
o=1;
return ask(p,l,r);
}
cur=x;
return 0;
}
if(L>mid) return Find(rs,L,R,mid+1,r,o);
if(R<=mid) return Find(ls,L,R,l,mid,o);
int ans=Find(ls,L,R,l,mid,o);
return o ? ans : Find(rs,L,R,mid+1,r,o);
}
signed main()
{
n=read();m=read();T=read();
Pow[0]=1;
for(int i=1;i<N;++i)
Pow[i]=Pow[i-1]*base;
for(int i=1;i<=n;++i)
{
fa[i]=read();
if(!fa[i]) root=i;
else num[fa[i]].push_back(i);
}
for(int i=1;i<=m;++i)
a[i]=read();
for(int i=1;i<=n;++i)
sort(num[i].begin(),num[i].end());
dfs(root,0);
build(1,1,m);
while(T--)
{
op=read();
if(op==2)
{
l=read();x=read();Update(1,1,m,l,x);
}
else
{
x=read();l=read();r=read();
cur=sx[x];
int fl=0;Find(1,l,r,1,m,fl);
cout<<q[cur]<<'\n';
}
}
}
1.29
学习了 Trie 和 01-Trie，但是写的题都挺板的，可能是难题现在也写不了了吧。
OKR-Periods of Words
KMP，找到前缀后继续找前缀的前缀，因为 border 的一些性质可以得到字符串的最小 border.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+50;
const int p=1e9+7;
int n,lb,next_[N];
int ans;
int min_border[N];
char a[N];
signed main()
{
cin>>n;
cin>>a+1;
for(int i=2,j=0;i<=n;++i)
{
while(j && a[i]!=a[j+1])
j=next_[j];
if(a[j+1]==a[i]) j++;
next_[i]=j;
}
for(int i=1;i<=n;++i)
{
int j=i;
while(next_[j]) j=next_[j];
if(next_[i]) next_[i]=j;
ans+=(i-j);
}
cout<<ans;
}
Trie
最基础的板子（判断是否有 \(A\) 串为 \(B\) 串的前缀）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
const int p=1e9+7;
int n,tot,nxt[N],k,t;
int root,len;
int trie[N][30];
int f[N];
inline void insert(string s)
{
int len=s.size();
int root=1;
for(int i=0;i<len;++i)
{
int x=s[i]-'0';
if(!trie[root][x])
trie[root][x]=++tot;
root=trie[root][x];
}
f[root]=1;
}
inline int find(string s)
{
int len=s.size();
int root=1;
for(int i=0;i<len;++i)
{
int x=s[i]-'0';
if(!trie[root][x]) return 0;
root=trie[root][x];
if(f[root]) return 1;
}
return 1;
}
signed main()
{
cin>>t;
while(t--)
{
memset(trie,0,sizeof(trie));
memset(f,0,sizeof(f));
tot=1;
int ans=0;
cin>>n;
for(int i=1;i<=n;++i)
{
string s;
cin>>s;
if(find(s)) ans=1;
insert(s);
}
if(ans) cout<<"NO"<<'\n';
else cout<<"YES"<<'\n';
}
}
01-Trie
两点异或最大和
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+5;
const int p=1e9+7;
int n,tot,nxt[N],k,t;
int root,ans;
int trie[N][2];
int s[N];
inline void insert(int x)
{
int root=0;
for(int i=31;i>=0;--i)
{
int c=(x>>i)&1;
if(!trie[root][c])
trie[root][c]=++tot;
root=trie[root][c];
}
}
inline int find(int x)
{
int root=0;
int ans=0;
for(int i=31;i>=0;--i)
{
int c=(x>>i)&1,o=c^1;
if(trie[root][o]) root=trie[root][o],ans=ans<<1|1;
else root=trie[root][c],ans<<=1;
}
return ans;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
int x;
cin>>x;
ans=max(ans,find(x));
insert(x);
}
cout<<ans;
}
边权异或最大值（放个前向星存图就行）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+5;
const int p=1e9+7;
int n,tot,nxt[N],k,t;
int root;
int trie[N][2];
int s[N];
struct node
{
int to,next,w;
}e[2*N];
int head[N],cnt;
inline void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].next=head[u];
e[cnt].w=w;
head[u]=cnt;
}
inline void insert(int x)
{
int root=0;
for(int i=31;i>=0;--i)
{
int c=(x>>i)&1;
if(!trie[root][c])
trie[root][c]=++tot;
root=trie[root][c];
}
}
inline int find(int x)
{
int root=0;
int ans=0;
for(int i=31;i>=0;--i)
{
int c=(x>>i)&1,o=c^1;
if(trie[root][o]) root=trie[root][o],ans=ans<<1|1;
else root=trie[root][c],ans<<=1;
}
return ans;
}
int f[N];
inline void dfs(int x,int fa)
{
insert(f[x]);
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if(fa==y) continue;
f[y]=f[x]^e[i].w;
dfs(y,x);
}
}
signed main()
{
cin>>n;
for(int i=1;i<n;++i)
{
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
dfs(1,1);int ans=0;
for(int i=1;i<=n;++i)
ans=max(ans,find(f[i]));
cout<<ans;
}
Nikitosh 和异或
神奇的数据导致可以乱搞做法（非正解，无不良导向）
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int n,a,ans=0;
cin>>n;
while(n--)
{
cin>>a;
ans|=a;
}
cout<<ans*2;
}
字符串匹配
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+50;
const int p=1e9+7;
int n,lb,nxt[N],k,s,t;
int c[N],ans[N];
int a[N],b[N],rk[N],rks[N],f[N];
inline int lowbit(int x){return x&(-x);}
inline void update(int p,int v){while(p<=s){c[p]+=v;p+=lowbit(p);}}
inline int ask(int p){int ans=0;while(p){ans+=c[p];p-=lowbit(p);}return ans;}
signed main()
{
cin>>n>>k>>s;
for(int i=0;i<n;++i)
cin>>a[i];
for(int i=0;i<k;++i)
{
cin>>b[i];
update(b[i],1);
rk[i]=ask(b[i]-1),rks[i]=ask(b[i]);
}
memset(c,0,sizeof(c));
for(int i=1,j;i<k;++i)
{
j=f[i];
update(b[i],1);
while(j && (ask(b[j]-1)!=rk[i] || ask(b[j])!=rks[i]))
{
for(int p=i-j;p<i-f[j];++p) update(b[p],-1);
j=f[j];
}
f[i+1]=(rk[j]==ask(b[i]-1) && rks[j]==ask(b[i])) ? j+1 : 0;
}
memset(c,0,sizeof(c));
for(int i=0,j=0;i<n;++i)
{
update(a[i],1);
while(j && (ask(a[i]-1)!=rk[j] || ask(a[i])!=rks[j]))
{
for(int p=i-j;p<i-f[j];++p) update(a[p],-1);
j=f[j];
}
if(ask(a[i]-1)==rk[j] && ask(a[i])==rks[j]) j++;
if(j==k)
{
ans[++t]=i-j+1;
for(int p=i-j+1;p<=i;++p)
update(a[p],-1);
j=0;
}
}
cout<<t<<"\n";
for(int i=1;i<=t;++i)
cout<<ans[i]+1<<"\n";
}
通配符匹配
做法有误，仅限于小数据，详见 1.30 闲话
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+5;
int n,m,t;
char s[N],st[N];
namespace IO
{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
bool check(int n,int m)
{
if(m==0)
{
for(int i=1;i<=n;++i)
if(s[i]!='*')
return 0;
return 1;
}
if(n==0) return 0;
if(s[n]!='*')
return (s[n]==st[m] || s[n]=='?') && check(n-1,m-1);
else
{
for(int i=m;i>=0;--i)
if(check(n-1,i))
return 1;
}
return 0;
}
signed main()
{
scanf("%s",s+1);
n=strlen(s+1);
t=read();
while(t--)
{
scanf("%s",st+1);
m=strlen(st+1);
cout<<(check(n,m) ? "YES" : "NO")<<'\n';
}
}
1.30
AC自动机
AC自动机简单版
模板，查询有多少个子串在文章中出现过
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6e6+5;
int n,m,cnt;
char s[N];
namespace AC_automaton
{
queue<int> q;
struct tree
{
int son[26],flag,fail;
}trie[N];
inline void insert(char* s)
{
int u=1,len=strlen(s);
for(int i=0;i<len;++i)
{
int v=s[i]-'a';
if(!trie[u].son[v]) trie[u].son[v]=++cnt;
u=trie[u].son[v];
}
trie[u].flag++;
}
inline void get_fail()
{
for(int i=0;i<26;++i)
trie[0].son[i]=1;
q.push(1);trie[1].fail=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<26;++i)
{
int v=trie[u].son[i];
int fail=trie[u].fail;
if(!v) {trie[u].son[i]=trie[fail].son[i];continue;}
trie[v].fail=trie[fail].son[i];
q.push(v);
}
}
}
inline int find(char* s)
{
int u=1,ans=0,len=strlen(s);
for(int i=0;i<len;++i)
{
int v=s[i]-'a';
int k=trie[u].son[v];
while(k>1 && trie[k].flag!=-1)
{
ans+=trie[k].flag,trie[k].flag=-1;
k=trie[k].fail;
}
u=trie[u].son[v];
}
return ans;
}
}
using namespace AC_automaton;
namespace IO
{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
cnt=1;
n=read();
for(register int i=1;i<=n;++i)
{
cin>>s;
insert(s);
}
get_fail();
cin>>s;
cout<<find(s);
}
AC自动机简单版二
求子串在文章中出现过几次
#include<bits/stdc++.h>
using namespace std;
const int N=7e5+1;
int n,cnt,ans_cnt;
int ans[N],anss[N];
string s[205];
namespace AC_automaton
{
class
{
public:
int son[26];
int fail,num;
}trie[N];
inline void insert(string s,int id)
{
int u=0,len=s.size();
for(int i=0;i<len;++i)
{
int v=s[i]-'a';
if(!trie[u].son[v]) trie[u].son[v]=++cnt;
u=trie[u].son[v];
}
trie[u].num=id;
}
inline void get_fail()
{
queue<int> q;
for(register int i=1;i<=N;++i)
trie[i].fail=0;
for(register int i=0;i<26;++i)
if(trie[0].son[i])
q.push(trie[0].son[i]);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<26;++i)
{
if(trie[u].son[i])
{
trie[trie[u].son[i]].fail=trie[trie[u].fail].son[i];
q.push(trie[u].son[i]);
}
else
trie[u].son[i]=trie[trie[u].fail].son[i];
}
}
}
inline int find(string s)
{
memset(ans,0,sizeof(ans));
int u=0,res=0,len=s.size();
for(int i=0;i<len;++i)
{
int v=s[i]-'a';
u=trie[u].son[v];
for(int j=u;j;j=trie[j].fail) ans[trie[j].num]++;
}
for(int i=1;i<=n;++i)
{
if(res<ans[i])
{
res=ans[i];
ans_cnt=0;
}
if(res==ans[i]) anss[++ans_cnt]=i;
}
return res;
}
}
using namespace AC_automaton;
namespace IO
{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[20];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
while((n=read())!=0)
{
memset(trie,0,sizeof(trie));
cnt=ans_cnt=0;
for(register int i=1;i<=n;++i)
cin>>s[i],insert(s[i],i);
cin>>s[n+1];
get_fail();
cout<<find(s[n+1])<<'\n';
for(int i=1;i<=ans_cnt;++i)
cout<<s[anss[i]]<<'\n';
}
}
数列分块入门2
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,m;
namespace IO
{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
struct tree
{
int lazy,tot,a[250];
inline int dichotomy(int v)
{
int l=1,r=tot;
while(l<r)
{
int mid=(l+r+1)>>1;
if(a[mid]<v) l=mid;
else r=mid-1;
}
return a[l]<v ? l : 0;
}
}t[250];
int sqt,pos[N],a[N];
inline void Sort(int x)
{
int l=(x-1)*sqt+1,r=x*sqt;
t[x].tot=0;
for(int i=l;i<=r;++i) t[x].a[++t[x].tot]=a[i];
sort(t[x].a+1,t[x].a+t[x].tot+1);
return;
}
inline void Init()
{
sqt=(int)ceil(sqrt(n));
for(int i=1;i<=n;++i)
pos[i]=(i-1)/sqt+1;
for(int i=1;i<=pos[n];++i) Sort(i);
return;
}
inline void update(int l,int r,int v)
{
if(pos[l]==pos[r])
{
for(int i=l;i<=r;++i)
a[i]+=v;
Sort(pos[l]);
return;
}
int i=l,j=r;
while(pos[i]==pos[l]) a[i++]+=v;
while(pos[j]==pos[r]) a[j--]+=v;
Sort(pos[l]),Sort(pos[r]);
for(int k=pos[i];k<=pos[j];++k) t[k].lazy+=v;
return;
}
inline int find(int l,int r,int v)
{
int ans=0;;
if(pos[l]==pos[r])
{
for(int k=l;k<=r;++k)
if(a[k]+t[pos[k]].lazy<v) ans++;
return ans;
}
int i=l,j=r;
while(pos[i]==pos[l])
{
if(a[i]+t[pos[l]].lazy<v) ans++;
i++;
}
while(pos[j]==pos[r])
{
if(a[j]+t[pos[r]].lazy<v) ans++;
j--;
}
for(int k=pos[i];k<=pos[j];++k) ans+=t[k].dichotomy(v-t[k].lazy);
return ans;
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n=read();
for(register int i=1;i<=n;++i)
cin>>a[i];
Init();
while(n--)
{
int opt=read(),l=read(),r=read(),c=read();
if(opt==0) update(l,r,c);
else cout<<find(l,r,c*c)<<'\n';
}
}
数列分块1
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5;
int n,m;
namespace IO
{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
struct tree
{
int l,r,val,tag;
}t[N];
int sqt,ka[N],a[N];
inline void Init(int n)
{
sqt=sqrt(n)+2;
for(int i=1;i<=sqt;++i)
{
t[i].l=t[i-1].r+1;
t[i].r=(i==sqt)? n : t[i].l+sqt;
t[i].val=0;
for(int j=t[i].l;j<=t[i].r;++j)
{
ka[j]=i;
t[i].val+=a[j];
}
}
}
inline void update(int l,int r,int v)
{
if(ka[l]==ka[r]){
for(int i=l;i<=r;i++){
a[i]+=v;
}
t[ka[l]].val+=v*(r-l+1);
return;
}
else{
for(int i=l;i<=t[ka[l]].r;i++){
t[i].val+=v;
a[i]+=v;
}
for(int i=t[ka[r]].l;i<=r;i++){
t[i].val+=v;
a[i]+=v;
}
for(int i=ka[l]+1;i<=ka[r]-1;i++){
t[i].tag+=v;
t[i].val+=sqt*v;
}
}
}
inline int find(int l,int r)
{
int sum=0;
while(t[ka[l]].l!=l && l<=r)
{
sum+=a[l]+t[ka[l]].tag;
++l;
}
while(l+sqt-1<=r)
{
sum+=t[ka[l]].val;
l+=sqt;
}
while(l<=r)
{
sum+=a[l]+t[ka[l]].tag;
++l;
}
return sum;
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
n=read();
for(register int i=1;i<=n;++i)
cin>>a[i];
Init(n);
while(n--)
{
int opt=read(),l=read(),r=read(),c=read();
if(opt==0) update(l,r,c);
else cout<<find(r,r)<<'\n';
}
}
玄武密码
正常跑模板然后把查找改一改记录子串出现的次数即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+1;
int n,m,cnt;
bool vis[N];
char a[N];
char s[100005][101];
namespace AC_automaton
{
class Trie
{
public:
int son[26],flag,fail;
}trie[N];
inline void insert(char* s)
{
int u=0,len=strlen(s);
for(int i=0;i<len;++i)
{
int v=s[i]-'A';
if(!trie[u].son[v]) trie[u].son[v]=++cnt;
u=trie[u].son[v];
}
trie[u].flag++;
}
inline void get_fail()
{
queue<int> q;
for(int i=0;i<26;++i)
if(trie[0].son[i]!=0)
{
trie[trie[0].son[i]].fail=0;
q.push(trie[0].son[i]);
}
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<26;++i)
{
int v=trie[u].son[i];
int fail=trie[u].fail;
if(!v) {trie[u].son[i]=trie[fail].son[i];continue;}
trie[v].fail=trie[fail].son[i];
q.push(v);
}
// if(trie[u].son[i]!=0)
// {
// trie[trie[u].son[i]].fail=trie[trie[u].fail].son[i];
// q.push(trie[u].son[i]);
// }
// else
// trie[u].son[i]=trie[trie[u].fail].son[i];
}
int p(0);
for(int i=0;i<n;++i)
{
p=trie[p].son[a[i]-'A'];
for(int j=p;j && !vis[j];j=trie[j].fail) vis[j]=1;
}
}
inline int find(char* s)
{
int u=0,ans=0,len=strlen(s);
for(int i=0;i<len;++i)
{
int v=s[i]-'A';
u=trie[u].son[v];
if(vis[u]) ans=i+1;
}
return ans;
}
}
using namespace AC_automaton;
namespace IO
{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[20];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
using namespace IO;
signed main()
{
close();
cin>>n>>m;
cin>>a;
for(register int i=1;i<=m;++i)
{
cin>>s[i];
insert(s[i]);
}
get_fail();
for(int i=1;i<=m;++i)
cout<<find(s[i])<<'\n';
}