板子合集

#include
#include
#include
using namespace std;
const int N=2e7+13;
char s[N],t[N];
int n,m,nxt[N],ext[N];
inline void init(){
	nxt[1]=n;
	for(int i=2,l=0,r=0;i<=n;++i){
		int tmp=nxt[i-l+1];
		if(i<=r){
			if(i+tmp<=r) nxt[i]=tmp;
			else nxt[i]=r-i+1;	
		}
		while(i+nxt[i]<=n&&t[i+nxt[i]]==t[1+nxt[i]]) ++nxt[i];
		if(i+nxt[i]-1>r) r=i+nxt[i]-1,l=i;
	}
}
inline void exKMP(){
	for(int i=1,l=0,r=0;i<=m;++i){
		int tmp=nxt[i-l+1];
		if(i<=r){
			if(i+tmp<=r) ext[i]=tmp;
			else ext[i]=r-i+1;	
		}
		while(i+ext[i]<=m&&1+ext[i]<=n&&s[i+ext[i]]==t[1+ext[i]]) ++ext[i];
		if(i+ext[i]-1>r) r=i+ext[i]-1,l=i;
	}
}
inline void file(){
	freopen("P5410_1.in","r",stdin);
	freopen("P5410.out","w",stdout);
}
int main(){
	//file();
	scanf("%s%s",s+1,t+1);
	m=strlen(s+1),n=strlen(t+1);
	init();
	exKMP();
	long long ans1=0,ans2=0;
	for(int i=1;i<=n;++i) ans1^=1ll*i*(nxt[i]+1);
	for(int i=1;i<=m;++i) ans2^=1ll*i*(ext[i]+1);
	printf("%lld\n%lld\n",ans1,ans2);
	return 0;
}

inline int newpos(std::array nson,int nlen){return ++ptot,len[ptot]=nlen,swap(son[ptot],nson),ptot;}
inline void insert(int c){
	int p=lastpos;int u=newpos(boom,len[p]+1);cnt[u]=1;
	while(p&&!son[p][c]) son[p][c]=u,p=nxt[p];
	if(!p) return lastpos=u,nxt[u]=1,void();
	int d=son[p][c];
	if(len[d]==len[p]+1) nxt[u]=d;
	else{
		int v=newpos(son[d],len[p]+1);
		nxt[v]=nxt[d],nxt[d]=v,nxt[u]=v;
		while(p&&son[p][c]==d) son[p][c]=v,p=nxt[p];
	}
	lastpos=u;
}

const int N=10000+13;
struct Edge{int v,w,nxt;}e[N*5];
int n,m,s,t,lim,to[N],xx[N],yy[N],uu[N],vv[N],deg[N],h[N],tot=1,ad[N];
inline void add(int u,int v,int w){
	e[++tot]=(Edge){v,w,h[u]};h[u]=tot;
	e[++tot]=(Edge){u,0,h[v]};h[v]=tot;
}
int dep[N],cur[N];
bool vis[N];
inline bool bfs(){
	memset(dep,0x7f,sizeof(dep));
	memcpy(cur,h,sizeof(h));
	memset(vis,0,sizeof(vis));
	std::queueq;
	q.push(t),dep[t]=0,vis[t]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i^1].w;
			if(!vis[v]&&w) dep[v]=dep[u]+1,vis[v]=1,q.push(v);
		}
	}
	return vis[s];
}
ll dfs(int u,ll minw){
	if(u==t||!minw) return minw;
	ll f,flow=0;
	for(int i=cur[u];i;i=e[i].nxt){
		cur[u]=i;
		int v=e[i].v,w=e[i].w;
		if(dep[u]==dep[v]+1&&(f=dfs(v,min(minw,(ll)w)))){
			minw-=f,flow+=f,e[i].w-=f,e[i^1].w+=f;
			if(!minw) break;
		}
	}
	return flow;
}
inline ll dinic(){
	ll flow=0;
	while(bfs()) flow+=dfs(s,INF);
	return flow;
}
int main(){
	read(n),read(m),read(s),read(t); 
	for(int i=1;i<=m;i++){
		int u,v,w;read(u),read(v),read(w);
		add(u,v,w);
		add(v,u,0);
	}
	println(dinic());
	return 0;
}

#include
#include
#include
#include
#define re register
using namespace std;
const int N=5000+21,M=50000+21,INF=0x3f3f3f3f;
struct Edge{int u,v,f,w,nxt;}e[M*2];
int h[N],dist[N],last[N],flow[N],pre[N];
bool vis[N];
int n,m,s,t,tot=1;
inline void add(re int u,re int v,re int f,re int w){
	e[++tot]=(Edge){u,v,f,w,h[u]};
	h[u]=tot;
}
bool spfa(){
	memset(dist,0x3f,sizeof(dist));
	memset(vis,0,sizeof(vis));
	memset(flow,0x3f,sizeof(flow));
	pre[t]=-1;
	queueq;
	q.push(s);
	vis[s]=1;
	dist[s]=0;
	while(!q.empty()){
		re int u=q.front();
		q.pop();
		vis[u]=0;
		for(re int i=h[u];i;i=e[i].nxt){
			re int v=e[i].v,w=e[i].w,f=e[i].f;
			if(f&&dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				flow[v]=min(flow[u],f);
				pre[v]=u;
				last[v]=i;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return pre[t]!=-1;
}
void mcmf(){
	re int maxflow=0,mincost=0;
	while(spfa()){
		maxflow+=flow[t];
		mincost+=flow[t]*dist[t];
		re int now=t;
		while(now!=s){
			e[last[now]].f-=flow[t];
			e[last[now]^1].f+=flow[t];
			now=pre[now];
		}
	}
	printf("%d %d\n",maxflow,mincost);
}
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(re int i=1;i<=m;++i){
		re int u,v,f,w;
		scanf("%d%d%d%d",&u,&v,&f,&w);
		add(u,v,f,w);
		add(v,u,0,-w);
	}
	mcmf();
	return 0;
}

#include
#include
using namespace std;
const int N=1e5+13;
inline void swap(int &x,int &y){x^=y^=x^=y;}
int n,m,a[N];
struct Link_Cut_Tree{
	struct Stack{
		int s[N],t;
		inline void clear(){t=0;}
		Stack(){clear();}
		inline void push(int x){s[++t]=x;}
		inline int top(){return s[t];}
		inline void pop(){--t;}
		inline bool empty(){return !t;}
	};
	int fa[N],val[N],ch[N][2];bool tag[N];
	inline void refresh(int x){val[x]=a[x]^val[ch[x][0]]^val[ch[x][1]];}
	inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
	inline bool chk(int x){return ch[fa[x]][1]==x;}
	inline void rotate(int x){
		int f=fa[x],gf=fa[f],k=chk(x),w=ch[x][k^1];
		fa[x]=gf;if(!isroot(f)) ch[gf][chk(f)]=x;
		if(w) fa[w]=f;ch[f][k]=w;
		fa[f]=x;ch[x][k^1]=f;
		refresh(f),refresh(x);
	}
	inline void pushdown(int x){
		if(!tag[x]) return;
		tag[ch[x][0]]^=1,tag[ch[x][1]]^=1,tag[x]=0;
		swap(ch[x][0],ch[x][1]);
	}
	inline void splay(int x){
		Stack st;
		int p=x;
		while(!isroot(p)) st.push(p),p=fa[p];
		st.push(p);
		while(!st.empty()) pushdown(st.top()),st.pop();
		while(!isroot(x)){
			int f=fa[x],gf=fa[f];
			if(!isroot(f)){
				if(chk(f)==chk(x)) rotate(f);
				else rotate(x);
			}
			rotate(x);
		}
	}
	inline void access(int x){
		for(int p=0;x;p=x,x=fa[x]) splay(x),ch[x][1]=p,refresh(x);
	}
	inline void makeroot(int x){
		access(x);
		splay(x);
		tag[x]^=1;
	}
	inline int findroot(int x){
		access(x);
		splay(x);
		while(ch[x][0]) x=ch[x][0];
		return x;
	}
	inline void split(int x,int y){
		makeroot(x);
		access(y);
		splay(y);
	}
	inline void link(int x,int y){
		makeroot(x);
		if(findroot(y)!=x) fa[x]=y;
	}
	inline void cut(int x,int y){
		split(x,y);
		if(ch[y][0]==x&&!ch[x][1]) fa[x]=ch[y][0]=0;
	}
	inline void modify(int x,int y){
		access(x);
		splay(x);
		a[x]=y,refresh(x);
	}
}T;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	while(m--){
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		switch(op){
			case 0:{T.split(x,y);printf("%d\n",T.val[y]);break;}
			case 1:{T.link(x,y);break;}
			case 2:{T.cut(x,y);break;}
			case 3:{T.modify(x,y);break;}
		}
	}
	return 0;
}

#include
#include
#include
#include
inline int rd(){
	int res=0,flag=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')flag=-1;
	for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
	return res*flag;
}
void wt(int x){if(x<0)putchar('-'),x=-x;if(x>9)wt(x/10);putchar(x%10+'0');}
std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
const int N=1e5+13;
int n,rt,tot;
struct Fhqtreap{int ls,rs,siz,val,prio;}t[N];
#define ls(p) t[p].ls
#define rs(p) t[p].rs
inline int newnode(int x){return t[++tot]=(Fhqtreap){0,0,1,x,(int)rnd()},tot;}
inline void refresh(int p){t[p].siz=t[ls(p)].siz+t[rs(p)].siz+1;}
int merge(int p,int q){
	if(!p||!q) return p|q;
	if(t[p].priot[ls(p)].siz+1) k-=t[ls(p)].siz+1,p=rs(p);
		else return p;
	}
}
int main(){
//	freopen("P3369_6.in","r",stdin);
//	freopen("P3369.out","w",stdout);
	int T=rd();
	while(T--){
		int op=rd(),k=rd(),x,y,z;
		switch(op){
			case 1:{
				split(rt,k,x,y);
				rt=merge(merge(x,newnode(k)),y);
				break;
			}
			case 2:{
				split(rt,k-1,x,z);split(z,k,z,y);
				rt=merge(merge(x,merge(ls(z),rs(z))),y);
				break;
			}
			case 3:{
				split(rt,k-1,x,y);
				wt(t[x].siz+1),putchar('\n');
				rt=merge(x,y);
				break;
			}
			case 4:{
				wt(t[kth(rt,k)].val),putchar('\n');
				break;
			}
			case 5:{
				split(rt,k-1,x,y);
				wt(t[kth(x,t[x].siz)].val),putchar('\n');
				rt=merge(x,y);
				break;
			}
			case 6:{
				split(rt,k,x,y);
				wt(t[kth(y,1)].val),putchar('\n');
				rt=merge(x,y);
				break;
			}
		}
	}
	return 0;
}

#include
#include
#include
#include
using namespace std;
const int N=5e5+13,logN=40+13;
int INF=2147483647;
struct Fhqtreap{int siz,ls,rs,prio,val;}t[N*logN];
typedef Fhqtreap Fhq;
int n,tot,rt[N];
inline int newnode(int v){t[++tot]=(Fhq){1,0,0,rand(),v};return tot;}
inline void refresh(int p){t[p].siz=t[t[p].ls].siz+t[t[p].rs].siz+1;}
int merge(int p,int q){
	if(!p||!q) return p+q;
	int now=++tot;
	if(t[p].priot[t[p].ls].siz+1) k-=t[t[p].ls].siz+1,p=t[p].rs;
		else return p;
	}
}
int main(){
	srand(time(NULL));
	scanf("%d",&n);
	for(int i=1,v,op,k,x,y,z;i<=n;++i,x=y=z=0){
		scanf("%d%d%d",&v,&op,&k);rt[i]=rt[v];
		switch(op){
			case 1:{
				split(rt[i],k,x,y);
				rt[i]=merge(merge(x,newnode(k)),y);
				break;
			}
			case 2:{
				split(rt[i],k,x,z);
				split(x,k-1,x,y);
				y=merge(t[y].ls,t[y].rs);
				rt[i]=merge(merge(x,y),z);
				break;
			}
			case 3:{
				split(rt[i],k-1,x,y);
				printf("%d\n",t[x].siz+1);
				rt[i]=merge(x,y);
				break;
			}
			case 4:{
				printf("%d\n",t[kth(rt[i],k)].val);
				break;
			}
			case 5:{
				split(rt[i],k-1,x,y);
				if(!x) printf("%d\n",-INF);
				else printf("%d\n",t[kth(x,t[x].siz)].val);
				rt[i]=merge(x,y);
				break;
			}
			case 6:{
				split(rt[i],k,x,y);
				if(!y) printf("%d\n",INF);
				else printf("%d\n",t[kth(y,1)].val);
				rt[i]=merge(x,y);
				break;
			}
		}
	}
	return 0;
}

#include
#include
#define rint register int
using namespace std;
inline int rd(){
	int res=0;char c=getchar();
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
	return res;
}
const int N=1e7+13;
int n,a[N],s[N],top,L[N],R[N];
int main(){
	n=rd();
	for(rint i=1;i<=n;++i){
		a[i]=rd();rint pos=top;
		while(pos&&a[s[pos]]>a[i]) --pos;
		if(pos) R[s[pos]]=i;
		if(pos