UOJ#58/BZOJ 3052【WC2013】糖果公园

好写好调的莫队算法，就算上树了仍然好写好调。

传送门

http://uoj.ac/problem/58

简要做法

将树按照dfs序分块，然后将询问按照（u所在块，v所在块，时间）作为关键字进行排序，依次转移。

转移只需依次把u，v移动到目标位置，将经过的点的标记翻转，同时每种颜色统计出现次数。

细节

转移的时候用了一个trick，把点权转换为边权，每个点代表它向父亲的边，于是不用考虑各种边界情况，处理询问的时候再将LCA加上即可。

具体方法：将端点u转移到端点v（此处uv的含义与询问的uv含义不同）时，先将u,v调整到同一深度，然后暴力向上走直到相遇。

其他

按照【王室联邦】的方法分块会更快一些。

具体参见vfk博客：http://vfleaking.blog.163.com/blog/static/174807634201311011201627/

一开始我的分块方法是错的：dfs，依次进栈，size大于块大小时弹栈，这样会导致同一个块中节点分散，于是T到飞起。

（调了好几次参数仍然跑不过同学的代码

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=100005, MAXB=1e7, S=1600;

char BUF[MAXB], *cp=BUF;

void rd(int &x){

	x=0;

	while(*cp<'0'||'9'<*cp) cp++;

	while('0'<=*cp&&*cp<='9') x=x*10+*cp-'0', cp++;

}

int N, M, K, ne, nq, no, top, tot, ord;

int vis[MAXN], V[MAXN], W[MAXN], co[MAXN], n[MAXN], st[MAXN];

int m[MAXN], fa[MAXN], d[MAXN], dfn[MAXN], be[MAXN], lca[MAXN], f[MAXN];

ll sum, ans[MAXN];

vector<P> ql[MAXN];

int find(int x){return x==f[x]?x:(f[x]=find(f[x]));}

void unite(int u, int v){f[find(u)]=find(v);}

struct Edge{Edge *nxt; int to;}E[MAXN<<1],*hd[MAXN];

void adde(int u, int v){

	E[ne].to=v;E[ne].nxt=hd[u];hd[u]=&E[ne++];

	E[ne].to=u;E[ne].nxt=hd[v];hd[v]=&E[ne++];

}

void addq(int u, int v, int i){ql[u].push_back(P(v,i));ql[v].push_back(P(u,i));}

void dfs(int u, int p){

	vis[u]=1; dfn[u]=ord++; fa[u]=p; d[u]=d[p]+1;

	for(Edge *e=hd[u]; e; e=e->nxt){

		int v=e->to;

		if(v!=p){

			dfs(v,u); unite(v,u);

		}

	}

	for(int i=0; i<ql[u].size(); ++i)

		if(vis[ql[u][i].first]) lca[ql[u][i].second]=find(ql[u][i].first);

}

struct Qry{

	int l, r, t, id;

	bool operator<(const Qry &o)const{

		if(be[l]==be[o.l]) return be[r]==be[o.r]?((be[r]&1)?t>o.t:t<o.t):((be[l]&1)?be[r]>be[o.r]:be[r]<be[o.r]);

		return be[l]<be[o.l];

	}

}Q[MAXN];

struct Op{int x, y;}O[MAXN];

inline void mdf(int x, int y){

	if(co[x]!=y&&m[x]){

		sum+=(ll)V[y]*W[n[y]+1]-(ll)V[co[x]]*W[n[co[x]]];

		n[y]++; n[co[x]]--; if(n[2]==-1) exit(233);

	}

}

inline void flip(int x){

	if(!m[x]) m[x]=1, sum+=(ll)V[co[x]]*W[++n[co[x]]];

	else m[x]=0, sum-=(ll)V[co[x]]*W[n[co[x]]--];

}

void tr(int u, int v){

	while(d[v]>d[u]) flip(v),v=fa[v];

	while(d[u]>d[v]) flip(u),u=fa[u];

	while(u!=v) flip(v),v=fa[v],flip(u),u=fa[u];

}

int main(){

	fread(BUF, 1, MAXB, stdin);

	rd(N),rd(M),rd(K);

	for(int i=1; i<=M; ++i) rd(V[i]);

	for(int i=1; i<=N; ++i) rd(W[i]);

	for(int i=1,u,v; i<N; ++i) rd(u),rd(v),adde(u,v);

	for(int i=1; i<=N; ++i) rd(co[i]);

	for(int i=0,t,x,y; i<K; ++i){

		rd(t),rd(x),rd(y);

		if(t==1) addq(x,y,nq),Q[nq].l=x,Q[nq].r=y,Q[nq].id=nq,Q[nq].t=no,nq++;

		else O[no].x=x,O[no].y=y,no++;

	}

	for(int i=1; i<=N; ++i) f[i]=i;

	dfs(1,0); tot++; while(top) be[st[--top]]=tot;

	for(int i=0; i<nq; ++i) if(dfn[Q[i].l]>dfn[Q[i].r]) swap(Q[i].l,Q[i].r);

	for(int i=1; i<=N; ++i) be[i]=dfn[i]/S;

	sort(Q,Q+nq);

	for(int i=0,l=1,r=1,t=0; i<nq; ++i){

		tr(l,Q[i].l); l=Q[i].l;

		tr(r,Q[i].r); r=Q[i].r;

		for(;t<Q[i].t;++t) mdf(O[t].x,O[t].y),swap(co[O[t].x],O[t].y);

		for(;t>Q[i].t;)--t,mdf(O[t].x,O[t].y),swap(co[O[t].x],O[t].y);

		flip(lca[Q[i].id]); ans[Q[i].id]=sum; flip(lca[Q[i].id]);

	}

	for(int i=0; i<nq; ++i) printf("%lld\n", ans[i]);

	return 0;

}

巴特西

UOJ#58/BZOJ 3052【WC2013】糖果公园

传送门

简要做法

细节

其他

代码

最新文章

热门文章