树状数组维护前缀最大值

https://leetcode.cn/contest/hhrc2022/

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std; 

typedef long long ll;

const int maxn=2e5+10;
int cnt=2e5+10;

class Solution {
public:
    int cnt=2e5+10;
    
    int a[maxn],num[maxn];

    void add( int x,int c ) { while( x<=cnt ) num[x]=min(num[x],c),x+=lowbit(x); }
    int query( int x,int ans=2e5 ) { while( x ) ans=min(ans,num[x]),x-=lowbit(x);return ans; }

    int longestESR(vector<int>& b) {
        int n=b.size();
        int sum = 0,ans=0;
	    memset(num,0x3f3f3f3f,sizeof(num));
        for( int i=0;i<b.size();i++ ){
            if( b[i]>8 ) b[i]=1;
            else b[i]=-1;
            sum+=b[i];
            ans=max(ans,(int)(i+1e4-query(sum-1+1e4)));
            add(sum+1e4,i);
            if( sum>0 ) ans=max(ans,i+10001);
        }
        
        return max(ans-10000,0);
    }
};