列表

详情

NC212619. Goddess

描述

The party began, the greasy uncle was playing cards, the fat otaku was eating, and the little beauty was drawing.

After the party for so long, why haven't you seen YHH? Oh, we almost forgot, a little beauty is drawing here! YHH watched her quietly and occasionally handed her a paintbrush.

However, your focus is quite strange: you have just found some rules about the colour of the brush, and now you want to use these rules to write out all the colour of the brushes that YHH handed to the little beauty. The rules are as following:

There are N areas on the little beauty's painting, some areas are adjacent, in order to make the adjacent areas can be distinguished, their colours need to be different, there are M adjacent relations in total;

Because the colour of some areas in the initial painting is wrong, or the colour of other adjacent areas is the same, the little beauty needs to make some adjustments. YHH does not need to care whether the other places are correct, but only need to meet the requirements of the little beauty every time.

The little beauty's brushes are arranged in rows, numbered starting from 0 according to the colour. Every time the little beauty needs to draw an area, YHH will pass a brush. And the colour of this brush is different from all colours of the adjacent area, and in order to be faster, YHH will take the closest one (the one with the smallest number);

Sometimes the little beauty is not satisfied with the colour of a particular area, so she will specify a colour to colour this area.

Now given two numbers N, M, representing the number of areas and the number of adjacent relationships on little beauty's painting. The next line contains N numbers, representing the initial colour of each area. And then M lines, each line contains two integers u, v represent the two adjacent areas.

Then given a number Q, representing the number of queries. In the following Q lines, each line includes a query. There are two forms of inquiry:

Type 1: 1 u x (0 ≤ x ≤ ) – Change the colour of area u to x.

Type 2: 2 u – At this time, the little beauty wants to draw area u, YHH will pass a brush according to the above rules, which number is what you should print.

输入描述

Each input file only contains one test case.

The first line contains two integers N, M (1 ≤ N, M ≤ ), indicating the number of areas and the number of adjacent relationships on the little beauty's painting.

The next line contains N integers a_1 , a_2 ,……, a_n (0 ≤ a_i ≤ ), indicating the initial color of area i.

Then following next M lines, each line contains two integers u, v (1 ≤ u, v ≤ N), indicating the two areas which are adjacent.

After that, the next line contains an integer Q (1≤ Q ≤ ), indicating the number of queries.

Then following Q lines contain queries described in the description.

输出描述

For each query of type 2, print an integer, indicating the number of brush that YHH passed to little beauty.

示例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

输出: 

2
2
0

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 1346ms, 内存消耗: 12052K, 提交时间: 2020-09-26 21:47:08 

#include <bits/stdc++.h>
 
using namespace std;
const int N=1e5+10;
int a[400][N],b[400][N],col[N],in[N],tot,id[N],n;
vector<int>G[N],V[N];
int lowbit(int x){return x&(-x);}
void update(int x,int op,int num){
	a[num][x]+=op;
	if(a[num][x]==1&&op==1){
	    for(;x<=n;x+=lowbit(x))b[num][x]+=1;
	}
	else if(a[num][x]==0&&op==-1){
		for(;x<=n;x+=lowbit(x))b[num][x]-=1;
	}
	else return ;
}
int getsum(int x,int num){
	int ans=0;
	for(;x;x-=lowbit(x))ans+=b[num][x];
	return ans;
}
int main(){
	int m;scanf("%d %d",&n,&m);
	int sqrtn=600;
	for(int i=1;i<=n;i++)scanf("%d",&col[i]),col[i]++;
	for(int i=1;i<=m;i++){
		int a,b;scanf("%d %d",&a,&b);
		G[a].push_back(b);
		G[b].push_back(a);
		in[a]++,in[b]++;
	}
	for(int i=1;i<=n;i++)if(in[i]>sqrtn)id[i]=++tot;
	for(int i=1;i<=n;i++){
		for(auto it:G[i]){
			if(in[it]>sqrtn){
				V[i].push_back(it);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(in[i]<=sqrtn&&col[i]<=n){
			//cout<<V[i].size()<<endl;
			for(auto it:V[i])update(col[i],1,id[it]);
		}
	}
	int q;scanf("%d",&q);
	while(q--){
		int op;scanf("%d",&op);
		if(op==1){
			int u,x;scanf("%d %d",&u,&x);x++;
			if(in[u]>sqrtn){
				col[u]=x;
			}else {
				if(col[u]<=n){
					for(auto it:V[u]){
						update(col[u],-1,id[it]);
					}
				}
				col[u]=x;
				if(col[u]<=n){
					for(auto it:V[u]){
						update(col[u],1,id[it]);
					}
				}
			}
		}else {
			int u;scanf("%d",&u);
			if(in[u]>sqrtn){
				for(auto it:V[u]){
					if(col[it]<=n)update(col[it],1,id[u]);
				}
				int l=1,r=n,ans=-1;
				while(l<=r){
					int mid=l+r>>1;
					if(getsum(mid,id[u])<mid){
						ans=mid;
						r=mid-1;
					}else l=mid+1;
				}
				if(ans==-1)ans=n+1;
				for(auto it:V[u]){
					if(col[it]<=n)update(col[it],-1,id[u]);
				}	
				col[u]=ans;
				printf("%d\n",ans-1);
			}else {
				set<int>st;
				if(col[u]<=n){
					for(auto it:V[u])
					update(col[u],-1,id[it]);
				}
				for(auto it:G[u])st.insert(col[it]);
				int now=1;
				for(auto it:st){
					if(it!=now)break;
					now++;
				} 
				col[u]=now;
				if(col[u]<=n){
					for(auto it:V[u])
					update(col[u],1,id[it]);
				}
				printf("%d\n",now-1);
			}
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 981ms, 内存消耗: 63000K, 提交时间: 2020-09-26 19:52:31 

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
vector<int> g[maxn], big[maxn];
int t,n,m,a[maxn],q;
int sqr;
struct block {
	int n, siz;
	vector<int> b;
	vector<int> sum;
	void init(int tot) {
		b.resize(tot + 1);
		siz = 300;
		sum.resize(tot / siz + 1);
		n = tot;
	}
	void update(int val,int t) {
		if (val > n) return ;
		if (t == 1) {
			b[val] += t;	
			if (b[val] == 1) 
				sum[val / siz]++;
		} else {
			b[val] += t;
			if (b[val] == 0)
				sum[val / siz]--;
		}
	}
	int qry() {
		for (int j = 0; j <= n / siz; j++) {
			if (sum[j] < siz) {
				int ed = min(n,(j + 1) * siz - 1);
				for (int k = j * siz; k <= ed; k++)
					if (!b[k]) return k;
			}
		}
	}
	void clear() {
		for (int i = 0; i <= n; i++)
			b[i] = 0;
		for (int i = 0; i <= n / siz; i++)
			sum[i] = 0;
	}
	void free() {
		sum.resize(0); 
		b.resize(0);
		n = siz = 0;
	}
}B[maxn]; 
int main() {
	t = 1;
	while (t--) {
		scanf("%d%d",&n,&m);
		sqr = 300;
		for (int i = 1; i <= n; i++)
			scanf("%d",&a[i]);
		for (int i = 1, x, y; i <= m; i++) {
			scanf("%d%d",&x,&y);
			g[x].push_back(y);
			g[y].push_back(x);
		}
		for (int i = 1; i <= n; i++) {
			B[i].init(g[i].size());
		}
		for (int i = 1; i <= n; i++) {
			for (auto it : g[i]) {
				B[i].update(a[it],1);
				if (g[it].size() > sqr)
					big[i].push_back(it);
			}
		}
		scanf("%d",&q);
		while (q--) {
			int c, x, y;
			scanf("%d%d",&c,&x);
			if (c == 1) {
				scanf("%d",&y);
				for (auto v : big[x])
					B[v].update(a[x],-1);
				a[x] = y;
				for (auto v : big[x])
					B[v].update(a[x],1);
			} else {
			    int y;
				if (g[x].size() > sqr)
                {
                    y = B[x].qry();
                    printf("%d\n",y);
                }
					
				else {
					B[x].clear();
					for (auto v : g[x])
						B[x].update(a[v],1);
                    
					y = B[x].qry();
                    printf("%d\n",y);
				}
				
				for (auto v : big[x])
					B[v].update(a[x],-1);
				a[x] = y;
				for (auto v : big[x])
					B[v].update(a[x],1);
			}
		}		
	}
	return 0;
}

上一题

© 2024 nowcoder.com