2023.12.13 cf1904D2
解题思路
首先，a[i]大于b[i]时肯定不行，等于就满足了，直接过掉
其次，要想使得a[i]等于b[i]，就要在a[i]左右找最近的j使得a[j]=b[i]（最近的最优，可证）
k是i和j中间的一个数，想要满足题意，要满足以下两个条件(a[j]=b[i])
1.ak<aj，即max(区间[i,j]中的ak)
2.bk>bi，即min(区间[i,j]中的bk)
要解决的就是区间最值了
三种思路
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int a[N], b[N];
struct Node
{
int l, r, mx, mi;
}tr[4 * N];
void pushup(int u)
{
Node& root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
root.mx = max(left.mx, right.mx);
root.mi = min(left.mi, right.mi);
}
void build(int u, int l, int r)
{
tr[u].l = l, tr[u].r = r;
if(l == r)
{
tr[u].mx = a[l], tr[u].mi = b[l];
return ;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
int query_max(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].mx;
int mid = tr[u].l + tr[u].r >> 1;
int ans = 0;
if(mid >= l) ans = query_max(u << 1, l, r);
if(mid < r) ans = max(ans, query_max(u << 1 | 1, l, r));
return ans;
}
int query_min(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].mi;
int mid = tr[u].l + tr[u].r >> 1;
int ans = INF;
if(mid >= l) ans = query_min(u << 1, l, r);
if(mid < r) ans = min(ans, query_min(u << 1 | 1, l, r));
return ans;
}
int main()
{
int tt;
cin >> tt;
while(tt--)
{
int n;
cin >> n;
vector<bool> v(n + 5, false);
vector<vector<int>> pos(n + 5);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++) pos[i].push_back(0);
for(int i = 1; i <= n; i++) pos[a[i]].push_back(i);
for(int i = 1; i <= n; i++) pos[i].push_back(n + 1);
build(1, 1, n);
for(int i = 1; i <= n; i++)
{
if(a[i] == b[i])
{
v[i] = true; continue;
}
if(a[i] < b[i])
{
int r_idx = upper_bound(pos[b[i]].begin(), pos[b[i]].end(), i) - pos[b[i]].begin();
int l = pos[b[i]][r_idx - 1], r = pos[b[i]][r_idx];
if(l != 0)
{
if(query_max(1, l, i) <= b[i] && query_min(1, l, i) >= b[i]) v[i] = true;
}
if(r != n + 1)
{
if(query_max(1, i, r) <= b[i] && query_min(1, i, r) >= b[i]) v[i] = true;
}
}
}
bool ok = true;
for(int i = 1; i <= n; i++)
{
if(!v[i])
{
ok = false;
break;
}
}
cout << (ok ? "YES" : "NO") << '\n';
}
return 0;
}
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
#define ll long long
const int N=200005;
int mx[N][25],mn[N][25];
int a[N],b[N];
int query_max(int l,int r)
{
int k=log2(r-l+1);
return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
int query_min(int l,int r)
{
int k=log2(r-l+1);
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<bool> ans(n+5,false);
vector<vector<int>> pos(n+5);//用来找j
for(int i=1;i<=n;i++)pos[i].push_back(0);//下界哨兵
for(int i=1;i<=n;i++)
{
cin>>a[i];
mx[i][0]=a[i];
pos[a[i]].push_back(i);
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
mn[i][0]=b[i];
}
for(int i=1;i<=n;i++)pos[i].push_back(n+1);//上界哨兵
for(int j=1;j<=19;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=n;i++)
{
if(a[i]==b[i])
{
ans[i]=true;
continue;
}
if(a[i]<b[i])
{
int r_idx=upper_bound(pos[b[i]].begin(),pos[b[i]].end(),i)-pos[b[i]].begin();
//当两个迭代器相减，得到的是它们之间的距离，即元素的个数，一般应该要加一，但这里有哨兵不用
int l=pos[b[i]][r_idx-1],r=pos[b[i]][r_idx];
if(l)
{
if(query_max(l,i)<=b[i]&&query_min(l,i)>=b[i])ans[i]=true;
}
if(r!=n+1)
{
if(query_max(i,r)<=b[i]&&query_min(i,r)>=b[i])ans[i]=true;
}
}
}
bool ok=true;
for(int i=1;i<=n;i++)
{
if(!ans[i])
{
ok=false;
break;
}
}
cout<<(ok?"YES":"NO")<<endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LLINF = 1e18;
void setIO()
{
ios_base::sync_with_stdio(0); cin.tie(0);
}
int main(){
setIO();
int T;
cin >> T;
for(int tt = 1; tt <= T; tt++)
{
int n;
cin >> n;
int a[n + 1], b[n + 1];
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
bool val[n + 1];
memset(val, false, sizeof(val));
for(int t = 0; t < 2; t++)
{
int prvb[n + 1]; //前一个比b[i]小的值的下标
int nxta[n + 1]; //后一个比a[i]大的值的下标
stack<pii> s;
s.push({INF, n + 1});
for(int i = n; i >= 1; i--)
{
while(s.top().ff <= a[i]) s.pop();
nxta[i] = s.top().ss;
s.push({a[i], i});
}
while(!s.empty()) s.pop();
s.push({0, 0});
for(int i = 1; i <= n; i++)
{
while(s.top().ff >= b[i]) s.pop();
prvb[i] = s.top().ss;
s.push({b[i], i});
}
int m[n + 1];
memset(m, 0, sizeof(m));
for(int i = 1; i <= n; i++)
{
m[a[i]] = i;
if(a[i] <= b[i] && m[b[i]]) val[i] |= prvb[i] < m[b[i]] && nxta[m[b[i]]] > i;
}
reverse(a + 1, a + n + 1);//第一遍只考虑了[i,j]，反转后就是考虑[j,i]
reverse(b + 1, b + n + 1);
reverse(val + 1, val + n + 1);
}
bool ans = true;
for(int i = 1; i <= n; i++) ans &= val[i];
cout << (ans ? "YES" : "NO") << endl;
}
}