牛客练习赛25 最长区间

其中表示left_len right_len可以用一个Len[i] 表示 len[i]表示包括i的在i之前的最长递增序列 用Len数组可以很方便得记录到从x往左的left_len等于多少  然后向由可以推出right_len

cnt[i ]计算每一个长度i的序列有多少个 其中 一个i的子长度的序列也会记录

更新a[x]后 只会改变x左右的值 例如 如果ax比ax-1要小了 则len[x]=1; 如果比ax-1大则len[x]=len[x-1]+1以此向后类推 因为a数组的值就为1-100所有严格递增序列最长也就100

牛客的题解：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int a[maxn],len[maxn];
int cnt[105];
int solve(){
for(int i=100;i>=1;i--)
    if(cnt[i])return i;
    return 1;
}
 
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
 
            memset(cnt,0,sizeof(cnt));
            memset(len,0,sizeof(len));
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        a[0]=10000;
        len[1]=1;
 
        for(int i=2;i<=n;i++){
        if(a[i]>a[i-1]){
           len[i]=len[i-1]+1;
        }
        else {
 
            len[i]=1;
        }
        cnt[len[i]]++;
 
        }
 
        printf("%d\n",solve());
        while(m--){
            int x,y;
            scanf("%d%d",&x,&y);
            a[x]=y;
            for(int i=x;i<=min(x+101,n);i++){
                    cnt[len[i]]--;
                    if(a[i]>a[i-1])len[i]=len[i-1]+1;
                    else len[i]=1;
                    cnt[len[i]]++;
 
            }
            printf("%d\n",solve());
 
        }
 
 
    }
 
 
    return 0;
}