BZOJ 2333 【SCOI2011】棘手的操作

　　网上的题解大部分都是在线用可并堆艹……但是树高严格\(\log\)的可并堆我不会啊……还是离线大法好……

　　我们可以先把所有的合并操作用并查集给处理好，把得到的森林记录下来。然后，我们对这个森林进行\(dfs\)，就可以得到一个\(dfs\)序，那么我们把所有点按照\(dfs\)序重标号，每个联通块就成为了一段区间了。然后就可以直接用线段树维护了。

　　注意一个细节：在\(dfs\)的时候对于一个点连出去的所有边，要优先走先连的边，这样才能保证联通块始终是一段区间。

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define maxn 300010

#define INF 2147483647

using namespace std;

typedef long long llg;

struct data{

	int op,x,y;

}s[maxn];

int head[maxn],next[maxn],to[maxn],tt,du[maxn];

int fa[maxn],n,m,a[maxn],le[maxn],ri[maxn],b[maxn];

int maxv[maxn<<2],addv[maxn<<2],L,R,z,_max,_add;

char ss[20];

int getint(){

	int w=0;bool q=0;

	char c=getchar();

	while((c>'9'||c<'0')&&c!='-') c=getchar();

	if(c=='-') c=getchar(),q=1;

	while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();

	return q?-w:w;

}

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

void link(int x,int y){du[x]++;to[++tt]=y;next[tt]=head[x];head[x]=tt;}

void dfs(int u){

	le[u]=++tt;

	int *d=new int[du[u]];

	for(int i=head[u],j=0;i;i=next[i]) d[j++]=to[i];

	for(int i=du[u];i;i--) dfs(d[i-1]);

}

void build(int u,int l,int r){

	int lc=u<<1,lv=u<<1|1,mid=(l+r)>>1;

	if(l==r){maxv[u]=b[l];return;}

	build(lc,l,mid); build(lv,mid+1,r);

	maxv[u]=max(maxv[lc],maxv[lv]);

}

void add(int u,int l,int r){

	int lc=u<<1,lv=u<<1|1,mid=(l+r)>>1;

	if(l>=L && r<=R){maxv[u]+=z,addv[u]+=z;return;}

	if(L<=mid) add(lc,l,mid);

	if(R>mid) add(lv,mid+1,r);

	maxv[u]=max(maxv[lc],maxv[lv])+addv[u];

}

void query(int u,int l,int r){

	int lc=u<<1,lv=u<<1|1,mid=(l+r)>>1;

	if(l>=L && r<=R){_max=max(_max,maxv[u]+_add);return;}

	_add+=addv[u];

	if(L<=mid) query(lc,l,mid);

	if(R>mid) query(lv,mid+1,r);

	_add-=addv[u];

}

void work(){

	_max=-INF; query(1,1,n);

	printf("%d\n",_max);

}

int main(){

	File("a");

	n=getint();

	for(int i=1;i<=n;i++) a[i]=getint(),fa[i]=i;

	m=getint();

	for(int i=1,u,v;i<=m;i++){

		scanf("%s",ss); if(!ss[1]) ss[1]='1';

		s[i].op=(ss[0]=='A')+(ss[0]=='F')*4+ss[1]-'0';

		if(s[i].op<7) s[i].x=getint();

		if(s[i].op<4) s[i].y=getint();

		if(s[i].op==1){

			u=find(s[i].x),v=find(s[i].y);

			if(u!=v) fa[u]=v,link(v,u);

		}

	}

	tt=0;

	for(int i=1;i<=n;i++) if(find(i)==i) dfs(i);

	for(int i=1;i<=n;i++) b[le[i]]=a[i],ri[i]=le[i];

	for(int i=1;i<=n;i++) fa[i]=i; build(1,1,n);

	for(int i=1,u,v;i<=m;i++){

		u=s[i].x; z=v=s[i].y;

		if(s[i].op==1){

			u=find(u),v=find(v);

			if(u!=v) fa[u]=v,ri[v]=ri[u];

		}

		else if(s[i].op==2) L=R=le[u],add(1,1,n);

		else if(s[i].op==3) u=find(u),L=le[u],R=ri[u],add(1,1,n);

		else if(s[i].op==4) z=u,L=1,R=n,add(1,1,n);

		else if(s[i].op==5) L=R=le[u],work();

		else if(s[i].op==6) u=find(u),L=le[u],R=ri[u],work();

		else printf("%d\n",maxv[1]);

	}

	return 0;

}

　　UPD 3.2：左偏树做法

　　其实无须树高严格\(\log\)，左偏树就够了

　　网上有的题解是每次用\(O(树高)\)的时间统计影响这个点的所有标记，可并堆用的是左偏树= =

　　但是这样复杂度是不对的，因为左偏树的树高可以达到\(O(n)\)级别

　　然后就需要考虑一种别的解法

　　既然不能每次暴力统计到根的所有标记，我们可以考虑把标记永久化了，固定在根节点，这样每次就只需要查询根节点的标记就可以了。但是这样的话合并的时候会出问题，两个堆无法直接合并。不要慌，我们只需要把\(size\)较小的那个堆里面所有的元素暴力修改掉就可以直接合并了。再用个全局的堆维护一下全局最大值。总复杂度\(O(n\log n)\)。

　　顺便Orz告诉我此解法的xlightgod大爷Orz

　　PS：我写的是斜堆，不是左偏树

　　下面贴代码：

#include<bits/stdc++.h>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define maxn 300010

using namespace std;

typedef long long llg;

struct Queue{

	priority_queue<int> q1,q2;

	void insert(int x){q1.push(x);}

	void erase(int x){q2.push(x);}

	int top(){

		while(!q2.empty() && q1.top()==q2.top()) q1.pop(),q2.pop();

		return q1.top();

	}

}q;

int n,rt[maxn],siz[maxn],fa[maxn],addv[maxn];

int ff[maxn],s[maxn][2],val[maxn],m,z,_add;

char ss[20];

int getint(){

	int w=0;bool q=0;

	char c=getchar();

	while((c>'9'||c<'0')&&c!='-') c=getchar();

	if(c=='-') c=getchar(),q=1;

	while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();

	return q?-w:w;

}

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

int merge(int u,int v){

	if(!u || !v) return u+v;

	if(val[u]<val[v]) swap(u,v);

	fa[s[u][1]=merge(s[u][1],v)]=u;

	swap(s[u][0],s[u][1]); return u;

}

void del(int u){

	int x=find(u),y=fa[u];

	if(rt[x]==u) fa[rt[x]=merge(s[u][0],s[u][1])]=0;

	else fa[s[y][u==s[y][1]]=merge(s[u][0],s[u][1])]=y;

}

void dfs(int u){

	val[u]+=z;

	if(s[u][0]) dfs(s[u][0]);

	if(s[u][1]) dfs(s[u][1]);

}

int main(){

	File("a");

	n=getint();

	for(int i=1;i<=n;i++){

		ff[i]=rt[i]=i,siz[i]=1;

		q.insert(val[i]=getint());

	}

	m=getint();

	while(m--){

		int x,y,u;

		scanf("%s",ss+1);

		if(ss[1]=='U'){

			x=find(getint()),y=find(getint());

			if(siz[x]>siz[y]) swap(x,y);

			if(x!=y){

				q.erase(min(val[rt[x]]+addv[x],val[rt[y]]+addv[y]));

				z=addv[x]-addv[y],dfs(rt[x]); siz[y]+=siz[x];

				ff[x]=y; rt[y]=merge(rt[x],rt[y]);

			}

		}

		else if(ss[1]=='A'){

			x=getint();

			if(ss[2]=='1' || ss[2]=='2'){

				u=find(x); y=getint();

				q.erase(val[rt[u]]+addv[u]);

				if(ss[2]=='1'){

					del(x); val[x]+=y;

					s[x][0]=s[x][1]=fa[x]=0;

					rt[u]=merge(rt[u],x);

				}

				else addv[u]+=y;

				q.insert(val[rt[u]]+addv[u]);

			}

			else if(ss[2]=='3') _add+=x;

		}

		else{

			if(ss[2]=='3') printf("%d\n",q.top()+_add);

			else{

				x=getint(); u=find(x);

				if(ss[2]=='1') printf("%d\n",val[x]+addv[u]+_add);

				else if(ss[2]=='2') printf("%d\n",val[rt[u]]+addv[u]+_add);

			}

		}

	}

	return 0;

}

巴特西

BZOJ 2333 【SCOI2011】棘手的操作

最新文章

热门文章

巴特西

BZOJ 2333 【SCOI2011】 棘手的操作

最新文章

热门文章

BZOJ 2333 【SCOI2011】棘手的操作