Educational Codeforces Round 16 F - String Set Queries (CDQ分治+AC自动机)

题目链接:

http://codeforces.com/contest/710/problem/F

 

题意:

1. 集合加入一个串

2. 集合删除一个串

3. 问集合中的串在给定串中出现的次数和(可重复)

要求强制在线

 

思路:

如果是离线的话,直接cdq分治,每次求左半边的AC自动机去更新右半边

强制在线的话,只要保存一下log个左半边的AC自动机就好了

 

复杂度:O((n+s)log(n))

#include<bits/stdc++.h>
using namespace std;

const int N=900005;

int ch[N][26],fail[N],cnt[N],f[N];
int tot;
int newnode(){
	tot++;
	for (int i=0;i<26;i++) ch[tot][i]=0;
	fail[tot]=0;  cnt[tot]=0;
	return tot;
}
int merge(int x,int y){
	if (!x||!y) return x+y;
	cnt[x]+=cnt[y];
	for (int i=0;i<26;i++)
		ch[x][i]=merge(ch[x][i],ch[y][i]);
	return x;
}

int root[20];
void insert(int root,char *s,int y){
	int now=root;
	for (int i=0;s[i];i++){
		int w=s[i]-'a';
		if (!ch[now][w]) ch[now][w]=newnode();
		now=ch[now][w];
	}
	cnt[now]+=y;
}
int go(int root,int u,int w){
	while(u!=root&&!ch[u][w]) u=fail[u];
	if (ch[u][w]) return ch[u][w];
	return u;
}
void build(int root){
	queue<int>Q;
	fail[root]=root;
	for (int i=0;i<26;i++){
		int v=ch[root][i];
		if (v){
			fail[v]=root;
			Q.push(v);
		}
	}
	while(!Q.empty()){
		int u=Q.front(); Q.pop();
		f[u]=f[fail[u]]+cnt[u];
		for (int i=0;i<26;i++){
			int v=ch[u][i];
			if (v){
				fail[v]=go(root,fail[u],i);
				Q.push(v);
			}
		}
	}
}
int query(int root,char *s){
	int ret=0;
	int now=root;
	for (int i=0;s[i];i++){
		int w=s[i]-'a';
		now=go(root,now,w);
		ret+=f[now];
	}
	return ret;
}
void init(int &root){
	root=newnode();
	build(root);
}

int tp;
char s[N];
int solve(int l,int r,int deep){
	if (l==r){
		cin>>tp>>s;
		init(root[deep]);
		if (tp<3){
			int y;
			if (tp==1) y=1; else y=-1;
			insert(root[deep],s,y);
		}
		else{
			long long ans=0;
			for (int d=1;d<deep;d++) ans+=query(root[d],s);
			cout<<ans<<endl;
			fflush(stdout);
		}
		return root[deep];
	}
	init(root[deep]);
	int mid=(l+r)/2;
	int rtl=solve(l,mid,deep+1);
	root[deep]=merge(root[deep],rtl);
	build(root[deep]);
	int rtr=solve(mid+1,r,deep+1);
	root[deep]=merge(root[deep],rtr);
	build(root[deep]);
	return root[deep];
}
int main(){
	ios::sync_with_stdio(false);
	int n; cin>>n;
	solve(1,n,1);
}

NOI2014购票(树的cdq分治+凸壳)

题目链接:

http://uoj.ac/problem/7

 

思路:

如果没有距离限制L的话只要dfs一遍同时维护到根的凸壳就可以(二分位置后可以做到O(1)添加,O(1)恢复)。

这题有个距离限制的话就可以将重心下面的点按d[v]-l[v]排序后,与重心到根的点一起双指针更新。

 

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200005;
struct E
{
	int v; ll z;
};
vector<E>link[N];
ll d[N],p[N],q[N],l[N],f[N];
int fa[N];

struct P
{
	ll d,f;
	ll operator*(const P &b)const
	{
		return d*b.d+f*b.f;
	}
}stk[N];
int top;
long double slope(P a,P b)
{
    long double tmp=1.0;
    return tmp*(b.f-a.f)/(b.d-a.d);
}
void add(P p)
{
	if (top<=1)
	{
		stk[top++]=p;
		return;
	}
	while(top>=2&&slope(p,stk[top-1])>slope(stk[top-1],stk[top-2])) top--;
	stk[top++]=p;
}
void upd(int id)
{
	P vec={-p[id],1};
	int l=0,r=top-1;
	while(l<r)
	{
		int mid=(l+r)/2;
		if (vec*stk[mid]>vec*stk[mid+1]) l=mid+1;
		else r=mid;
	}
	f[id]=min(f[id],p[id]*d[id]+q[id]+vec*stk[l]);
}

int cent,mxsz;
int size[N];
int vis[N];
void findcent(int u,int n)
{
	size[u]=1;
	int mx=0;
	for (E e:link[u])
	{
		int v=e.v;
		if (vis[v]) continue;
		d[v]=d[u]+e.z;
		findcent(v,n);
		size[u]+=size[v];
		mx=max(mx,size[v]);
	}
	mx=max(mx,n-size[u]);
	if (mx<=mxsz) cent=u,mxsz=mx;
}

int nd[N],tot;
void add(int u)
{
	nd[tot++]=u;
	for (E e:link[u])
		if (!vis[e.v]) add(e.v);
}
bool cmp(int i,int j)
{
	return d[i]-l[i]>d[j]-l[j];
}
void solve(int u,int n)
{
	if (n==1) return;
	cent=u;  mxsz=n;
	findcent(u,n);
	int rt=cent;
	for (E e:link[rt]) vis[e.v]++;
	if (u==4&&n==2)
		u=4;
	solve(u,n-size[rt]+1);

	for (E e:link[rt]) vis[e.v]--;
	for (E e:link[rt]) add(e.v);
	sort(nd,nd+tot,cmp);
	int now=rt;
	for (int i=0;i<tot;i++)
	{
		int id=nd[i];
		while(now!=fa[u]&&d[now]>=d[id]-l[id]) add({d[now],f[now]}),now=fa[now];
		if (top) upd(id);
	}
	tot=0; top=0;
	for (E e:link[rt]) solve(e.v,size[e.v]);
}
int main()
{
	int n,t; scanf("%d%d",&n,&t);
	for (int i=2;i<=n;i++)
	{
		f[i]=1ll<<62;
		ll s; scanf("%d%lld",&fa[i],&s);
		link[fa[i]].push_back({i,s});
		scanf("%lld%lld%lld",&p[i],&q[i],&l[i]);
	}
	solve(1,n);
	for (int i=2;i<=n;i++) printf("%lld\n",f[i]);
}

 

hdu 5354 cdq分治+并查集

题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=5354

 

题意:问删除每个点后能否构成二分图。

 

做法:

   考虑分治,solve(l,r)是用来求区间l到r的答案,那么可以把l到mid的点都加入并查集,如果存在奇环了,那么mid+1到r的答都

是0,如果没有奇环,继续solve(mid+1,r)。 然后用相同的做法处理l到mid的答案。

   并查集需要还原,所以用启发式合并,用一个栈来记录需要还原的数据。这样复杂度是nlognlogn。

 

 

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int base[N],vec[2*N],pre[2*N],tot;
void link(int x,int y)
{
	vec[++tot]=y; pre[tot]=base[x]; base[x]=tot;
}
int fa[N],sz[N],len[N];
int top,stk[N];
bool check(int l,int r,int x,int y)
{
	for (int u=l;u<=r;u++)
	{
		for (int now=base[u];now;now=pre[now])
		{
			int v=vec[now];
			if (v>=x&&v<=y) continue;
			int su=0,sv=0,fu=u,fv=v;
			while(fu!=fa[fu]) su^=len[fu],fu=fa[fu];
			while(fv!=fa[fv]) sv^=len[fv],fv=fa[fv];
			if (fu==fv)
			{
				if (su==sv) return 0;
				continue;
			}
			if (sz[fu]<sz[fv]) swap(fu,fv);
			stk[++top]=fv;
			fa[fv]=fu;
			sz[fu]+=sz[fv];
			len[fv]=su^sv^1;
		}
	}
	return 1;
}
void load(int u)
{
	sz[fa[u]]-=sz[u];
	fa[u]=u;
}
int ans[N];
void solve(int l,int r)
{
	if (l==r) { ans[l]=1; return; }
	int pretop=top;
	int mid=(l+r)/2;
	if (!check(l,mid,mid+1,r))
		for (int i=mid+1;i<=r;i++) ans[i]=0;
	else
		solve(mid+1,r);
	while(top>pretop) load(stk[top]),top--;

	if (!check(mid+1,r,l,mid))
		for (int i=l;i<=mid;i++) ans[i]=0;
	else
		solve(l,mid);
	while(top>pretop) load(stk[top]),top--;
}
int main()
{
	int t; scanf("%d",&t);
	int n,m;
	while(t--)
	{
		scanf("%d%d",&n,&m);
		while(m--)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			link(x,y); link(y,x);
		}
		for (int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
		solve(1,n);
		for (int i=1;i<=n;i++) printf("%d",ans[i]);
		printf("\n");
		tot=0;
		for (int i=1;i<=n;i++) base[i]=0;
	}
}

  

  

hdu 5127(cdq分治+凸包)

参考了这篇博客 http://blog.csdn.net/u013912596/article/details/47978791 

 

我的做法:

其实每次询问就是 找一个向量(x,y)使得 (x,y)*(p,q)最大。根据向量点积的性质很容易发现最优的向量肯定在凸包上。

如果没有删除操作,可以用平衡树来维护上凸壳和下凸壳,每次询问二分查找。

这题有删除操作,看了题解再想了很久才知道怎么分治。

 

对于一个操作区间【L,R】:

如果【L,mid】区间内的添加的向量在 R 之后被删除或者不删,那么就可以用它们构建上下凸壳来更新【mid+1,R】区间内的询问。

如果【mid+1,R】区间内的删除的向量在 L 之前添加,那么也可以用它们构建上下凸壳来更新【L,mid】区间内的询问。

然后就做完了。

 

一些小技巧:下凸壳可以翻转一下变成上凸壳用同样的方法维护,nxt数组记录与操作i相关的另一个操作的位置,可以很方便的判断它是添加操作还是删除操作。

 

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=50005;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n;
ll ans[N];
int nxt[N];
struct P
{
	int x,y;
	bool operator<(const P &t)const
	{
		return x<t.x||x==t.x&&y>t.y;
	}
	P operator-(const P &t)
	{
		return {x-t.x,y-t.y};
	}
	ll operator*(const P &t)
	{
		return 1ll*x*t.x+1ll*y*t.y;
	}
	ll operator^(const P &t)
	{
		return 1ll*x*t.y-1ll*y*t.x;
	}
}a[N];
ll cross(P a,P b,P c)
{
	return (b-a)^(c-b);
}
map<P,int>mp;
struct hull
{
	int n,top;
	P a[N],stk[N];
	void init()
	{
		n=0;
	}
	void add(P p)
	{
		a[++n]=p;
	}
	void make()
	{
		sort(a+1,a+n+1);
		top=0;
		for (int i=1;i<=n;i++)
		{
			while(top>1&&cross(stk[top-1],stk[top],a[i])>=0) top--;
			stk[++top]=a[i];
		}
	}
	ll get(P p)
	{
		if (top==0) return -INF;
		int l=1,r=top;
		while(l<r)
		{
			int mid=(l+r)/2;
			if (p*stk[mid]<p*stk[mid+1]) l=mid+1;else r=mid;
		}
		return p*stk[l];
	}
}up,down;
void solve(int l,int r)
{
	if (l==r) return;
	int mid=(l+r)/2;

	up.init(); down.init();
	for (int i=l;i<=mid;i++)
		if (nxt[i]>r)
		{
			up.add(a[i]);
			down.add({a[i].x,-a[i].y});
		}
	up.make(); down.make();
	for (int i=mid+1;i<=r;i++)
		if (nxt[i]==i)
		{
			ans[i]=max(ans[i],up.get(a[i])),
			ans[i]=max(ans[i],down.get({a[i].x,-a[i].y}));
		}

	up.init(); down.init();
	for (int i=mid+1;i<=r;i++)
		if (nxt[i]<l)
		{
			up.add(a[i]);
			down.add({a[i].x,-a[i].y});
		}
	up.make(); down.make();
	for (int i=l;i<=mid;i++)
		if (nxt[i]==i)
		{
			ans[i]=max(ans[i],up.get(a[i]));
			ans[i]=max(ans[i],down.get({a[i].x,-a[i].y}));
		}

	solve(l,mid);
	solve(mid+1,r);
}
int main()
{
	while(scanf("%d",&n),n)
	{
		mp.clear();
		for (int i=1;i<=n;i++) ans[i]=-INF;
		for (int i=1;i<=n;i++)
		{
			int tp;
			scanf("%d%d%d",&tp,&a[i].x,&a[i].y);
			if (tp==1) nxt[i]=n+1,mp[a[i]]=i;
			if (tp==-1)
			{
				int id=mp[a[i]];
				nxt[id]=i; nxt[i]=id;
				mp.erase(a[i]);
			}
			if (tp==0) nxt[i]=i;
		}
		solve(1,n);
		for (int i=1;i<=n;i++)
			if (nxt[i]==i) printf("%lld\n",ans[i]);
	}
}