2020杭电多校第一场 Finding a MEX（分块+树状数组，维护MEX）

本文主要是介绍2020杭电多校第一场 Finding a MEX（分块+树状数组，维护MEX），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
Given an undirected graph G=(V,E). All vertices are numbered from 1 to N. And every vertex u has a value of Au. Let Su={Av│(u,v)∈E}. Also, F(u) equals MEX(minimum excludant) value of Su. A MEX value of a set is the smallest non-negative integer which doesn’t exist in the set.

There are two types of queries.

Type 1: 1 u x – Change Au to x (0≤x≤109).
Type 2: 2 u – Calculate the value of F(u).

For each query of type 2, you should answer the query.

Input
The first line of input contains a single integer T (1≤T≤10) denoting the number of test cases. Each test case begins with a single line containing two integers n (1≤n≤105), m (1≤m≤105) denoting the number of vertices and number of edges in the given graph.

The next line contains n integers and ith of them is a value of Ai (0≤Ai≤109).

The next m lines contain edges of the graph. Every line contains two integers u, v meaning there exist an edge between vertex u and v.

The next line contains a single integer q (1≤q≤105) denoting the number of queries.

The next q lines contain queries described in the description.

Output
For each query of type 2, output the value of F(u) in a single line.

Sample Input
1
5 4
0 1 2 0 1
1 2
1 3
2 4
2 5
5
2 2
1 2 2
2 2
1 3 1
2 1

Sample Output
2
2
0

Source
2020 Multi-University Training Contest 1

题意：
一个图，每个点有权值。
每个点有一个出边点的权值组成的集和。
操作为改变一个点的权值，和求解每个点的mex值。

思路：
小范围暴力，大范围单独考虑。这个范围的界限是分块，回忆起以前写过的一道并查集，也是这个思路。
https://blog.csdn.net/tomjobs/article/details/106891877

本题可以将块设置为450，小于这个范围的点，改变直接跑出边改变每个出边对应的点的点集。大范围点只改变自己。

那么每次查询的时候，每个点点集中的小点全部算出来了，然后再遍历其所有大范围点得到整个点集，再利用树状数组跑二分得到MEX值。

因为小范围的点遍历复杂度为$\sqrt{n}$，大范围点一共只有$\sqrt{n}$，所以复杂度为$\sqrt{n}\ast n\ast logn$

#include<iostream>
#include<cstring>
#include <cstdio>
#include <algorithm>
#include <vector>using namespace std;const int maxn = 2e5 + 7;
const int SZ = 450;int lim[maxn],a[maxn];
vector<int>mp[maxn],BIT[maxn];
vector<int>G[maxn],g[maxn];int sum(int u,int x) {int res = 0;while(x) {res += BIT[u][x];x -= x & (-x);}return res;
}void add(int u,int x,int d) {if(x > G[u].size()) return;while(x <= G[u].size()) {BIT[u][x] += d;x += x & (-x);}
}int main() {int T;scanf("%d",&T);while(T--) {int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);a[i]++;G[i].clear(),g[i].clear();BIT[i].clear();mp[i].clear();}for(int i = 1;i <= m;i++) {int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}for(int i = 1;i <= n;i++) {lim[i] = G[i].size();BIT[i].resize(lim[i] + 2);mp[i].resize(lim[i] + 2);for(int j = 0;j < G[i].size();j++) {int v = G[i][j];if(G[v].size() > SZ) {g[i].push_back(v);}}}for(int i = 1;i <= n;i++) {if(G[i].size() <= SZ) {for(int j = 0;j < G[i].size();j++) {int v = G[i][j];if(a[i] > lim[v]) continue;mp[v][a[i]]++;if(mp[v][a[i]] == 1) add(v,a[i],1);}}}int q;scanf("%d",&q);while(q--) { //小点直接维护，大点单独维护int op;scanf("%d",&op);if(op == 1) {int x,y;scanf("%d%d",&x,&y);y++;if(G[x].size() > SZ) {a[x] = y;} else {for(int i = 0;i < G[x].size();i++) {int v = G[x][i];if(a[x] > lim[v]) continue;mp[v][a[x]]--;if(mp[v][a[x]] == 0) add(v,a[x],-1);}a[x] = y;for(int i = 0;i < G[x].size();i++) {int v = G[x][i];if(a[x] > lim[v]) continue;mp[v][a[x]]++;if(mp[v][a[x]] == 1) add(v,a[x],1);}}} else {int x;scanf("%d",&x);for(int i = 0;i < g[x].size();i++) {int v = g[x][i];if(a[v] > lim[x]) continue;mp[x][a[v]]++;if(mp[x][a[v]] == 1) add(x,a[v],1);}int l = 1,r = G[x].size();int ans = 1;while(l <= r) {int mid = (l + r) >> 1;if(sum(x,mid) == mid) {ans = l = mid + 1;} else {r = mid - 1;}}printf("%d\n",ans - 1);for(int i = 0;i < g[x].size();i++) {int v = g[x][i];if(a[v] > lim[x]) continue;mp[x][a[v]]--;if(mp[x][a[v]] == 0) add(x,a[v],-1);}}}}return 0;
}

这篇关于2020杭电多校第一场 Finding a MEX（分块+树状数组，维护MEX）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---