代码仓库

6

代码仓库

char st[N]; while(~scanf(\,st)){ string st0=\; for(int i=0;st[i]!='\\0';i++){ st0+=st[i]; st0+=\; } printf(\,Manacher(st0)); } return0; } KMP 字符串匹配

#include #include usingnamespace std; typedeflonglong ll; constint N=100007; constint P=1000000007; char a[N],b[N]; bool mat[N]; int next[N]; ll f[N];

void getNext(int m){ int i=0,j=-1; next[0]=-1; while(i

if(j==-1||b[i]==b[j]){ if(b[++i]!=b[++j])next[i]=j; else next[i]=next[j]; }else j=next[j]; } }

void KMP(int n,int m){

memset(mat,0,sizeof(mat)); int i=0,j=0; getNext(m); while(i

if(j==-1||a[i]==b[j])i++,j++; else j=next[j]; if(!i&&!j)break;

7

代码仓库

if(j==m){ mat[i]=1; //printf(\ j=next[j]; } } }

线段树(ZKW大法) #include #include #include #include usingnamespace std; constint INF=0x3f3f3f3f; constint N=3000100; struct linetree{ #define lc (t<<1) #define rc (t<<1^1) int mi[N],M;

inlinevoid build(int n){

M=1;while(M

for(int i=1+M;i<=n+M;i++) scanf(\,&mi[i]); for(int t=M;t>=1;t--)mi[t]=min(mi[lc],mi[rc]); }

void change(int t,int x){ for(mi[t+=M]=x,t>>=1;t;t>>=1) mi[t]=min(mi[lc],mi[rc]); }

int query(int l,int r){ int ans = INF;

for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){ if(~l&1)ans=min(ans,mi[l^1]); if( r&1)ans=min(ans,mi[r^1]); }

return ans; }

8

代码仓库

}T; int main(){ int n,q,ord,x,y; for(;~scanf(\,&n);){ T.build(n); for(scanf(\,&q);q--;){ scanf(\,&ord,&x,&y); if(ord)T.change(x,y); else printf(\,T.query(x,y)); } } return0; } 线段树（RMQ） #include #include #include #include usingnamespace std; constint INF=0x3f3f3f3f; constint N=600100; int n,ans,m,a[N]; struct node { int l,r,id; node (){}

node(int x,int y,int z){l=x;r=y;id=z;} }b[N],c[N];

inlinebool cmp1(node a,node b){return a.l

struct linetree{ #define lc (t<<1) #define rc (t<<1^1) #define mid (l[t]+r[t]>>1)

int l[N],r[N],ma[N],mi[N],M,ta[N],ti[N]; inlinevoid build(int n){

M=1;while(M

9

代码仓库

for(int i=1+M;i<=M*2+1;i++)l[i]=r[i]= i-M ; for(int t=M;t>=1;t--)l[t]=l[lc],r[t]=r[rc]; }

inlinevoid down(int t){ if(t>M)return;//leaf node

ma[lc]=max(ma[lc],ta[t]); ma[rc]=max(ma[rc],ta[t]); ta[lc]=max(ta[lc],ta[t]); ta[rc]=max(ta[rc],ta[t]); ta[t]=0;

mi[lc]=min(mi[lc],ti[t]); mi[rc]=min(mi[rc],ti[t]); ti[lc]=min(ti[lc],ti[t]); ti[rc]=min(ti[rc],ti[t]); ti[t]= INF; }

inlinevoid maintain(int t){ ma[t]=max(ma[lc],ma[rc]); mi[t]=min(mi[lc],mi[rc]); }

inlinevoid tag(int t,int x){ ma[t]=max(ma[t],x); mi[t]=min(mi[t],x); ta[t]=max(ta[t],x); ti[t]=min(ti[t],x); }

void change(int t,int L,int R,int x){ if(L<=l[t]&&r[t]<=R){tag(t,x);return;}//in down(t);

if(L<=mid)change(lc,L,R,x); if(mid< R)change(rc,L,R,x); maintain(t); }

void query(int t){ if(t>M){//leaf node

b[t-M]=c[t-M]=node(mi[t],ma[t],t-M); return; }

down(t); query(lc); query(rc);

10

代码仓库

maintain(t); } }T;

线段树（区间加+赋值） #include #include #include #include usingnamespace std; constint N =260000; int n,m;

struct linetree{ #define lc (t<<1) #define rc (t<<1^1) #define mid (l[t]+r[t]>>1)

int l[N],r[N],M,tag[N],sum[N],len[N],Set[N]; inlinevoid build(int n){

M=1;while(M

for(int t=M;t>=1;t--){//fathers