LCA:
#include<bits/stdc++.h>
using namespace std;
const int N=500000,M=500000*2,LOGN=30;
int head[N+10],ver[M+10],nxt[M+10],tot=0,t,n,m,d[N+10],f[N+10][LOGN+10];
void add(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void bfs(int cur)
{
queue<int> que;
que.push(cur);
d[cur]=1;
while(!que.empty())
{
int x=que.front();que.pop();
for(int i=head[x];i;i=nxt[i])
{
int y=ver[i];
if(d[y]) continue;
d[y]=d[x]+1;
f[y][0]=x;
for(int j=1;j<=t;j++)
f[y][j]=f[f[y][j-1]][j-1];
que.push(y);
}
}
}
int lca(int x,int y)
{
if(d[x]<d[y]) swap(x,y);
for(int i=t;~i;i--)
if(d[f[x][i]]>=d[y])
x=f[x][i];
if(x==y) return x;
for(int i=t;~i;i--)
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
return f[x][0];
}
int main()
{
int s;
scanf("%d %d %d",&n,&m,&s);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
t=log2(n)+1;
bfs(s);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
printf("%d
",lca(x,y));
}
return 0;
}
线段树：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5;
typedef long long ll;
int a[N+10],n,m;
struct SegmentTree
{
int l,r;
ll add,sum;
}t[N*4+10];
void build(int p,int l,int r)
{
t[p].l=l;
t[p].r=r;
if(l==r)
{
t[p].sum=a[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
void spread(int p)
{
if(t[p].add)
{
t[p*2].add+=t[p].add;
t[p*2+1].add+=t[p].add;
t[p*2].sum+=(t[p*2].r-t[p*2].l+1)*t[p].add;
t[p*2+1].sum+=(t[p*2+1].r-t[p*2+1].l+1)*t[p].add;
t[p].add=0;
}
}
void change(int p,int l,int r,int d)
{
if(l<=t[p].l && t[p].r<=r)
{
t[p].add+=d;
t[p].sum+=(t[p].r-t[p].l+1)*d;
return;
}
spread(p);
int mid=(t[p].l+t[p].r)/2;
if(l<=mid) change(p*2,l,r,d);
if(r>mid) change(p*2+1,l,r,d);
t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
ll query(int p,int l,int r)
{
if(l<=t[p].l && t[p].r<=r) return t[p].sum;
ll ans=0;
spread(p);
int mid=(t[p].l+t[p].r)/2;
if(l<=mid) ans+=query(p*2,l,r);
if(mid<r) ans+=query(p*2+1,l,r);
return ans;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int p;
scanf("%d",&p);
if(p==1)
{
int l,r,d;
scanf("%d %d %d",&l,&r,&d);
change(1,l,r,d);
}
else
{
int l,r;
scanf("%d %d",&l,&r);
printf("%lld
",query(1,l,r));
}
}
return 0;
}
kmp:
void init()
{
int lb=strlen(b+1);
for(int i=2,j=0;i<=lb;i++)
{
while(j && b[i]!=b[j+1]) j=nxt[j];
if(b[i]==b[j+1]) j++;
nxt[i]=j;
}
}
int kmp()
{
int ans=0;
int la=strlen(a+1),lb=strlen(b+1);
for(int i=1,j=0;i<=la;i++)
{
while(j && a[i]!=b[j+1]) j=nxt[j];
if(a[i]==b[j+1]) j++;
if(j==lb)
{
ans++;
j=nxt[j];
}
}
return ans;
}
火车头：
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
Splay：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5;
int rt,tot,sz[N+10],ch[N+10][2],fa[N+10],cnt[N+10],val[N+10];
void maintain(int x) {sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];}
void clear(int x) {sz[x]=ch[x][0]=ch[x][1]=fa[x]=cnt[x]=val[x]=0;}
int get(int x) {return ch[fa[x]][1]==x;}
void rorate(int x)
{
int y=fa[x],z=fa[y],w=get(x);
ch[y][w]=ch[x][w^1];
fa[ch[x][w^1]]=y;
ch[x][w^1]=y;
fa[y]=x;
fa[x]=z;
if(z) ch[z][y==ch[z][1]]=x;
maintain(y);
maintain(x);
}
void splay(int x)
{
for(int f=fa[x];f=fa[x],f;rorate(x))
if(fa[f]) rorate(get(f)==get(x)?f:x);
rt=x;
}
void ins(int k)
{
if(!rt)
{
val[++tot]=k;
cnt[tot]++;
rt=tot;
maintain(rt);
return;
}
int cur=rt,f=0;
while(1)
{
if(val[cur]==k)
{
cnt[cur]++;
maintain(cur);
maintain(f);
splay(cur);
break;
}
f=cur;
cur=ch[cur][val[cur]<k];
if(!cur)
{
val[++tot]=k;
cnt[tot]++;
fa[tot]=f;
ch[f][val[f]<k]=tot;
maintain(tot);
maintain(f);
splay(tot);
break;
}
}
}
int rk(int k)
{
int cur=rt,res=0;
while(1)
{
if(k<val[cur]) cur=ch[cur][0];
else
{
res+=sz[ch[cur][0]];
if(val[cur]==k)
{
splay(cur);
return res+1;
}
res+=cnt[cur];
cur=ch[cur][1];
}
}
}
int kth(int k)
{
int cur=rt;
while(1)
{
if(k<=sz[ch[cur][0]] && ch[cur][0]) cur=ch[cur][0];
else
{
k-=sz[ch[cur][0]]+cnt[cur];
if(k<=0)
{
splay(cur);
return val[cur];
}
cur=ch[cur][1];
}
}
}
int pre()
{
int cur=ch[rt][0];
while(ch[cur][1]) cur=ch[cur][1];
return cur;
}
int nxt()
{
int cur=ch[rt][1];
while(ch[cur][0]) cur=ch[cur][0];
return cur;
}
void del(int k)
{
rk(k);
if(cnt[rt]>1)
{
cnt[rt]--;
maintain(rt);
return;
}
if(!ch[rt][0] && !ch[rt][1])
{
clear(rt);
rt=0;
return;
}
if(!ch[rt][0])
{
int cur=rt;
rt=ch[rt][1];
fa[rt]=0;
clear(cur);
return;
}
if(!ch[rt][1])
{
int cur=rt;
rt=ch[rt][0];
fa[rt]=0;
clear(cur);
return;
}
int cur=rt,x=pre();
splay(x);
fa[ch[cur][1]]=x;
ch[x][1]=ch[cur][1];
clear(cur);
maintain(rt);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int p,x;
scanf("%d %d",&p,&x);
if(p==1) ins(x);
else if(p==2) del(x);
else if(p==3) printf("%d
",rk(x));
else if(p==4) printf("%d
",kth(x));
else if(p==5)
{
ins(x);
printf("%d
",val[pre()]);
del(x);
}
else
{
ins(x);
printf("%d
",val[nxt()]);
del(x);
}
}
return 0;
}