萌新刚学oi0秒mle0pts求助
查看原帖
萌新刚学oi0秒mle0pts求助
795344
lfxxx_楼主2024/8/13 19:08
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
struct {
	int tr[M][26],exist[M],fail[M],tot;
	void insert(string s,int x)
	{
		int p=0;
		for(int i=0;i<(int)s.size();++i)
		{
			int k=s[i]-97;
			if(!tr[p][k])
				tr[p][k]=++tot;
			p=tr[p][k];
		}
		exist[p]=x;
	}
	void build()
	{
		queue<int>q;
		for(int i=0;i<26;++i)
			if(!tr[0][i])
				q.emplace(tr[0][i]);
		while(!q.empty())
		{
			int u=q.front();q.pop();
			for(int i=0;i<26;++i)
				if(tr[u][i])
					fail[tr[u][i]]=tr[fail[u]][i],q.emplace(tr[u][i]);
			else
				tr[u][i]=tr[fail[u]][i];
		}
	}
	int query(string s)
	{
		int p=0,res=0;
		for(int i=0;i<(int)s.size();++i)
		{
			p=tr[p][s[i]-97];
			for(int u=p;u&&~exist[u];u=fail[u])
				exist[u]=-1,res+=exist[u];
		}
		return res;
	}
}_;
const int N=1e5+5;
int n=2;
int tr[N<<2];
void pushup(int p){tr[p]=tr[p<<1]+tr[p<<1|1];}
void update(int p,int pl,int pr,int x,int d)
{
	if(x<pl||pr<x)
		return ;
	if(pl==x&&pr==x)
	{
		tr[p]+=d;
		return ;
	}
	int mid=(pl+pr)>>1;
	update(p<<1,pl,mid,x,d);
	update(p<<1|1,mid+1,pr,x,d);
}
int query(int p,int pl,int pr,int L,int R)
{
	if(L<=pl&&pr<=R)
		return tr[p];
	if(R<pl||pr<L)
		return 0;
	int mid=(pl+pr)>>1;
	return query(p<<1,pl,mid,L,R)+query(p<<1|1,mid+1,pr,L,R);
}
vector<int>edge[N];
int son[N],sz[N],fa[N],dep[N];
int dfn[N],rnk[N],top[N],id;
void dfs1(int u,int ft)
{
	sz[u]=1;
	fa[u]=ft;
	dep[u]=dep[ft]+1;
	son[u]=-1;
	for(auto &v:edge[u])
	{
		if(v==ft)
			continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]])
			son[u]=v;
	}
}
void dfs2(int u,int t)
{
	top[u]=t;
	dfn[u]=++id;
	rnk[id]=u;
	dfs2(son[u],t);
	for(auto &v:edge[u])
	{
		if(v==fa[u])
			continue;
		dfs2(v,v);
	}
}
int qrange(int x,int y)
{
	int res=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		res+=query(1,1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	return res+query(1,1,n,dfn[x],dfn[y]);
}
int work0(int x,int  y)
{
	edge[1].emplace_back(2);
	edge[2].emplace_back(1);
	dfs1(1,0);
	dfs2(1,1);
	update(1,1,n,dfn[1],x);
	update(1,1,n,dfn[2],y);
	return qrange(1,2);
}
int work1(int x,int y)
{
	_.insert("LYLOVEYHY",x);
	_.insert("TYWLOVELHQ",y);
	return _.query("LYLOVEYHYTYWLOVELHQ");
}
signed main()
{
	int x,y;
	cin>>x>>y;
	cout<<work0(x/2,y/2)+work1(x-x/2,y-y/2);
}
2024/8/13 19:08
加载中...