[noi simulation] regional division (conclusion, structure)

Topic

1s , 512mb

Answer key

First , If there are two neighboring cities with the same party, there must be no solution .

We found that , The final plan must have three adjacent cities in a triangle , And after connecting this triangle , It is equivalent to removing the middle city , The rest is another sub problem .

therefore , We count the number of adjacent triples that can form triangles $X$（ If a certain position $i$ Satisfy $a_i$ And its left and right positions just form a set $\{0,1,2\}$ , Can form a triple ）, It's not hard to find out , When we connect One Three triangles ,$X$ The reduction is Odd number , And there is a scheme to make it greater than zero . In the end, there must be three cities left , just $X$ Turn into 1 Of , therefore —— The answer is if and only if $X>0$ And $X$ And $n$ The parity of is the same .

How to make $X$ Constant is greater than zero ？ In fact, just try to use Edge triples —— If and only if a certain triple is related to the left and right triples The central city is adjacent when , This triplet No Edge triples . If there is no triplet on the edge , Of course, it's OK to choose any one . Because we found that , If you choose a non edge triple , Will make $X$ Reduce $3$ , At this time, only when they are all non edge triples can we guarantee that there are triples .

So we use set And linked list maintenance triples , Time complexity $O(n\log n)$ .

---

After reading the solution , I found myself a XX.

First , If there is no adjacent same city , be $X$ The parity of must be related to $n$ identical . That is, as long as $X>0$ There is a solution . And it's not difficult to prove , As long as it exists at the same time $0,1,2$ ,$X$ Greater than 0 .

then , There is a very simple construction method ：

CODE

Hit my stupid size , Avoiding my stupid responsibility

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN 100005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
#define eps 1e-6
int xchar() {
    
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
    
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {
    if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {
    x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {
    if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {
    putnum(x);putchar(c);}

int n,m,s,o,k;
int a[MAXN];
int l[MAXN],r[MAXN];
set<int> st,sp;
bool che(int x) {
    
	if(a[l[x]]^a[x]^a[r[x]]) return st.erase(x),0;
	return st.insert(x),1;
}
bool che2(int x) {
    
	if(!(a[l[x]]^a[x]^a[r[x]]) && ((a[l[l[x]]]^a[l[x]]^a[x]) || (a[x]^a[r[x]]^a[r[r[x]]]))) return sp.insert(x),1;
	return sp.erase(x),0;
}
void del(int x) {
    
	st.erase(x); sp.erase(x);
	int s = l[x],o = r[x];
	AIput(min(s,o)+1,' '); AIput(max(s,o)+1,'\n');
	r[s] = o; l[o] = s;
	che(s); che(o); che2(s); che2(o);
	che2(l[s]); che2(r[o]);
}
int main() {
    
	freopen("divide.in","r",stdin);
	freopen("divide.out","w",stdout);
	n = read();
	for(int i = 0;i < n;i ++) a[i] = read()+1;
	for(int i = 0;i < n;i ++) {
    
		if(a[i] == a[(i+1)%n]) return printf("No\n"),0;
		l[i] = (i+n-1)%n; r[i] = (i+1)%n;
	}
	for(int i = 0;i < n;i ++) che(i),che2(i);
	if((st.size()&1) == (n&1) && !st.empty()) {
    
		printf("Yes\n");
		for(int i = 1;i <= n-3;i ++) {
    
			int t = *st.begin();
			while(!sp.empty() && !che2(*sp.begin()));
			if(!sp.empty()) t = *sp.begin();
			del(t); while(!st.empty() && !che(*st.begin()));
		}
	}
	else printf("No");
	return 0;
}