ビルの Decoration り pay け 4

Topic link ：luogu P6891

The main idea of the topic

Here are two lengths for you 2n Sequence , Then you have to gather one 2n Each position of the sequence can be selected from the corresponding position in the two sequences .
Then you need to ensure that the sequence you get is monotonic and that both sequences are used n individual .
You need to judge whether there is no solution or output one of the legal solutions .

Ideas

On the subject

The first one is obvious DP set up $f_{i,j,0/1}$ For the former $i$ One of the first sequences used $j$ One last, one first / Is there an answer to the second sequence .
And then this is $n^2$ Of , Consider some nature .

Observe the appearance of the edge , You will find that there are such restrictions .
There are some places where you can only choose one , In some places, you can't choose one after choosing one .
（ It's small enough to connect two , Big ones can only be connected with one , From the perspective of not being able to connect, this is the case ）

The front one is easy to do , Consider the following limitations , The whole graph can certainly be divided into several complementary constraints , Then the limitation of connection will form a chain , Specifically, the adjacent two on the chain cannot be selected at the same time .
The quantity selected for each chain is an interval , The sum of those intervals is also an interval , So we can draw such a conclusion ：
The number of two sequences that can be selected is in an interval .

Because of complementarity , We can separate DP Out $f_{i,0/1,0/1}$ For the former $i$ The last one is the first sequence or the second , How many can you choose from the first sequence or the second sequence at most .
So as long as the maximum value of both sequences is greater than the requirement , It falls into the interval .

Then we ask for a plan , Let's push backwards , If you can still meet the conditions, choose , Then if you are not satisfied with either choice, there is no solution .

ex Bupleurum

Niuke has an upgraded version of this one , It requires legal choice , I'm too lazy to write here .

Let's continue to see from the proof , Let's consider each link , Assumed length is $x$, We have to choose among them $y$ individual , The inserting method is ：
$\left(\genfrac{}{}{0ex}{}{x-y+1}{y}\right)$（ The subtracted ones are put behind the ones you choose, and you are forced not to choose ）

Then you make these polynomials , Then it is not difficult to see that several polynomials multiply to take a certain term , Divide and conquer directly + NTT that will do .

Code

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int N = 1e6 + 100;
int n, a[N][2], f[N][2][2];
char ans[N];

int main() {
    
	scanf("%d", &n);
	for (int i = 1; i <= n << 1; i++) scanf("%d", &a[i][0]);
	for (int i = 1; i <= n << 1; i++) scanf("%d", &a[i][1]);
	
	memset(f, -0x7f, sizeof(f));
	f[1][0][0] = 1; f[1][0][1] = 0; f[1][1][0] = 0; f[1][1][1] = 1;
	for (int i = 2; i <= n << 1; i++) {
    
		if (a[i - 1][0] <= a[i][0]) {
    
			f[i][0][0] = max(f[i][0][0], f[i - 1][0][0] + 1); f[i][0][1] = max(f[i][0][1], f[i - 1][0][1]);
		}
		if (a[i - 1][1] <= a[i][0]) {
    
			f[i][0][0] = max(f[i][0][0], f[i - 1][1][0] + 1); f[i][0][1] = max(f[i][0][1], f[i - 1][1][1]);
		}
		if (a[i - 1][0] <= a[i][1]) {
    
			f[i][1][0] = max(f[i][1][0], f[i - 1][0][0]); f[i][1][1] = max(f[i][1][1], f[i - 1][0][1] + 1);
		}
		if (a[i - 1][1] <= a[i][1]) {
    
			f[i][1][0] = max(f[i][1][0], f[i - 1][1][0]); f[i][1][1] = max(f[i][1][1], f[i - 1][1][1] + 1);
		}
	}
	
	int numa = 0, numb = 0, lst = 2e9;
	for (int i = n << 1; i >= 1; i--) {
    
		if (numa + f[i][0][0] >= n && numb + f[i][0][1] >= n && a[i][0] <= lst) {
    
			numa++; ans[i] = 'A'; lst = a[i][0];
		}
		else if (numa + f[i][1][0] >= n && numb + f[i][1][1] >= n && a[i][1] <= lst) {
    
			numb++; ans[i] = 'B'; lst = a[i][1];
		}
		else {
    
			printf("-1"); return 0;
		}
	}
	for (int i = 1; i <= n << 1; i++) putchar(ans[i]);
	
	return 0;
}