线段树逆序对(偏序)——cf1187D好题!
2024-09-06 10:47:57
/*
排除掉所有不可能的情况,剩下的就是可行的
1.数的数量不相同
2.对任意一个区间进行排序,等价于可以交换任意逆序对,
那么从1到n扫描b数组,判断是否可以将a数组中等于b[i]的值所在的位置j交换到位置i,等价于判断区间a[i,j]是否存在<b[i]的数,判完后这个数不会再用到,所以改成无穷大
类似于一类偏序问题,可以建立线段树为维护动态区间最小值
*/
#include<bits/stdc++.h>
#include<queue>
using namespace std;
#define maxn 300005
#define inf 0x3f3f3f3f int a[maxn],b[maxn],ta[maxn],tb[maxn],n; #define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int Min[maxn<<];
void pushup(int rt){
Min[rt]=min(Min[rt<<],Min[rt<<|]);
}
void build(int l,int r,int rt){
if(l==r){
Min[rt]=a[l];
return;
}
int m=l+r>>;
build(lson);
build(rson);
pushup(rt);
}
void update(int pos,int val,int l,int r,int rt){
if(l==r){
Min[rt]=val;
return;
}
int m=l+r>>;
if(pos<=m)update(pos,val,lson);
else update(pos,val,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l && R>=r)return Min[rt];
int m=l+r>>,res=0x3f3f3f3f;
if(L<=m)res=min(res,query(L,R,lson));
if(R>m)res=min(res,query(L,R,rson));
return res;
} queue<int>q[maxn]; int main(){
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=;i<=n;i++){
cin>>a[i],ta[i]=a[i];
while(q[a[i]].size())q[a[i]].pop();
}
for(int i=;i<=n;i++)cin>>b[i],tb[i]=b[i];
sort(ta+,ta++n);sort(tb,tb++n);
int flag=;
for(int i=;i<=n;i++)
if(ta[i]!=tb[i])flag=;
if(!flag){
build(,n,);
for(int i=;i<=n;i++)
q[a[i]].push(i);
for(int i=;i<=n;i++){
int pos=q[b[i]].front();
q[b[i]].pop();
int tmp=query(,pos,,n,);
update(pos,inf,,n,);
if(tmp<b[i])flag=;
}
}
if(flag)puts("NO");
else puts("YES");
}
}
最新文章
- WPF模板
- ARCGIS常用几种本地数据AE初始化
- Alembic
- iOS----Asset Catalog的用法
- eclipse技巧总结
- Designing Evolvable Web API with ASP.NET 随便读,随便记 “The Internet,the World Wide Web,and HTTP”——HTTP
- C#控制台输入
- apache 工作模式
- ssh链接云主机的一些笔记
- sql 当重复的数据有多条时,保留一条,删除其他重复
- MySql索引原理与使用大全
- 使用Visual Studio 2010 - 初学者系列 - 学习者系列文章
- Jquery 实现原理之 Ajax
- JS实现轻量级计算器
- java基础(九章)
- Queuing(以前写的没整理)
- aspnetcore.webapi实战k8s健康探测机制 - kubernetes
- tensorflow 使用 4 非线性回归
- 廖雪峰 JavaScript 学习笔记(函数)
- kue