欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

nowcoder911L 最优子区间

程序员文章站 2022-03-20 14:35:57
题目链接 思路 用$f(i,j)$表示前i个元素,以i为右端点,j为左端点时的答案。 用个"区间修改,单点查询"的线段树维护出第二维。在从左往右枚举i的过程中。将$[lst_i+1,i]$的答案+1.将$[lst_{lst_i}+1,lst_i]$的答案 1。 代码 cpp / @Author: w ......

题目链接

思路

\(f(i,j)\)表示前i个元素,以i为右端点,j为左端点时的答案。

用个"区间修改,单点查询"的线段树维护出第二维。在从左往右枚举i的过程中。将\([lst_i+1,i]\)的答案+1.将\([lst_{lst_i}+1,lst_i]\)的答案-1。

代码

/*
* @author: wxyww
* @date:   2019-06-05 11:13:19
* @last modified time: 2019-06-05 11:39:04
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 100000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int tree[n << 2],lazy[n << 2];
void pushdown(int rt) {
    if(lazy[rt]) {
        tree[rt << 1] += lazy[rt];
        tree[rt << 1 | 1] += lazy[rt];
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
    }
}
void update(int rt,int l,int r,int l,int r,int c) {
    if(l >= l && r <= r) {
        lazy[rt] += c;
        tree[rt] += c;
        return;
    }
    pushdown(rt);
    int mid = (l + r) >> 1;
    if(l <= mid) update(rt << 1,l,mid,l,r,c);
    if(r > mid) update(rt << 1 | 1,mid + 1,r,l,r,c);
    tree[rt] = max(tree[rt << 1],tree[rt << 1 | 1]);
}
int pos[n],ans,lst[n];
int main() {
    int n = read();
    int ans = 0;
    for(int i = 1;i <= n;++i) {
        int x = read();
        if(pos[x]) lst[i] = pos[x];
        pos[x] = i;
        if(lst[i]) update(1,1,n,lst[lst[i]] + 1,lst[i],-1);
        update(1,1,n,lst[i] + 1,i,1);
        ans = max(ans,tree[1]);
    }
    cout<<ans;
    return 0;
}