Google Kickstart2022 Round G Problem C 快乐子数组

有点思路，但还需要细想

思路

一眼上去，应该是写单调队列，但是不是像写滑动窗口一样写
设前缀和为pre,如果一个区间\([l,r]\)满足条件，那么\(pre[l-1]<min(pre[l],pre[l+1],.....,pre[r]\)
根据这一点，
我们每次枚举到i，只需要统计左端有多少个相对应的j使得pre[j]<pre[i]即可，这时就可以用单调队列，维护一个单调递增的pre队列，使得队列中的值始终小于pre[i]，这时队列中的任意一个pre都可以与pre[i]满足题意
再结合代码应该能懂了

CODE

#include<bits/stdc++.h>

using namespace std;
#define ll long long 
int n;
int t;
const int maxn=4e5+10;
int q[maxn<<1];
ll pre[maxn];
ll ans=0;
void solve(){
    cin>>n;
    
    int l=1,r=0;q[++r]=0;
    ll sum=0;
    for(int i=1;i<=n;++i){
        cin>>pre[i];
        pre[i]+=pre[i-1];
    }
    for(int i=1;i<=n;++i){
        while(l<=r && pre[q[r]]>pre[i]){
            sum-=pre[q[r]];
            --r;
        }
        if(r-l+1>0) ans+=(ll)pre[i]*(r-l+1)-sum;
        sum+=pre[i];
        q[++r]=i;
    }
    
    return ;
}
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>t;
    for(int i=1;i<=t;++i){
        ans=0;
        solve();
        cout<<"Case #"<<i<<": "<<ans<<endl;
    }
    return 0;
}

反思

虽然上去一眼想到了做法，单调队列，因为与模板有点像，但是具体实施时又发现貌似不好处理符合区间的值

从这个题中我们可以学到的是，单调队列的维护对象可以是多种多样的，不一定和模板是相同的