为什么直接单调队列不行
查看原帖
为什么直接单调队列不行
315205
Kniqht楼主2023/7/21 16:28

rt,能举出一个反例吗,我没想出来问题在哪里啊

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<utility>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e6+10;
ll n,q[N],hh,tt,a[N];
signed main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    int ans=0,cnt=0;tt=-1;
    for(ll i=1;i<=n;i++){
        ans+=cnt;
        while(hh<=tt&&a[q[tt]]<a[i]) tt--,cnt--;
        q[++tt]=i,cnt++;
        // printf("%lld\n",cnt);
    }   
    printf("%lld",ans);
	return 0;
}
/*
2 
4 
1 
2 
2 
5 
1

2
4
4 1
4 2
4 2 2
5
5 1







*/
2023/7/21 16:28
加载中...