BZOJ2333 [SCOI2011]棘手的操作【离线 + 线段树】

题目

有N个节点，标号从1到N，这N个节点一开始相互不连通。第i个节点的初始权值为a[i]，接下来有如下一些操作：

U x y: 加一条边，连接第x个节点和第y个节点

A1 x v: 将第x个节点的权值增加v

A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v

A3 v: 将所有节点的权值都增加v

F1 x: 输出第x个节点当前的权值

F2 x: 输出第x个节点所在的连通块中，权值最大的节点的权值

F3: 输出所有节点中，权值最大的节点的权值

输入格式

输入的第一行是一个整数N，代表节点个数。

接下来一行输入N个整数，a[1], a[2], …, a[N]，代表N个节点的初始权值。

再下一行输入一个整数Q，代表接下来的操作数。

最后输入Q行，每行的格式如题目描述所示。

输出格式

对于操作F1, F2, F3，输出对应的结果，每个结果占一行。

输入样例

0 0 0

A1 3 -20

A1 2 20

U 1 3

A2 1 10

F1 3

F2 3

A3 -10

输出样例

-10

提示

对于30%的数据，保证 N<=100，Q<=10000

对于80%的数据，保证 N<=100000，Q<=100000

对于100%的数据，保证 N<=300000，Q<=300000

对于所有的数据，保证输入合法，并且 -1000<=v, a[1], a[2], …, a[N]<=1000

题解

据说此题很多人堆套堆，怎么这么难写

我那么弱当然是用线段树啦

我觉得线段树的确好写到不知哪里去

对于所有操作，似乎在线段树上都很好实现，唯一的难点就在于点的编号

那么问题就转化成了，给定一种编号方法，使任意时刻同一个联通块内的所有点编号连续

只需要分两种情况想就很容易实现了：

我们想象，一开始所有点相互独立，没什么关系

①当两个独立的点相连时，它们的编号一定是连续的，否则此时就不满足所需性质

那我们就先用链表将它们连起来，表示编号连续

②当两个联通块相连时，由我们维护的性质得：两个联通块内部的点编号一定是连续的，现在我们需要两个联通块编号连续，我们只需要将它们的编号衔接起来就好了，那么我们把其中一个联通块所对应的链接到另一个联通块对应的链末尾就好了

可以发现，这样子操作之后，我们就会得出若干个链，表示链上的点编号必须按链上的顺序

所以我们按链的顺序标号，就能保证所有时刻联通块内部点的编号连续

取链头链尾用并查集实现

我们在询问的时候，也要用上并查集，并且链接顺序与标号的时候相同，保证每个联通块目前的代表元一定是标号时编号最小的点，所以我们再维护并查集的大小就可以轻松求出每次操作的区间啦~

数据结构部分就只用实现一个简单的线段树

比堆套堆不知道要好写到哪里去

丑丑的代码

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");

#define ls (u << 1)

#define rs (u << 1 | 1)

using namespace std;

const int maxn = 300005,maxm = 100005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}

	return out * flag;

}

struct Query{int opt,a,b,c;}q[maxn];

int n,m,pre[maxn],post[maxn],id[maxn],Hash[maxn],val[maxn],cnt;

int nxt[maxn],siz[maxn];

int mx[4 * maxn],tag[4 * maxn];

char opt[10];

int findu(int u){return u == pre[u] ? u : pre[u] = findu(pre[u]);}

int findd(int u){return u == post[u] ? u : post[u] = findd(post[u]);}

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

	if (l == r) {mx[u] = val[Hash[l]]; return;}

	int mid = l + r >> 1;

	build(ls,l,mid);

	build(rs,mid + 1,r);

	mx[u] = max(mx[ls],mx[rs]);

}

void pd(int u){

	if (tag[u]){

		mx[ls] += tag[u]; tag[ls] += tag[u];

		mx[rs] += tag[u]; tag[rs] += tag[u];

		tag[u] = 0;

	}

}

void modify(int u,int l,int r,int L,int R,int v){

	if (l >= L && r <= R){mx[u] += v; tag[u] += v; return;}

	pd(u);

	int mid = l + r >> 1;

	if (mid >= L) modify(ls,l,mid,L,R,v);

	if (mid < R) modify(rs,mid + 1,r,L,R,v);

	mx[u] = max(mx[ls],mx[rs]);

}

int query(int u,int l,int r,int L,int R){

	if (l >= L && r <= R) return mx[u];

	pd(u);

	int mid = l + r >> 1;

	if (mid >= R) return query(ls,l,mid,L,R);

	else if (mid < L) return query(rs,mid + 1,r,L,R);

	else return max(query(ls,l,mid,L,R),query(rs,mid + 1,r,L,R));

}

int main(){

	n = read();

	for (int i = 1; i <= n; i++) val[i] = read(),pre[i] = post[i] = i;

	m = read();

	int fa,fb,sa,sb;

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

		scanf("%s",opt);

		if (opt[0] == 'U'){

			q[i].opt = 0,q[i].a = read(),q[i].b = read();

			fa = findu(q[i].a); fb = findu(q[i].b);

			if (fa == fb) continue;

			sa = findd(q[i].a); sb = findd(q[i].b);

			nxt[sa] = fb;

			pre[fb] = fa;

			post[sa] = sb;

		}

		else if (opt[0] == 'A'){

			q[i].a = read();

			if (opt[1] == '1') q[i].opt = 1,q[i].b = read();

			else if (opt[1] == '2') q[i].opt = 2,q[i].b = read();

			else q[i].opt = 3;

		}else {

			if (opt[1] == '1') q[i].opt = 4,q[i].a = read();

			else if (opt[1] == '2') q[i].opt = 5,q[i].a = read();

			else q[i].opt = 6;

		}

	}

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

		if (id[i]) continue;

		int u = findu(i);

		while (u) id[u] = ++cnt,Hash[cnt] = u,u = nxt[u];

	}

	build(1,1,n);

	for (int i = 1; i <= n; i++) pre[i] = i,siz[i] = 1;

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

		switch(q[i].opt){

			case 0:

				fa = findu(q[i].a); fb = findu(q[i].b);

				if (fa != fb){

					siz[fa] += siz[fb];

					pre[fb] = fa;

				}

				break;

			case 1:

				modify(1,1,n,id[q[i].a],id[q[i].a],q[i].b);

				break;

			case 2:

				fa = findu(q[i].a);

				modify(1,1,n,id[fa],id[fa] + siz[fa] - 1,q[i].b);

				break;

			case 3:

				modify(1,1,n,1,n,q[i].a);

				break;

			case 4:

				printf("%d\n",query(1,1,n,id[q[i].a],id[q[i].a]));

				break;

			case 5:

				fa = findu(q[i].a);

				printf("%d\n",query(1,1,n,id[fa],id[fa] + siz[fa] - 1));

				break;

			case 6:

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

				break;

		}

	}

	return 0;

}

巴特西

BZOJ2333 [SCOI2011]棘手的操作【离线 + 线段树】

题目

输入格式

输出格式

输入样例

输出样例

提示

题解

最新文章

热门文章

巴特西

BZOJ2333 [SCOI2011]棘手的操作 【离线 + 线段树】

题目

输入格式

输出格式

输入样例

输出样例

提示

题解

最新文章

热门文章

BZOJ2333 [SCOI2011]棘手的操作【离线 + 线段树】