526互联

刷题 ST表、单调栈、线段树->区间最值

发布时间 2023-12-13 13:00:48作者: modemingzi

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)

要解决的就是区间最值了

三种思路

 

线段树

ST表

单调栈

 

线段树代码

 

#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;
}

ST表代码

 

#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;
    }
}