存档

//定义 low 为u 能走到的栈里的最小值
//有向图强连通分量
//区分返祖边
void tar(int u){
    low[u]=++num_tar; dfn[u]=low[u];
	vis[u]=1; st[++top]=u;
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		if(!dfn[v]){
			tar(v); low[u]=min(low[u],low[v]);
		}else if(vis[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}if(dfn[u]==low[u]){
	    c++;
		do{
			col[st[top]]=c;
			vis[st[top]]=0;
			top--;
		}while(st[top]!=u);
	}
}

//无向图
//割点
//定义 low 为u能走到的最小点

void tarjin(int u){
	dfn[u]=low[u]=++cnt;
	int flag=0;
	for(int i=head[u];i;i=s[i].nex){
		int v=s[i].to;
		if(!dfn[v]){
			tarjin(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<=low[v]){
				++flag;
				if(u!=root||flag>1) {
					if(cut[u]==0) ans++;
					cut[u]=1;
				}
			}
		}else low[u]=min(low[u],dfn[v]);
	}
}

//无向图 求桥
void tarjin(int u){
	dfn[u]=low[u]=++cnt;
	int flag=0;
	for(int i=head[u];i;i=s[i].nex){
		int v=s[i].to;
		if(!dfn[v]){
			tarjin(v);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<low[v]){
				++flag;
				//u ----v 为桥
			}
		}else low[u]=min(low[u],dfn[v]);
	}
}

//字典树  过
//AC自动机
//多模式串匹配
//fail指针：失配指针，当前位置无法匹配后下一个最优且最长的前缀位置
//每一个节点代表一个前缀状态
//构造trie
int cnt=1;//构造一个1的虚根
char s[N];
void insert(){
	int u=1,len=strlen(s);
	for(int i=0;i<len;i++){
		int v=s[i]-'a';
		if(!son[u][v]) son[u][v]=++cnt;
		u=son[u][v];
	}num[u]++;
}
//getfail
void getfail(){
	queue<int> q;
	for(int i=0;i<26;i++) son[0][i]=1;
	q.push(1); fail[1]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			int v=son[u][i];
			int Fail=fail[u];
			if(!v){
				son[u][i]=son[Fail][i];//相当于见trie 图
				continue;
			}fail[v]=son[Fail][i];
            q.push(v);
		}
	}
}
//匹配   用到再说
//fail树
//判环



//splay
struct Splay{
	#define ls (ch[tmp][0])
	#define rs (ch[tmp][1])
	int num;
	int f[N],ch[N][2],siz[N],val[N],w[N];
	void pushup(int tmp){siz[tmp]=siz[ls]+siz[rs]+w[k];}
	int rela(int k){return ch[f[k]][0]==k?0:1;}
	void c(int x,int fa,int rc){ch[fa][rc]=x; f[x]=fa;}
	void rot(int x){//把x旋转到f[x]
        int fa=f[x],gr=f[fa];
		int tf=rela(x),tg=rela(fa);
		c(chx[x][tf^1],fa,tf);
		c(fa,x,tf^1);
		c(x,gr,tg);
		pushup(fa); pushup(x);
	}void splay(int x,int aim){
		aim=f[aim];
		while(f[x]!=aim){
			if(f[f[x]]!=aim){
				if(rela(x)==rela(f[x])) rot(f[x]);
				else rot(x);
			}rot(x);
		}
	}void add(int aim){
		int x=rt;
		if(!x){
			x=newpoint(aim,0);
			rt=x;
			return;
		}while(1){
			if(val[x]==aim){
				//aaaaaaaa
				splay(x,rt);
			}int typ=val[x]>aim?0:1;
			if(!ch[x][typ]){
				ch[x][typ]=nowpoint(aim,x);
				splay(ch[x][typ],rt);
				return;
			}x=ch[x][typ];
		}
	}int find(int x,int aim){
		if(!x) return 0;
		if(val[x]==aim){
			splay(x,rt);
			return x;
		}//递归就行了 find
	}void del(int x){
		int pos=find(rt,x);
		if(!pos) return;
		if(w[pos]>1) {//常规操作}
		else{
			//找到左儿子里面最大的
			//splay to 左儿子的位置
			//把右子树接到左儿子的右儿子上
			//把左儿子和虚根0接上
		}
	}//剩下的都随便吧 摆烂
}


//kmp 算法

void get_p(string s){////
	int len=s.size();
	p[0]=0;
	for(int i=1;i<len;i++){
		int j=p[i-1];
		while(j>0&&s[i]!=s[j]){
			j=p[j-1];
		}
		if(s[i]==s[j]) ++j;
		p[i]=j;
    }
}//文本串匹配一会再说






//CRT  待补……






}