乱搞做法求调
查看原帖
乱搞做法求调
232796
Deson楼主2022/4/1 23:04

写了一个疑似单调队列的做法,开了O2民间能过但是官方的过不了求助各位帮忙看一下谢谢大佬

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
int a[maxn],b[maxn];
int main(){
    // freopen("stack.in","r",stdin);
    // freopen("stack.out","w",stdout);
    ios::sync_with_stdio(0);
    int n,q;
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    for(int i=1;i<=n;i++){
        cin >> b[i];
    }
    a[n+1] = 10000000;
    b[n+1] = 10000000;
    stack<int>s;
    int w[maxn];
    for(int i=1;i<=n+1;i++){
        //我比你高 = 我的b>你的b或者我的a == 你的a
        while(!s.empty()){
            int x = s.top();
            if(b[i]>=b[x]){
                w[x] = i;
                s.pop();
            }
            else if(a[i] == a[x]){
                w[x] = i;
                s.pop();
            }
            else break;
        }
        s.push(i);
    }
    for(int i=1;i<=q;i++){
        int l,r;
        cin >> l >> r;
        int ans = 0;
        for(int j = l;j<=r;){
            ans++;
            j = w[j];
        }
        cout << ans << '\n';
    }
    return 0;
}
2022/4/1 23:04
加载中...