自己常用的板子

杜教筛

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define LL long long
#define Maxn 3000000
using namespace std;
LL T,N;
LL cnt=0,prime[Maxn+5],mu[Maxn+5],phi[Maxn+5];
bool is_prime[Maxn+5];
LL Sum_Mu[Maxn+5],Sum_Phi[Maxn+5];
tr1::unordered_map<LL,LL> SUM_MU,SUM_PHI;
inline void Read(LL &x)
{
    LL f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
LL Get_Mu_Sum(LL X)
{
    if (X<=Maxn) return Sum_Mu[X];
    if (SUM_MU[X]) return SUM_MU[X];
    LL res=1;
    for (LL l=2,r;l<=X;l=r+1)
    {
        r=X/(X/l);
        res-=(r-l+1)*Get_Mu_Sum(X/l);
    }
    return SUM_MU[X]=res;
}
LL Get_Phi_Sum(LL X)
{
    if (X<=Maxn) return Sum_Phi[X];
    if (SUM_PHI[X]) return SUM_PHI[X];
    LL res=(X+1)*X/2;
    for (LL l=2,r;l<=X;l=r+1)
    {
        r=X/(X/l);
        res-=(r-l+1)*Get_Phi_Sum(X/l);
    }
    return SUM_PHI[X]=res;
}
void Get(LL X)
{
    memset(is_prime,1,sizeof(is_prime));
    is_prime[0]=is_prime[1]=0;mu[1]=1;phi[1]=1;
    for (LL i=1;i<=Maxn;i++)
    {
        if (is_prime[i]) prime[++cnt]=i,mu[i]=-1,phi[i]=i-1;
        for (LL j=1;j<=cnt&&i*prime[j]<=Maxn;j++)
        {
            is_prime[i*prime[j]]=0;
            mu[i*prime[j]]=-mu[i];
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
            if (i%prime[j]==0){mu[i*prime[j]]=0;phi[i*prime[j]]=phi[i]*prime[j];break;}
        }
    }
    for (LL i=1;i<=Maxn;i++) Sum_Mu[i]=Sum_Mu[i-1]+mu[i],Sum_Phi[i]=Sum_Phi[i-1]+phi[i];
}
int main()
{
    Read(T);
    Get(N);
    while (T--)
    {
        Read(N);
        cout<<Get_Phi_Sum(N)<<" "<<Get_Mu_Sum(N)<<endl;
    }
    return 0;
}

点分治

#include<bits/stdc++.h>
using namespace std;
struct node{int next,to,dis;}e[40005*2];
int K,N,cnt=0,head[40005],size[40005],Minn=2e9,rt,len[40005],D[40005],Ans=0,l,r;
bool vis[40005];
inline void Read(int &x)
{
    int f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
inline void add(int a,int b,int c)
{
    e[++cnt].next=head[a],e[cnt].to=b,e[cnt].dis=c,head[a]=cnt;
}
inline void Get_dis(int now,int fa)
{ 
	D[++r]=len[now];
    for (int i=head[now];i;i=e[i].next)
    {
        int v=e[i].to;
        if (vis[v]||v==fa) continue;
        len[v]=len[now]+e[i].dis;
        Get_dis(v,now);
    }
}
inline void Get_rt(int now,int fa,int Size)
{
	size[now]=1;int Max_size=0;
    for (int i=head[now];i;i=e[i].next)
    {
        int v=e[i].to;
        if (vis[v]||v==fa) continue;
        Get_rt(v,now,Size);
        size[now]+=size[v];
        Max_size=max(size[v],Max_size);
    }
    Max_size=max(Max_size,Size-size[now]);
    if (Minn>Max_size) rt=now,Minn=Max_size;
}
inline int solve(int rt,int val)
{
    l=1,r=0;
	int ans=0;
	len[rt]=val;
    Get_dis(rt,rt);
    sort(D+1,D+r+1);
    while (l<r)
    {
        if (D[l]+D[r]<=K) ans+=r-l,l++;
        else r--;
    }
    return ans;
}
inline void Get_Ans(int now)
{
    vis[now]=1;
    Ans+=solve(rt,0);
    for (int i=head[now];i;i=e[i].next)
    {
        int v=e[i].to;
        if (vis[v]) continue;
        Ans-=solve(v,e[i].dis);
        Minn=2e9;
        Get_rt(v,v,size[v]);
        Get_Ans(rt);
    }
}
int main()
{
    memset(vis,0,sizeof(vis));
    Read(N);
    for (int i=1;i<=N-1;i++) 
    {
        int a,b,c;
        Read(a),
        Read(b),
        Read(c);
        add(a,b,c),
        add(b,a,c);
    }
    Read(K);
    Get_rt(1,1,N);
    Get_Ans(rt);
    cout<<Ans<<endl;
    return 0;
}

BSGS&exBSGS

#include<bits/stdc++.h>
using namespace std;
long long b,p,a;
void Read(long long &x)
{
	long long f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
long long gcd(long long a,long long b)
{
	if (b==0) return a;
	return gcd(b,a%b);
}
long long KSM(long long base,long long index,long long p)
{
	long long Res=1;
	while (index)
	{
		if (index%2==1) Res*=base,Res%=p;
		base*=base;
		base%=p;
		index/=2;	
	} 
	return Res%p;
}
void ex_gcd(long long a,long long b,long long &d,long long &x,long long &y) {
	if (b==0) x=1,y=0,d=a;
	else	
	{
		ex_gcd(b,a%b,d,x,y);
		long long tmp=x;x=y;y=tmp-a/b*y;
	}
}
long long inv(long long a,long long b)
{
    long long x,y,d;
    ex_gcd(a,b,d,x,y);
    return (x%b+b)%b;
}
long long BSGS(long long a,long long b,long long p)
{
	map <long long,long long> m;
	long long X=(long long)ceil(sqrt(p));
	m[b]=0;
	long long Ans_=b;
	for (int i=1;i<=X;i++) Ans_*=a,Ans_%=p,m[Ans_]=i;
	long long Ans__=KSM(a,X,p);
	long long Ans___=1,Ans=-1;
	for (int i=1;i<=X;i++) 
	{
		Ans___*=Ans__,Ans___%=p;
		if (m.count(Ans___)) {Ans=i*X-m[Ans___];break;}
	}
	return Ans;
}
long long exBSGS(long long a,long long b,long long p)
{
    if (b==1||p==1)return 0;     
    long long g=gcd(a,p),k=0,na=1;
    while (g!=1)
    {
        if (b%g!=0)return -1;   
        k++;b/=g;p/=g;na=na*(a/g)%p;
        if (na==b)return k;   
        g=gcd(a,p); 
    }
    long long f=BSGS(a%p,b*inv(na,p)%p,p);
    if (f==-1)return -1;
    return f+k;
}

int main() 
{
	while (1)
	{
	Read(a),Read(p),Read(b);
	if (p==0||a==0||b==0) break;
	long long answer=exBSGS(a,b,p);
	if (answer==-1) cout<<"No Solution"<<endl;
	else cout<<answer<<endl;
	}
	return 0;
}

FastIO读写优化

struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;
	~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}
	inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}
	inline void endl(){pc('\n');}
	FastIO& operator >> (int& ret){ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;}
	FastIO& operator >> (char* s){register int Len=0;register char ch=nc();while(ch!='\n'){*(s+Len)=ch;Len++;ch=nc();}}
	FastIO& operator << (int x){if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);while(stk[0]) pc('0'+stk[stk[0]--]);return *this;}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){register int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;

KMP

#include<bits/stdc++.h>
using namespace std;
int len1,len2;
char s1[1000010],s2[1000010];
int next[1000010],ans=0;
int main(){
    scanf("%s%s",s1,s2);
    len1=strlen(s1);len2=strlen(s2);
    next[0]=0;
    for(int i=1;i<len2;i++){
        int temp=next[i-1];
        while(temp>0&&s2[temp]!=s2[i]) temp=next[temp-1];
        if(s2[i]==s2[temp]) next[i]=temp+1;
        next[i]=temp;
    }
    int j=0;
    for(int i=0;i<len1;i++){
        while(j!=0&&s1[i]!=s2[j]) j=next[j-1];
        if(s1[i]==s2[j]) j++;
        if(j==len2){
            j=next[j-1];
            cout<<i-len2+1<<endl;
        }
    }
    return 0;
}

Tarjan

#include<bits/stdc++.h>
#define MAXM 1000005
#define MAXN 1000005
using namespace std;
int n,m;
int head[MAXN],cnt=0;
int dfn[MAXN],low[MAXN],co[MAXN],col=0,top=0,num=0,st[MAXN];
struct Edge{int next,to;}t[MAXM];
void Tarjan(int u)
{
	dfn[u]=low[u]=++num;
	st[++top]=u;
	for (int i=head[u];i;i=t[i].next)
	{
		int v=t[i].to;
		if (!dfn[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}else
		if (!co[v]) low[u]=min(low[u],dfn[v]);
	}
	if (low[u]==dfn[u]) 
	{
		co[u]=++col;
		while (st[top]!=u)
		{
			co[st[top]]=col;
			--top;
		}
		--top;
	}
}
void add(int a,int b)
{
 	t[++cnt].next=head[a];
 	t[cnt].to=b;
 	head[a]=cnt;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
	}
	for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i);
	for (int i=1;i<=n;i++) cout<<co[i]<<endl;
	return 0;
}
/*
6 8
1 3
3 5
5 6
4 6
2 4
1 2
4 1
3 4
*/

SPFA

#include<bits/stdc++.h>
const long long inf=2147483647;
const int maxn=10005;
const int maxm=500005;
using namespace std;
int n,m,s,num_edge=0;
int dis[maxn],vis[maxn],head[maxm];
struct Edge
{
  int next,to,dis;
}edge[maxm]; //结构体表示静态邻接表
void addedge(int from,int to,int dis) //邻接表建图
{ //以下是数据结构书上的标准代码,不懂翻书看解释
  edge[++num_edge].next=head[from]; //链式存储下一条出边
  edge[num_edge].to=to; //当前节点编号
  edge[num_edge].dis=dis; //本条边的距离
  head[from]=num_edge; //记录下一次的出边情况
}
void spfa()
{
  queue<int> q; //spfa用队列,这里用了STL的标准队列
  for(int i=1; i<=n; i++) 
  {
    dis[i]=inf; //带权图初始化
    vis[i]=0; //记录点i是否在队列中,同dijkstra算法中的visited数组
  }
  q.push(s); dis[s]=0; vis[s]=1; //第一个顶点入队,进行标记
  while(!q.empty())
  {
    int u=q.front(); //取出队首
    q.pop(); vis[u]=0; //出队标记
    for(int i=head[u]; i; i=edge[i].next) //邻接表遍历,不多解释了(也可用vector代替)
    {
      int v=edge[i].to; 
      if(dis[v]>dis[u]+edge[i].dis) //如果有最短路就更改
      {
        dis[v]=dis[u]+edge[i].dis;
        if(vis[v]==0) //未入队则入队
        {
          vis[v]=1; //标记入队
          q.push(v);
        }
      }
    }
  }
}
int main()
{
  cin>>n>>m>>s;
  for(int i=1; i<=m; i++)
  {
    int f,g,w;
    cin>>f>>g>>w; 
    addedge(f,g,w); //建图,有向图连一次边就可以了
  }
  spfa(); //开始跑spfa
  for(int i=1; i<=n; i++)
    if(s==i) cout<<0<<" "; //如果是回到自己,直接输出0
      else cout<<dis[i]<<" "; //否则打印最短距离
  return 0;
} //结束

倍增LCA

#include<bits/stdc++.h>
using namespace std;
int tot=0,n,m,s;
int to[1000005],next[1000005],head[1000005];
int deep[1000005],f[1000005][25];
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; 
}
inline void add(int a,int b)
{
	next[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void dfs(int u,int fa)
{
	deep[u]=deep[fa]+1;
	f[u][0]=fa;
	for (int i=1;(1<<i)<=deep[u];i++) f[u][i]=f[f[u][i-1]][i-1];
	for (int e=head[u];e;e=next[e])
	{
		int v=to[e];
		if (v==fa) continue;
		dfs(v,u);
	}
}
inline int LCA(int x,int y)
{
	if (deep[x]<deep[y]) swap(x,y);
	for (int i=20;i>=0;i--) 
	{
		if (deep[f[x][i]]>=deep[y]) x=f[x][i];	
		if (x==y) return x;
	}
	for(int i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];           
    }
    return f[x][0]; 
}
int main()
{
	read(n);read(m);read(s);
	for (int i=1;i<=n-1;i++)
	{
		int a,b;
		read(a);read(b);
		add(a,b);
		add(b,a);
	}
	dfs(s,0);
	for (int i=1;i<=m;i++)
	{
		int a,b;
		read(a);read(b);
		cout<<LCA(a,b)<<endl;
	}
	return 0;
}

Kruskal

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
struct node{int u,v,w;}x[200005];
int fa[5005],ans=0,N,M;
bool flag=0;
bool cmp(node a,node b){return a.w<b.w;}
inline int getfa(int x)
{
	if (x==fa[x]) return x;
	return fa[x]=getfa(fa[x]);
}
void Kruskal()
{
	int cnt=0;
	for (int i=1;i<=M;i++)
	{
		int fx=getfa(x[i].u);
		int fy=getfa(x[i].v);
		if (fx!=fy)
		{
			cnt++;
			fa[fy]=fx;
			ans+=x[i].w;
			if (cnt==N-1){flag=1;cout<<ans<<endl;break;};
		}
	}
	if (flag==0) cout<<"-1"<<endl;
}
int main()
{
	scanf("%d%d",&N,&M);
	for (int i=1;i<=N;i++) fa[i]=i; 
	for (int i=1;i<=M;i++) scanf("%d%d%d",&x[i].u,&x[i].v,&x[i].w);
	sort(x+1,x+M+1,cmp);
	Kruskal();
	return 0;
}

分块

#include<bits/stdc++.h>
using namespace std;
struct block{int l;int r;int tag;}k[1000005];
int num[1000005],a[1000005],N;
void build()
{
	int len=sqrt(N);
	int tot=N/len;
	if (N%len) tot++;
	for (int i=1;i<=tot;i++)
	{
		k[i].l=(i-1)*len+1;
		k[i].r=i*len;
	}
	k[tot].r=N;
	for (int i=1;i<=N;i++) num[i]=(i-1)/len+1;
}
void add(int x,int y,int z)
{
	if (num[x]==num[y]) 
	{
		for (int i=x;i<=y;i++) a[i]+=z;
	}
	else
	{
		for (int i=x;i<=k[num[x]].r;i++) a[i]+=z;
		for (int i=num[x]+1;i<num[y];i++) k[i].tag+=z;
		for (int i=k[num[y]].l;i<=y;i++) a[i]+=z;
	}
}
int ask(int x)
{
	return a[x]+k[num[x]].tag;
}
int main()
{
	scanf("%d",&N);
	for (int i=1;i<=N;i++) scanf("%d",&a[i]);
	build();
	for (int i=1;i<=N;i++)
	{
		int opt,l,r,c;
		scanf("%d%d%d%d",&opt,&l,&r,&c);
		if (opt==0) add(l,r,c);
		else cout<<ask(r)<<endl;
	}
	return 0;
}

换根树剖

#include<bits/stdc++.h>
#define MAXN 500005
#define MAXM 500005
long long n,m,SUMM,r=1,p;
long long seg[MAXN],rev[MAXM],size[MAXN],son[MAXN],top[MAXN],dep[MAXN];
long long sum[4*MAXM],num[MAXN],fa[MAXN],Add[4*MAXN];
long long first[2*MAXM],nex[2*MAXM],go[2*MAXM];
using namespace std;
inline long long query(long long root,long long l,long long r,long long L,long long R)
{
	if (L>r||R<l) return 0;
	if (L<=l&&r<=R) return sum[root]+(r-l+1)*Add[root];  
	long long res=(min(R,r)-max(l,L)+1)*Add[root];
	long long mid=(l+r)/2;
	if (mid>=L) res+=query(root<<1,l,mid,L,R);
	if (mid+1<=R) res+=query(root<<1|1,mid+1,r,L,R);
	return res;
}
inline void change(long long root,long long l,long long r,long long Val,long long pos)
{
	if (pos>r||pos<l) return;
	if (l==r&&r==pos)
	{
		sum[root]=Val;
		return;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
	}
    long long mid=(l+r)/2;
    if (mid>=pos) change(root*2,l,mid,Val,pos);
    if (mid+1<=pos) change(root*2+1,mid+1,r,Val,pos);
    sum[root]=sum[root<<1]+sum[root<<1|1];
}
inline void dfs1(long long u,long long f)
{
	size[u]=1;
	fa[u]=f;
	dep[u]=dep[f]+1;
	for (long long e=first[u];e;e=nex[e])
	{
		long long v=go[e];
		if (v==f) continue;
		dfs1(v,u);
		size[u]+=size[v];
		if (size[v]>size[son[u]]) son[u]=v;
	}
}
inline void dfs2(long long u,long long f)
{
	if (son[u])
	{         
     seg[son[u]]=++seg[0];
     top[son[u]]=top[u];
	 rev[seg[0]]=son[u];
	 dfs2(son[u],u);
	}
	for (long long e=first[u];e;e=nex[e])
	{
		long long v=go[e];
		if (!top[v])
		{
			seg[v]=++seg[0];
			rev[seg[0]]=v;
			top[v]=v;
			dfs2(v,u);
		}
	}
}
inline void modify(long long root,long long maxl,long long maxr,long long l,long long r,long long v)
{
    if (maxl>=l&&maxr<=r){Add[root]+=v;return;}
    sum[root]+=(min(maxr,r)-max(maxl,l)+1)*v;
    long long mid=(maxl+maxr)/2;
    if (l<=mid) modify(root*2,maxl,mid,l,r,v);
    if (mid<r) modify(root*2+1,mid+1,maxr,l,r,v);
}
inline void build(long long root,long long l,long long r)
{
	long long mid=(l+r)/2;
	if (l==r) 
	{
		sum[root]=num[rev[l]];
		return;
	}
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	sum[root]=sum[root<<1]+sum[root<<1|1];
}
long long tot=0;
inline void add(long long x,long long y)
{
	nex[++tot]=first[x];
	go[tot]=y;
	first[x]=tot;
}
inline void insert(long long x,long long y){add(x,y);add(y,x);}
inline long long read()
{
    char chr;
    long long f=1;
    while (((chr=getchar())<'0')||(chr>'9')){if (chr=='-'){f=-1;}}
    long long res=chr-'0';
    while (((chr=getchar())>='0')&&(chr<='9')){res=res*10+chr-'0';}
    return res*f;
}
long long LCA(long long u,long long v)
{
    long long ans=0;
    while (top[u]!=top[v]){
        if (dep[top[u]]<dep[top[v]]){
            swap(u,v);
        }
        u=fa[top[u]];
    }
    if (dep[u]>dep[v]){
        swap(u,v);
    }
    return u;
}
long long LCA2(long long u,long long v){return max(LCA(u,v),max(LCA(u,r),LCA(v,r)));}
int get(int u,int v)
{
    while (top[u]!=top[v])
	{
        u=top[u];
        if (fa[u]==v) return u;
        u=fa[u];
    }
    return son[v];
}
int main()
{
 n=read(); m=read();
 for (long long i=1;i<=n;i++) num[i]=read();
 for (long long i=1;i<n;i++) insert(read(),read());
 dfs1(r,r);
 seg[0]=seg[r]=1;rev[1]=r;top[r]=r;
 dfs2(r,r);
 build(1,1,seg[0]);
 for (int i=1;i<=m;i++)
 {
    long long opt=read(),u,v,x;
    if (opt==1) {r=read();continue;}//换根 
    if (opt==2) //子树加权 
    {
        u=read();v=read();x=read();
        long long now=LCA2(u,v);
        //cout<<"LCA "<<u<<" "<<v<<"="<<now<<endl;
        if (now==r){modify(1,1,seg[0],seg[1],seg[1]+size[1]-1,x);continue;}
		if (LCA(now,r)==now) {long long tmp=get(r,now);modify(1,1,seg[0],seg[1],seg[1]+size[1]-1,x);modify(1,1,seg[0],seg[tmp],seg[tmp]+size[tmp]-1,-x);}else modify(1,1,seg[0],seg[now],seg[now]+size[now]-1,x);
    }
	if (opt==3)//子树求和 
	{
		u=read();
		if (r==u) {cout<<query(1,1,seg[0],seg[1],seg[1]+size[1]-1)<<endl;continue;}
		if (LCA(u,r)==u){long long tmp=get(r,u);cout<<query(1,1,seg[0],seg[1],seg[1]+size[1]-1)-query(1,1,seg[0],seg[tmp],seg[tmp]+size[tmp]-1)<<endl;}else cout<<query(1,1,seg[0],seg[u],seg[u]+size[u]-1)<<endl;
		//if (LCA(u,r)==u) cout<<"Fuckever"<<" "<<query(1,1,seg[0],seg[u]+1,seg[u]+size[u]-1)<<endl;
	}
 }
 return 0;	
}




trie

#include<bits/stdc++.h>
#define MAXN 1005
using namespace std;
int ch[MAXN][10005],tot=0,n,m;
bool f[MAXN];
void insert(char s[])
{
	int len=strlen(s),p=1;
	for(int i=0;i<len;i++)
	{
		int t=s[i]-'a';
		if(ch[p][t]==0)
		{
			ch[p][t]=++tot;
			p=ch[p][t];
		}
	    f[p]=1;
	}
}
int find(char s[])
{
	int p=1,len=strlen(s);
	for(int i=0;i<len;i++)
	{
		int c=s[i]-'a';
		if(ch[p][c]==0)	return 0;
		p=ch[p][c];
	}
	return 1;
}
int main()
{
 	cin>>n>>m;
 	for (int i=1;i<=n;i++) 
 	{
 		char s[1005];
 		cin>>s;
 		insert(s);
	}
	for (int i=1;i<=m;i++)
	{
		char s[1005];
		cin>>s;
		if (find(s)) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
} 

CDQ三维偏序

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
struct node{int a,b,c,cnt,ans;};
int N,K,Tot=0,F[MAXN];
node Tmp[MAXN],Val[MAXN];
bool Cmp_1(node x,node y){if (x.a!=y.a) return x.a<y.a;else if (x.b!=y.b) return x.b<y.b;else return x.c<y.c;}
bool Cmp_2(node x,node y){if (x.b!=y.b) return x.b<y.b;return x.c<y.c;};
void Read(int &x)
{
    int f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
struct Seg_Tree
{
	int Tree[800010];
    void Insert(int root,int l,int r,int num,int cnt)
    {
        if (l==r) {Tree[root]+=cnt;return;}
        int Mid=l+r>>1;
        if (num<=Mid) Insert(root<<1,l,Mid,num,cnt);else Insert(root<<1|1,Mid+1,r,num,cnt);
        Tree[root]=Tree[root<<1]+Tree[root<<1|1];
    }
    int ask(int root,int l,int r,int quel,int quer)
    {
        if (l>quer||r<quel) return 0;
		if (quel<=l&&r<=quer) return Tree[root];
		int Mid=l+r>>1;
		return ask(root<<1,l,Mid,quel,quer)+ask(root<<1|1,Mid+1,r,quel,quer); 
    }
}seg;
void CDQ(int l,int r)
{
	if (l==r) return;
    int Mid=l+r>>1;
    CDQ(l,Mid); CDQ(Mid+1,r);
    sort(Val+l,Val+Mid+1,Cmp_2); sort(Val+Mid+1,Val+r+1,Cmp_2);
    int j=l;
    for (int i=Mid+1;i<=r;i++)
    {
        while (j<=Mid&&Val[j].b<=Val[i].b) seg.Insert(1,1,K,Val[j].c,Val[j].cnt),j++;
        Val[i].ans+=seg.ask(1,1,K,1,Val[i].c);
    }
	//cout<<"OK"<<endl;
    for (int i=l;i<j;i++) seg.Insert(1,1,K,Val[i].c,-Val[i].cnt);
}
int main()
{
//	freopen("testdata.in","r",stdin);
//	freopen("testdata.out","w",stdout);
    Read(N);Read(K);
    for (int i=1;i<=N;i++) Read(Tmp[i].a),Read(Tmp[i].b),Read(Tmp[i].c),Tmp[i].cnt=1;    
    sort(Tmp+1,Tmp+N+1,Cmp_1);
    for (int i=1;i<=N;i++)
    {
        if (Tmp[i].a==Tmp[i-1].a&&Tmp[i].b==Tmp[i-1].b&&Tmp[i].c==Tmp[i-1].c) Val[Tot].cnt++;
        else Val[++Tot]=Tmp[i];
    }
    //for (int i=1;i<=Tot;i++) printf("%d %d %d %d\n",Val[i].a,Val[i].b,Val[i].c,Val[i].cnt);
	CDQ(1,Tot);
    for (int i=1;i<=Tot;i++) F[Val[i].ans+Val[i].cnt-1]+=Val[i].cnt;
    for (int i=0;i<N;i++) cout<<F[i]<<endl;
    //cout<<endl;
    //for (int i=1;i<=Tot;i++) cout<<Val[i].ans<<endl;
    return 0;
}

对拍

@echo off
:loop
MakeData.exe
a.exe
b.exe
fc a.out b.out
if not errorlevel 1 goto loop
pause
:end

树链剖分

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define MAXN 101000
#define MAXM 624000
int n,m,SUMM,MAXX;
int seg[MAXN],rev[MAXM],size[MAXN],son[MAXN],top[MAXN],dep[MAXN];
int sum[MAXM],num[MAXN],fa[MAXN],Max[MAXN];
int first[MAXM],next[MAXM],go[MAXM];
using namespace std;
inline void query(int root,int l,int r,int L,int R)
{
	if (L>r||R<l) return;
	if (L<=l&&r<=R) 
	{
		SUMM+=sum[root];
		MAXX=max(MAXX,Max[root]);
		return; 
	} 
	int mid=(l+r)/2,res=0;
	if (mid>=L) query(root<<1,l,mid,L,R);
	if (mid+1<=R) query(root<<1|1,mid+1,r,L,R);
}//不多讲,还是线段树
inline void change(int root,int l,int r,int Val,int pos)
{
	if (pos>r||pos<l) return;
	if (l==r&&r==pos)
	{
		sum[root]=Val;
		Max[root]=Val;
		return;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
	}
    int mid=(l+r)/2;
    if (mid>=pos) change(root*2,l,mid,Val,pos);
    if (mid+1<=pos) change(root*2+1,mid+1,r,Val,pos);
    sum[root]=sum[root<<1]+sum[root<<1|1];
	Max[root]=max(Max[root<<1],Max[root<<1|1]);
}//不多讲,就是线段树
inline void dfs1(int u,int f)//u为当前点,f为父节点
{
	int e;
	size[u]=1;//自己是自己子树的一个部分
	fa[u]=f;//肯定的
	dep[u]=dep[f]+1;//深度比父亲大1
	for (int e=first[u];e;e=next[e])//遍历所有与u相连的边
	{
		int v=go[e];//此边到达的点
		if (v==f) continue;//不能是父亲,要不然走上面回去了
		dfs1(v,u);//让u当v的父亲再dfs
		size[u]+=size[v];//子树u的size=dep[u]-1的所有直连子节点的子树size之和
		if (size[v]>size[son[u]]) son[u]=v;//选出一个size最大的直连子节点做重儿子
	}
}
inline void dfs2(int u,int f)
{
	int e;
	if (son[u])//先走重儿子,使重路径在线段树中位置连续
	{          //根在这无法赋值,要在主程序中赋值
     seg[son[u]]=++seg[0];//seg[0]用于计数,将重儿子放到线段中
     top[son[u]]=top[u];//父亲的重链顶端也是重儿子的重链顶端
	 rev[seg[0]]=son[u];//使线段树第x个位置对应树中的节点编号,rev[seg[x]]=x;
	 dfs2(son[u],u);//往重儿子处dfs
	}
	for (e=first[u];e;e=next[e])
	{
		int v=go[e];
		if (!top[v])//没有被遍历过,也就是不是u的重儿子或父亲
		{
			seg[v]=++seg[0];//同理,将v下放到线段中
			rev[seg[0]]=v;//使线段树第x个位置对应树中的节点编号,rev[seg[x]]=x;
			top[v]=v;//u,v为轻链,v定为重链开头,也就是top
			dfs2(v,u);
		}
	}
}
inline void build(int root,int l,int r)
{
	int mid=(l+r)/2;
	if (l==r) 
	{
		Max[root]=sum[root]=num[rev[l]];
		return;
	}
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	sum[root]=sum[root<<1]+sum[root<<1|1];
	Max[root]=max(Max[root<<1],Max[root<<1|1]);
}//对着线段建树
int tot=0;
inline void add(int x,int y)
{
	next[++tot]=first[x];
	go[tot]=y;
	first[x]=tot;
}
inline void insert(int x,int y){add(x,y);add(y,x);}
inline void ask(int x,int y)
{
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if (dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
		query(1,1,seg[0],seg[fx],seg[x]);//这时的seg[0]也就成为了线段总长
	    x=fa[fx]; fx=top[x];
	}
	if (dep[x]>dep[y]) swap(x,y);
	query(1,1,seg[0],seg[x],seg[y]);//此时seg[x]为lca(x,y)
}//LCA式路径询问
inline int read()
{
    char chr;
    int f=1;
    while (((chr=getchar())<'0')||(chr>'9')){if (chr=='-'){f=-1;}}
    int res=chr-'0';
    while (((chr=getchar())>='0')&&(chr<='9')){res=res*10+chr-'0';}
    return res*f;
}
int main()
{
 //freopen("count1.in","r",stdin);
 //freopen("count1.out","w",stdout);
 n=read();
 for (int i=1;i<n;i++) insert(read(),read());//读入边
 for (int i=1;i<=n;i++) num[i]=read();//点的权值
 dfs1(1,0);//第一遍dfs,可找出fa,dep,size,son
 seg[0]=seg[1]=top[1]=rev[1]=1;
 dfs2(1,0);
 build(1,1,seg[0]);
 m=read();
 for (int i=1;i<=m;i++)
 {
    int u,v;
 	string s;
 	cin>>s;
 	u=read();v=read(); 
 	if (s=="CHANGE") change(1,1,seg[0],v,seg[u]);
 	else
 	{
 	 SUMM=0;
 	 MAXX=-214748364;
	 ask(u,v);
 	 if (s=="QMAX") cout<<MAXX<<endl;
	 if (s=="QSUM") cout<<SUMM<<endl;  	
	}
 }
 return 0;	
}

区间+子树修改查询树链剖分

#include<bits/stdc++.h>
#define MAXN 501000
#define MAXM 1224000
long long n,m,SUMM,r,p;
long long seg[MAXN],rev[MAXM],size[MAXN],son[MAXN],top[MAXN],dep[MAXN];
long long sum[MAXM],num[MAXN],fa[MAXN],Add[MAXN];
long long first[MAXM],next[MAXM],go[MAXM];
using namespace std;
inline long long query(long long root,long long l,long long r,long long L,long long R)
{
	if (L>r||R<l) return 0;
	if (L<=l&&r<=R) return sum[root]+(r-l+1)*Add[root];  
	long long res=(min(R,r)-max(l,L)+1)*Add[root];
	long long mid=(l+r)/2;
	if (mid>=L) res+=query(root<<1,l,mid,L,R);
	if (mid+1<=R) res+=query(root<<1|1,mid+1,r,L,R);
	return res;
}//不多讲,还是线段树
inline void change(long long root,long long l,long long r,long long Val,long long pos)
{
	if (pos>r||pos<l) return;
	if (l==r&&r==pos)
	{
		sum[root]=Val;
		return;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
	}
    long long mid=(l+r)/2;
    if (mid>=pos) change(root*2,l,mid,Val,pos);
    if (mid+1<=pos) change(root*2+1,mid+1,r,Val,pos);
    sum[root]=sum[root<<1]+sum[root<<1|1];
}//不多讲,就是线段树
inline void dfs1(long long u,long long f)//u为当前点,f为父节点
{
	long long e;
	size[u]=1;//自己是自己子树的一个部分
	fa[u]=f;//肯定的
	dep[u]=dep[f]+1;//深度比父亲大1
	for (long long e=first[u];e;e=next[e])//遍历所有与u相连的边
	{
		long long v=go[e];//此边到达的点
		if (v==f) continue;//不能是父亲,要不然走上面回去了
		dfs1(v,u);//让u当v的父亲再dfs
		size[u]+=size[v];//子树u的size=dep[u]-1的所有直连子节点的子树size之和
		if (size[v]>size[son[u]]) son[u]=v;//选出一个size最大的直连子节点做重儿子
	}
}
inline void dfs2(long long u,long long f)
{
	long long e;
	if (son[u])//先走重儿子,使重路径在线段树中位置连续
	{          //根在这无法赋值,要在主程序中赋值
     seg[son[u]]=++seg[0];//seg[0]用于计数,将重儿子放到线段中
     top[son[u]]=top[u];//父亲的重链顶端也是重儿子的重链顶端
	 rev[seg[0]]=son[u];//使线段树第x个位置对应树中的节点编号,rev[seg[x]]=x;
	 dfs2(son[u],u);//往重儿子处dfs
	}
	for (e=first[u];e;e=next[e])
	{
		long long v=go[e];
		if (!top[v])//没有被遍历过,也就是不是u的重儿子或父亲
		{
			seg[v]=++seg[0];//同理,将v下放到线段中
			rev[seg[0]]=v;//使线段树第x个位置对应树中的节点编号,rev[seg[x]]=x;
			top[v]=v;//u,v为轻链,v定为重链开头,也就是top
			dfs2(v,u);
		}
	}
}
inline void modify(long long root,long long maxl,long long maxr,long long l,long long r,long long v)
{
    if (maxl>=l&&maxr<=r){Add[root]+=v;return;}
    sum[root]+=(min(maxr,r)-max(maxl,l)+1)*v;
    long long mid=(maxl+maxr)/2;
    if (l<=mid) modify(root*2,maxl,mid,l,r,v);
    if (mid<r) modify(root*2+1,mid+1,maxr,l,r,v);
}
inline void build(long long root,long long l,long long r)
{
	long long mid=(l+r)/2;
	if (l==r) 
	{
		sum[root]=num[rev[l]];
		return;
	}
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	sum[root]=sum[root<<1]+sum[root<<1|1];
}//对着线段建树
long long tot=0;
inline void add(long long x,long long y)
{
	next[++tot]=first[x];
	go[tot]=y;
	first[x]=tot;
}
inline void insert(long long x,long long y){add(x,y);add(y,x);}
inline void ask(long long x,long long y)
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if (dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
        SUMM+=query(1,1,seg[0],seg[fx],seg[x]);//这时的seg[0]也就成为了线段总长
        SUMM%=p;
        x=fa[fx]; fx=top[x];
    }
    if (dep[x]>dep[y]) swap(x,y);
    SUMM+=query(1,1,seg[0],seg[x],seg[y]);//此时seg[x]为lca(x,y)
    SUMM%=p;
}//LCA式路径询问
inline void updata(long long x,long long y,long long z)
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if (dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
        modify(1,1,seg[0],seg[fx],seg[x],z);//这时的seg[0]也就成为了线段总长
        x=fa[fx]; fx=top[x];
    }
    if (dep[x]>dep[y]) swap(x,y);
    modify(1,1,seg[0],seg[x],seg[y],z);//此时seg[x]为lca(x,y)
}//LCA式路径询问
inline long long read()
{
    char chr;
    long long f=1;
    while (((chr=getchar())<'0')||(chr>'9')){if (chr=='-'){f=-1;}}
    long long res=chr-'0';
    while (((chr=getchar())>='0')&&(chr<='9')){res=res*10+chr-'0';}
    return res*f;
}
void print(long long x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
int main()
{
 //freopen("count1.in","r",stdin);
 //freopen("count1.out","w",stdout);
 n=read(); m=read(); r=read(); p=read();
 for (long long i=1;i<=n;i++) num[i]=read();//点的权值
 for (long long i=1;i<n;i++) insert(read(),read());//读入边
 dfs1(r,r);//第一遍dfs,可找出fa,dep,size,son
 seg[0]=seg[r]=1;
 rev[1]=r;
 top[r]=r;
 dfs2(r,r);
 build(1,1,seg[0]);
 for (long long i=1;i<=m;i++)
 {
    SUMM=0;
    long long kind=read();
    if (kind==1) 
	{
	 long long x,y,z;
	 z%=p;
	 x=read();y=read();z=read();
	 updata(x,y,z);
	}
    if (kind==2) 
	{
	 long long x,y;
	 x=read();y=read();
	 ask(x,y);
	 print(SUMM%p);
	 putchar('\n');
	}
    else
    {
    if (kind==3) 
	{
	 long long x,y;
	 x=read();y=read();
	 y%=p;
	 modify(1,1,seg[0],seg[x],seg[x]+size[x]-1,y);	
	}
	if (kind==4) 
	{
	 long long x;
	 x=read();
	 print(query(1,1,seg[0],seg[x],seg[x]+size[x]-1)%p);
	 putchar('\n');
	}
	}
 }
 return 0;	
}

标记永久化线段树

#include<bits/stdc++.h>
#define Maxn 100005
#define LL long long
using namespace std;
inline void Read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
LL N,M,num[Maxn],id=0,rt,mark[Maxn*40];
struct node{LL ls,rs,sum;}tree[Maxn*40];
inline void build(LL &root,LL l,LL r)
{
	if (!root) root=++id;
	if (l==r) {tree[root].sum=num[l];return;}
	LL mid=l+r>>1;
	build(tree[root].ls,l,mid);
	build(tree[root].rs,mid+1,r);
	tree[root].sum=tree[tree[root].ls].sum+tree[tree[root].rs].sum;
} 
inline void modify(LL root,LL l,LL r,LL ql,LL qr,LL x)
{
	tree[root].sum+=(qr-ql+1)*x;
	if (l==ql&&r==qr) {mark[root]+=x;return;}
	LL mid=l+r>>1;
	if (ql<=mid&&qr>mid) modify(tree[root].ls,l,mid,ql,mid,x),modify(tree[root].rs,mid+1,r,mid+1,qr,x);  
	if (qr<=mid) modify(tree[root].ls,l,mid,ql,qr,x);
	if (ql>mid) modify(tree[root].rs,mid+1,r,ql,qr,x);
}
inline LL query(LL root,LL l,LL r,LL ql,LL qr,LL tag)
{
	if (ql==l&&qr==r) {return tree[root].sum+tag*(r-l+1);}
	LL mid=l+r>>1;
	if (ql<=mid&&qr>mid) return query(tree[root].ls,l,mid,ql,mid,tag+mark[root])+query(tree[root].rs,mid+1,r,mid+1,qr,tag+mark[root]);  
	if (qr<=mid) return query(tree[root].ls,l,mid,ql,qr,tag+mark[root]);
	if (ql>mid) return query(tree[root].rs,mid+1,r,ql,qr,tag+mark[root]);
}
int main()
{
	Read(N),Read(M);
	for (int i=1;i<=N;i++) Read(num[i]); 
	build(rt,1,N);
	while (M--)
	{
		LL opt,x,y,k;
		Read(opt);
		if (opt==1)
		{
			Read(x),Read(y),Read(k);
			modify(rt,1,N,x,y,k);
		} 
		else
		{
			Read(x);Read(y);
			cout<<query(rt,1,N,x,y,0)<<endl; 
		} 
	}
	return 0;	
} 

中国剩余定理Crt

#include<bits/stdc++.h>
using namespace std;
long long n,b[15],w[15],ans=0,m=1,d,x,y;
void ex_gcd(long long a,long long b,long long d,long long &x,long long &y) {
	if (b==0) x=1,y=0,d=a;
	else	
	{
		ex_gcd(b,a%b,d,x,y);
		long long tmp=x;
		x=y;
		y=tmp-a/b*y;
	}
}
void Crt() {
	for (long long i=1; i<=n; i++) m*=w[i];
	for (long long i=1; i<=n; i++)
	{
		long long u=m/w[i];
		d=0;
		x=0;
		y=0;
		ex_gcd(w[i],u,d,x,y);
		ans=ans+y*u*b[i];
	}
	cout<<(ans%m+m)%m<<endl;
}
int main() {
	scanf("%lld",&n);
	for (long long i=1; i<=n; i++) scanf("%lld%lld",&b[i],&w[i]);
	Crt();
	return 0;
}

主席树

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int N,M,a[2000005],b[2000005],cnt,rt[8000005];
struct node{int sum,l,r;}T[8000005];
void build(int &root,int l,int r)
{
    root=++cnt;
    if (l==r) return;
    int mid=(l+r)/2;
    build(T[root].l,l,mid);
    build(T[root].r,mid+1,r);
} 
void update(int pre,int &root,int l,int r,int k)
{
    root=++cnt;
    T[root].l=T[pre].l;T[root].sum=T[pre].sum+1;T[root].r=T[pre].r;
    if (l>=r) return;
    int mid=(l+r)/2;
    if (k<=mid) update(T[pre].l,T[root].l,l,mid,k);
    else update(T[pre].r,T[root].r,mid+1,r,k);
}
int query(int x,int y,int l,int r,int k)
{
    if (l>=r) return l;
    int sum=T[T[y].l].sum-T[T[x].l].sum;
    int mid=(l+r)/2;
    if (k<=sum) return query(T[x].l,T[y].l,l,mid,k);
    else return query(T[x].r,T[y].r,mid+1,r,k-sum);
}
int main()
{
    memset(rt,0,sizeof(rt));
    scanf("%d%d",&N,&M);
    for (int i=1;i<=N;i++) scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+N+1);
    int tot=unique(b+1,b+N+1)-b-1;
    build(rt[0],1,tot);
    for (int i=1;i<=N;i++)
    {
        int x=lower_bound(b+1,b+tot+1,a[i])-b;
        update(rt[i-1],rt[i],1,tot,x); 
    }
    for (int i=1;i<=M;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        cout<<b[query(rt[x-1],rt[y],1,tot,z)]<<endl;
    }
    return 0;	
} 

treap

#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
int tot,root,n;
struct node
{
  int l,r,size,val,cnt,priority;
}tree[MAXN];
void updata(int x)//没讲,就是更新size值,可以讲,但没必要 
{
 tree[x].size=tree[tree[x].l].size+tree[x].cnt+tree[tree[x].r].size;	
} 
inline void rotate_right(int &x)
{
  int y=tree[x].l;
  tree[x].l=tree[y].r;
  tree[y].r=x;
  tree[y].size=tree[x].size;
  updata(x);
  x=y;
}
inline void rotate_left(int &x)
{
  int y=tree[x].r;
  tree[x].r=tree[y].l;
  tree[y].l=x;
  tree[y].size=tree[x].size;
  updata(x);
  x=y;
}
inline void insert(int &x,const int &num)//x是位置,num是插入值 
{
  if (!x)//插入 
  {
    x=++tot; tree[x].val=num; tree[x].priority=rand();
    tree[x].size=tree[x].cnt=1; tree[x].l=tree[x].r=0;
    return;
  }
  else tree[x].size++;
  //找地方插入 
  if (tree[x].val==num) tree[x].cnt++;//重复的话加cnt 
  else if (num<tree[x].val)//满足平衡树性质 
  {
    insert(tree[x].l,num);
    if (tree[tree[x].l].priority<tree[x].priority) rotate_right(x);//不满足小根堆性质,转一转 
  }
  else
  {
    insert(tree[x].r,num);
    if (tree[tree[x].r].priority<tree[x].priority) rotate_left(x);//不满足小根堆性质,转一转 
  }
}
inline void del(int &x,const int &num)
{
  //删除 
  if (tree[x].val==num) 
  {
    if (tree[x].cnt>1) tree[x].cnt--,tree[x].size--;//如果有重复就去个重就好了 
    else if (!tree[x].l||!tree[x].r) x=tree[x].l+tree[x].r;//如果叶节点不为2,那么就删掉此点连到唯一的叶节点上 
    else if (tree[tree[x].l].priority<tree[tree[x].r].priority) rotate_right(x),del(x,num);//左右儿子都有,先旋转再删除 
    else rotate_left(x),del(x,num);
    return;
  }
  tree[x].size--;//儿子没了,爸爸大小肯定要减
  //找地方删 
  if (num<tree[x].val) del(tree[x].l,num);
  else del(tree[x].r,num);
  return;
}
inline int before(const int &num)
{
  int x=root,res=-2e9;
  while (x)
  {
    if (tree[x].val<num) res=tree[x].val,x=tree[x].r;//比查询值小 
    else x=tree[x].l;
  }
  return res;
}
inline int after(const int &num)
{
  int x=root,res=-2e9;
  while (x)
  {
    if (tree[x].val>num) res=tree[x].val,x=tree[x].l;//比查询值大 
    else x=tree[x].r;
  }
  return res;
}
inline int kth(int k)
{
  int x=root;
  while (x)
  {
    if (tree[tree[x].l].size<k&&tree[tree[x].l].size+tree[x].cnt>=k) return tree[x].val;//x就是第k大 
    if (tree[tree[x].l].size>=k) x=tree[x].l;//x比第k大大,找左儿子 
    else k-=tree[tree[x].l].size+tree[x].cnt,x=tree[x].r;//x比第k大小,找右儿子,累加排名 
  }
  return 0;
}
inline int rank(const int &num)
{
  int x=root,res=0;
  while (x)
  {
    if (num==tree[x].val) return res+tree[tree[x].l].size+1;
    if (num<tree[x].val) x=tree[x].l;
    else res+=tree[tree[x].l].size+tree[x].cnt,x=tree[x].r;
  }
  return res;      
}
inline int read()
{
    char chr;
    int f=1;
    while (((chr=getchar())<'0')||(chr>'9')){if (chr=='-'){f=-1;}}
    int res=chr-'0';
    while (((chr=getchar())>='0')&&(chr<='9')){res=res*10+chr-'0';}
    return res*f;
}
inline void write(int x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
int main()
{
  n=read();
  for (int i=1;i<=n;i++)
  {
  	int opt,x;
  	opt=read();x=read();
  	if (opt==1) insert(root,x);
  	if (opt==2) del(root,x);
  	if (opt==3) write(rank(x)),putchar('\n');
  	if (opt==4) write(kth(x)),putchar('\n');
  	if (opt==5) write(before(x)),putchar('\n');
  	if (opt==6) write(after(x)),putchar('\n');
  }
  return 0;
}

线段树合并

int merge(int x,int y)
{
    if (!x) return y;
    if (!y) return x;
    k[x].l=merge(k[x].l,k[y].l);
    k[x].r=merge(k[x].r,k[y].r);
    k[x].sum=k[k[x].l].sum+k[k[x].r].sum;
    return x;
}

可持久化trie

inline void insert(int pre,int &root,int i,int x)
{
    root=++cnt;
    t[root]=t[pre];
    t[root].size++;
	if (i<0) return;
    if ((x>>i)&1) insert(t[pre].rs,t[root].rs,i-1,x);
    else insert(t[pre].ls,t[root].ls,i-1,x);
}
inline int query(int pre,int root,int i,int x)
{
    if (i<0) return 0;
    if ((x>>i)&1)
    {
    	if (t[t[root].ls].size-t[t[pre].ls].size>0) return query(t[pre].ls,t[root].ls,i-1,x)+(1<<i);
    	else return query(t[pre].rs,t[root].rs,i-1,x);
	}
    else
    {
    	if (t[t[root].rs].size-t[t[pre].rs].size>0) return query(t[pre].rs,t[root].rs,i-1,x)+(1<<i);
    	else return query(t[pre].ls,t[root].ls,i-1,x);
    }
}

FFT

#include<bits/stdc++.h>
#define Pi acos(-1.0)
#define Maxn 10000005
using namespace std;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();
	return ret*f;
}
struct node
{
	double x,y;
	friend inline node operator + (const node x,const node y){return (node){x.x+y.x,x.y+y.y};}
	friend inline node operator - (const node x,const node y){return (node){x.x-y.x,x.y-y.y};}
	friend inline node operator * (const node x,const node y){return (node){x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x};}
}a[Maxn];
int n,m,limit=1,r[Maxn],Log;
inline void FFT(node *A,int type)
{
	for(int i=0;i<limit;i++) if(i<r[i]) swap(A[i],A[r[i]]);
	for(int mid=1;mid<limit;mid<<=1){
		node Wn=(node){cos(Pi/mid),type*sin(Pi/mid)};
		for(int R=mid<<1,L=0;L<limit;L+=R)
        {
			node w=(node){1,0};
			for(int k=0;k<mid;k++,w=w*Wn)
            {
				node x=A[L+k],y=w*A[L+mid+k];
				A[L+k]=x+y,A[L+mid+k]=x-y;
			}
		}
	}
}
int main()
{
	n=read(),m=read();	
	for(int i=0;i<=n;i++) a[i].x=(double)read();for(int i=0;i<=m;i++) a[i].y=(double)read();
	while(limit<=n+m) limit<<=1,Log++;for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(Log-1));
	FFT(a,1);for(int i=0;i<limit;i++) a[i]=a[i]*a[i];FFT(a,-1);
	for(int i=0;i<=n+m;i++) printf("%d ",(int)(a[i].y/(limit<<1)+0.5));
	return 0;
}

Splay

#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
	x*=f;
}
LL n,m,rt,id=0;
struct tree{LL size,cnt,ch[2],fa,val;}t[1500005];
struct Splay
{
	inline void update(LL x){t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;}
	inline LL identify(LL x){if (t[t[x].fa].ch[0]==x) return 0;if (t[t[x].fa].ch[1]==x) return 1;return -1;}
	inline void connect(LL x,LL y,LL opt){t[x].fa=y;if (opt==-1) return;t[y].ch[opt]=x;}
	inline void rotate(LL x){LL Fa=t[x].fa,FaFa=t[Fa].fa,optx=identify(x),opty=identify(Fa);connect(t[x].ch[optx^1],Fa,optx);connect(Fa,x,optx^1);connect(x,FaFa,opty);update(Fa),update(x);}
	inline void splay(LL x,LL y)
	{
		while (t[x].fa!=y)
		{
			if (t[t[x].fa].fa!=y) if (identify(x)==identify(t[x].fa)) rotate(t[x].fa);else rotate(x);
			rotate(x);
		}
		if (!y) rt=x;
	}
	inline void Find(LL x)
	{
		LL u=rt;
		if (!u) return;
		while (t[u].ch[x>t[u].val]&&x!=t[u].val) u=t[u].ch[x>t[u].val];
		splay(u,0);
	}
	inline void insert(LL x)
	{
		LL u=rt,Fa=0;
		while (u&&t[u].val!=x){Fa=u;u=t[u].ch[x>t[u].val];}
		if (u) t[u].cnt++;
		else{u=++id;if (Fa) t[Fa].ch[x>t[Fa].val]=u;t[u].ch[0]=t[u].ch[1]=0,t[u].fa=Fa,t[u].val=x,t[u].cnt=1,t[u].size=1;}
		splay(u,0);
	}
	inline LL Pre(LL x)
	{
		Find(x);
		LL u=t[rt].ch[0];
		while (t[u].ch[1]) u=t[u].ch[1];
		return u;
	}
	inline LL Aft(LL x){Find(x);LL u=t[rt].ch[1];while (t[u].ch[0]) u=t[u].ch[0];return u;}
	inline void Delete(LL x)
	{
		LL Bef=Pre(x),Nex=Aft(x);splay(Bef,0),splay(Nex,rt);LL del_wz=t[t[rt].ch[1]].ch[0];
		if (t[del_wz].cnt>1) {t[del_wz].cnt--;splay(del_wz,0);}else t[t[rt].ch[1]].ch[0]=0,t[t[t[rt].ch[1]].ch[0]].fa=0;
	}
	inline LL K_th(LL x)
	{
       LL u=rt;
       if(t[u].size<x) return 0;
       while(1){if(x>t[t[u].ch[0]].size+t[u].cnt) x-=t[t[u].ch[0]].size+t[u].cnt,u=t[u].ch[1];else{if(t[t[u].ch[0]].size>=x)  u=t[u].ch[0];else return u;} }
	}
}T;
int main()
{
	LL lastans=0,Ans=0;
	T.insert(-2147483647);
    T.insert(2147483647);
    read(n);read(m);
    for (LL a,i=1;i<=n;i++) read(a),T.insert(a);
    while(m--)
       {
            LL opt,x;
            read(opt),read(x);
            x^=lastans;
            if(opt==1) T.insert(x);
            if(opt==2) T.Delete(x);
        	if(opt==3) T.insert(x),T.Find(x),lastans=t[t[rt].ch[0]].size,T.Delete(x),Ans^=lastans;
            if(opt==4) lastans=t[T.K_th(x+1)].val,Ans^=lastans;
        	if(opt==5) T.insert(x),lastans=t[T.Pre(x)].val,T.Delete(x),Ans^=lastans;
            if(opt==6) T.insert(x),lastans=t[T.Aft(x)].val,T.Delete(x),Ans^=lastans;
       }
       cout<<Ans<<endl;
       return 0;
}

LCT

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,m;
inline void read(LL &x){LL f=1;x=0;char ch=getchar();while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}x*=f;}
struct LCT
{
	struct tree{LL ch[2],fa,val,sum,tag;}t[1000005];
	inline LL identify(LL x){if (t[t[x].fa].ch[0]==x) return 0;if (t[t[x].fa].ch[1]==x) return 1;return -1;}
	inline void connect(LL x,LL y,LL opt){t[x].fa=y;if (opt==-1) return;t[y].ch[opt]=x;}
	inline void pushup(LL x){t[x].sum=t[t[x].ch[0]].sum^t[t[x].ch[1]].sum^t[x].val;}
	inline void pushdown(LL x){if(t[x].tag){swap(t[x].ch[0],t[x].ch[1]);t[t[x].ch[0]].tag^=1;t[t[x].ch[1]].tag^=1;t[x].tag=0;}}
	inline void pushall(LL x){if(identify(x)!=-1)pushall(t[x].fa);pushdown(x);}
	inline void rotate(LL x){LL Fa=t[x].fa,FaFa=t[Fa].fa,optx=identify(x),opty=identify(Fa);connect(t[x].ch[optx^1],Fa,optx);connect(Fa,x,optx^1);connect(x,FaFa,opty);pushup(Fa),pushup(x);}
	inline void splay(LL x){pushall(x);while (identify(x)!=-1){if (identify(t[x].fa)!=-1){if (identify(x)==identify(t[x].fa)) rotate(t[x].fa);else rotate(x);}rotate(x);}}
	inline void access(LL x){LL las=0;while (x){splay(x);t[x].ch[1]=las;pushup(x);las=x;x=t[x].fa;}}
	inline void make_root(LL x){access(x),splay(x),t[x].tag^=1,pushdown(x);}
	inline void split(LL x,LL y){make_root(x);access(y);splay(y);}
	inline LL findroot(LL x){access(x);splay(x);while(t[x].ch[0]){pushdown(x);x=t[x].ch[0];}splay(x);return x;}
	inline void link(LL x,LL y){make_root(x);if(findroot(y)==x)return;t[x].fa=y;}
	inline void cut(LL x,LL y){if(findroot(x)!=findroot(y))return;split(x,y);if(t[x].fa!=y||t[x].ch[1])return;t[x].fa=t[y].ch[0]=0;pushup(x);}
}T;
int main()
{
	read(n),read(m);
	for (LL i=1;i<=n;i++) read(T.t[i].val),T.t[i].sum=T.t[i].val;
	while (m--)
	{
		LL opt,x,y;
		read(opt),read(x),read(y);
		if (opt==0) T.split(x,y),cout<<T.t[y].sum<<endl;
		if (opt==1) T.link(x,y);
		if (opt==2) T.cut(x,y);
		if (opt==3) T.splay(x),T.t[x].val=y; 
	}
	return 0;
}