题目链接

哎呦我去，比赛的时候差一点就写出来了…
wa了好几发，没想明白错在哪；
赛后想了一下，原来少了个判断，在一个集合的时候就不用合并了…我是sb
不过还是很开心的，第一次在比赛时能写出离线处理的题。

离线 + 思维倒推 + 并查集；

分析

首先读完题目我的第一个反应就是之前写过类似的，PAT的《红色警戒》；
因此引导我往并查集方面去想，但是《红色警戒》数据范围很小，每个询问都去暴力找连通块就行；

显然在这道题是行不通的，看一下数据范围5×1e5，范围比较大，每次询问可以带一个log；
但是并查集没有log，所以我就产生了离线处理，然后O(1)查询的想法；

然后模拟了一下发现从前往后询问并不好搞…后面的询问用不到前面的询问…
因此考虑从后往前处理询问，每次相当于是新建一条路，判断两个连通块的关系并且合并就行；
这样就能用到已经处理好的询问信息；

这里有个细节，由于发电场是编号比较大的点；
因此我们合并的时候可以把集合都挂在编号比较大的点；
这样find的时候就知道了集合是否有发电站！

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
#define int long long
// #define double long double
typedef long long ll;
typedef unsigned long long ull;
      
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 3e6 + 7;
const int N = 2e6 + 7;
const int M = 4e6 + 7;
const int mod = 1e9 + 7;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

int n,m,e,q;
int f[maxn];
int sz[maxn];
int vis[maxn];
int ans[maxn];

PII p[maxn];
int qq[maxn];
map<int,int> mp;

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

void solve()
{
	iire(n,m);	//读入
	ire(e);
	for(int i=1;i<=e;i++) iire(p[i].first,p[i].second);
	
	ire(q);	//读入询问
	for(int i=1;i<=q;i++)
	{
		ire(qq[i]);
		mp[qq[i]] = 1;
	}
	
	for(int i=1;i<=n+m;i++) f[i] = i, sz[i] = 1;
	
	for(int i=1;i<=e;i++)	//把所有的路都破坏后的情况
		if(!mp[i])
		{
			int a = find(p[i].first);
			int b = find(p[i].second);
			
			if(a != b)	//挂在编号大的点上
			{
				if(a > b)
				{
					f[b] = a;
					sz[a] += sz[b];
				}
				else
				{
					f[a] = b;
					sz[b] += sz[a];
				}
			}
		}

	int cnt = 0;	//统计一下把所有的路都破坏后的合法点的个数
	for(int i=1;i<=n;i++)
	{
		int fa = find(i);
		if(fa >= n+1 && fa <= n+m) cnt++;
	}
	ans[q] = cnt;
	
	for(int i=q;i>=1;i--)	//从后往前离线处理询问
	{
		int id = qq[i];
		
		int fa = find(p[id].first);
		int fb = find(p[id].second);
		
		int mn = min(fa,fb);
		int mx = max(fa,fb);
		
		if(mn >= n+1)	//最小的点都有发电站了
		{
			ans[i-1] = cnt;
			continue;
		}
		
		//一个有发电站，一个没有，此时合并时就要累加答案了
		if(mn < n+1 && mx >= n+1) cnt += sz[mn];
		
		if(fa != fb)	//在一个集合的时候就不用合并了！！！
		{
		    f[mn] = mx;
	    	sz[mx] += sz[mn];
		}
		
		ans[i-1] = cnt;
	}
	
	for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
}

signed main()
{
//	IOS;
	
	int t;
	t = 1;
//	ire(t);
//	cin>>t;
	while(t--)
	{
		solve();
	}
	
// 	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165