思路

用\(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;

}

巴特西

nowcoder911L 最优子区间

思路

代码

最新文章

热门文章