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; }
上一篇: Go语言快速入门图文教程