实验室外的攻防战 UOJ#180 [树状数组]

题目

时针指向午夜十二点，约定的日子——2月28日终于到来了。随着一声枪响，伏特跳蚤国王率领着他的跳蚤大军们包围了 \(picks\) 博士所在的实验室。

当然，\(picks\) 博士不会坐以待毙，他早就率领着他的猴子们在实验室外修筑了许多的坚固防御工事。

经过跳蚤侦察兵的勘察，跳蚤国王发现 \(picks\) 博士的防御工事有着 \(n\) 处薄弱点，于是他把他的跳蚤大军分成了 \(n\) 支小队，并打算让它们分别进攻每一个薄弱点。但是因为战场混乱，这 \(n\) 支小队的位置被打乱了，重新整队之后，跳蚤国王发现第 \(i\) 个位置的小队编号为 \(A_i\)（显然 \(A\) 是一个排列）。

经过计算，跳蚤国王发现，让第 \(i\) 个位置的小队编号为 \(B_i\) 时，他的军队可以发挥出最大的战斗力（保证 \(B\) 也是一个排列）。

跳蚤国王可以发出指令来改变小队们的排列顺序，每一次，他都会报出一个整数 \(i\ (1\leqslant i< n)\) 。如果排在第 \(i\) 个位置的小队编号大于第 \(i+1\) 个位置的小队，那么这两支小队会交换顺序，否则这一个命令将会被忽略。

现在跳蚤国王希望他的军队能够发挥出最强大的战斗力，于是他想要知道是否存在一种指令序列，使得小队们可以按照排列 \(B\) 的方式排列。

但是因为小队数目实在是太多，跳蚤国王一时间也没有看出答案。于是他派跳蚤绑架来了你——这附近最著名的民间科学家来帮他计算这个问题的答案。

输入格式

输入数据第一行包含一个正整数 \(n\) 。

接下来两行每行 \(n\) 个正整数，分别描述排列 \(A\) 和排列 \(B\) 。

输出格式

对于每组数据，如果存在这样的指令序列，输出YES，否则输出NO(引号不输出，请注意大小写)。

样例

样例输入1

3

2 3 1

2 1 3

样例输出1

YES

explanation

只要报出 \(2\) ，也就是交换第 \(2\) 个位置和第 \(3\) 个位置的小队即可。

样例输入2

3

2 1 3

3 1 2

样例输出2

NO

explanation

注意只有相邻的满足前一个数大于后一个数的情况下才可以交换。

样例输入3

5

4 1 2 5 3

1 2 4 3 5

样例输出3

YES

explanation

步骤如下(每次交换的两个数加粗表示)：

样例输入4

5

1 5 3 4 2

1 2 4 3 5

样例输出4

NO

样例输入5

8

8 2 7 4 5 3 6 1

2 8 5 7 4 3 6 1

样例输出5

NO

限制与约定

1	24	\(n\leqslant 8\)
2	32	\(n\leqslant 1000\)
3	44	\(n\leqslant 100000\)

对于所有数据，\(1\leqslant n\leqslant 100000\) ，保证输入的 \(A\) 和 \(B\) 均为一个排列。

时间限制：\(1\ s\)

空间限制：\(256MB\)

分析

又是一个偏序的题，给出一个 \(A\) 序列，让你判断能否通过符合要求的转换，使其转化成 \(B\) 序列。

我们可以得到这样一个结论：设有两个值 \(i\)，\(j\) 满足 \(i<j\) ，如果 \(posa_i < posa_j\) 并且 \(posb_i > posb_j\)，那么这种情况一定是不成立的。证明就是要想从左移到右边，必须满足 \(i>j\) 但是这里 \(i<j\) ，所以一定是不成立的。那么我们就可以用树状数组来维护一下。

我们记录下来每个值的位置，并且在修改的时候以 \(A\) 序列中的位置作为下标， \(B\) 序列中的位置作为值，维护一个最大值。这样我们在查询的时候枚举数值，每一次查询 \(A\) 序列中值的位置，查询到的结果就是 \(i<j\) 且 \(posa_i < posa_j\) 的最大的 \(posb_j\) 这样我们只需要比较一下这个值和当前枚举到的 \(i\) 值的 \(posb_i\) ，就能得到答案。

代码

#include<cstdio>

//以下好多行都是卡常

const int L=1<<20;

char buffer[L],*S,*T;

#define lowbit(x) (x & -x)

#define getchar() (S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T)?EOF:*S++)

#define inline __inline__ __attribute__((__always_inline__))

#define max(a,b) (a>b?a:b)

#define re register

//从这里开始正经

const int maxn = 1e5+10;

int n;

int t[maxn];

int posa[maxn],posb[maxn];

inline int read(){

	re int s = 0,f = 1;

	re char ch = getchar();

	while(ch < '0' || ch > '9'){

		if(ch == '-')f = -1;

		ch = getchar();

	}

	while(ch >= '0' && ch <= '9'){

		s = (s<<3) + (s<<1) + ch - '0';

		ch = getchar();

	}

	return s * f;

}

inline void modify(re int x,re int val){//树状数组维护最大值

	while(x <= n){

		t[x] = max(t[x],val);

		x += lowbit(x);

	}

}

inline int query(re int x){//查询

	re int ans = 0;

	while(x){

		ans = max(ans,t[x]);

		x -= lowbit(x);

	}

	return ans;

}

int main(){

	n = read();

	for(re int i=1;i<=n;++i){//记录值在A序列中的位置

		posa[read()] = i;

	}

	for(re int i=1;i<=n;++i){//记录值在B序列中的位置

		posb[read()] = i;

	}

	for(re int i=1;i<=n;++i){//枚举数值，依次查询A序列中i的位置

		if(query(posa[i]) > posb[i]){//如果有上边所说的冲突情况直接NO

			puts("NO");

			return 0;

		}

		modify(posa[i],posb[i]);

	}

	puts("YES");//没有输出NO就是合法的

	return 0;

}