UOJ小清新题表
题目内容
依然没有粘题面主要是UOJ的题面都太长了qwq
一句话题意：给出两个序列 (A) 和 (B)，对于 (A) 进行若干次操作，每次给出一个 (i)，若 (A_i>A_{i+1}) 则可交换。问能否通过若干次操作后把 (A) 序列转化为 (B) 序列。
数据范围
| 子任务 | 分值 | 限制与约定 |
|---|---|---|
| 1 | 24 | (nleq 8) |
| 2 | 32 | (nleq 1000) |
| 3 | 44 | (nleq 100000) |
思路
好像是一道三维偏序题。可以先想想冒泡排序的运行方式。
首先有一个显然的性质。若遍历到两个数 (i) 和 (j) 且 (i<j)，若在 (A) 序列中 (i) 在 (j) 之前，在 (B) 序列中 (i) 在 (j) 之后，那么永远都无法将其转化为符合条件的位置。当我们遍历到这样的情况的时候，直接输出NO就完了。
形式化的说，不满足条件的限制就是：存在对于 (i<j) 的两个数，使得 (a[i]<a[j])，(b[i]>b[j])。其中 (a[i]) 表示 (i) 在 (A) 序列的位置，(b[i]) 表示 (i) 在 (B) 序列中的位置，这个直接在读入的时候就已经处理好了。
此题判断其存在性即可。对于 (i<j)，可以从小到大枚举每一个 (j)，找出所有的 (a[i]<a[j]) 中 (b[i]) 的最大值，判断其是否大于 (b[j])，若不符合，加入 (j) 即可，否则直接输出NO。
若最终都无法找到，则答案为YES。
然后剩下的就是随便找一个数据结构维护一下最大值就行了，这里采用的是树状数组。
可能有点混乱，看代码应该能懂
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n;
int a[maxn],b[maxn],tree[maxn];
inline int read(){
int x=0,fopt=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=-1;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;
return x*fopt;
}
inline int lowbit(int x){
return x&-x;
}
inline void modify(int x,int b){
while(x<=n){
tree[x]=max(tree[x],b);
x+=lowbit(x);
}
}
inline int query(int x){
int ans=-1;
while(x){
ans=max(ans,tree[x]);
x-=lowbit(x);
}
return ans;
}
int main(){
n=read();
for(int i=1;i<=n;i++)
a[read()]=i;
for(int i=1;i<=n;i++)
b[read()]=i;
for(int i=1;i<=n;i++)
if(query(a[i])>b[i])return puts("NO"),0;//询问所有下标小于等于i的最大值
else modify(a[i],b[i]);//交换操作，直接一步到胃
puts("YES");
return 0;
}