一些想法题

例一：Longest Subarray

链接

HDOJ 6602

题意

N个数字，范围为[1,C]，求最长的连续子序列，
使得子序列中每种数值出现的次数大于等于K或者等于0。
N,C,K≤$10^5$105

分析

如果右端点固定，对于每种元素，可行的左端点下标是两段连续的区间。
对于每种元素，将它的可行左端点区间在线段树中加一。
当右端点右移的时候，维护C 种元素的可行左端点。
查询时只需要询问线段树中最小的、值为C 的下标即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
template<class T>inline void MAX(T &x,T y){if(y>x)x=y;}
template<class T>inline void MIN(T &x,T y){if(y<x)x=y;}
template<class T>inline void rd(T &x){
	x=0;char o,f=1;
	while(o=getchar(),o<48)if(o==45)f=-f;
	do x=(x<<3)+(x<<1)+(o^48);
	while(o=getchar(),o>47);
	x*=f;
}
const int M=1e5+5;
int n,c,k,A[M];
vector<int>vi[M];
int mx[M<<2],lazy[M<<2];
void build(int l=1,int r=n,int p=1){
	mx[p]=c,lazy[p]=0;
	if(l==r)return;
	int mid=l+r>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
}
void down(int p){
	if(lazy[p]){
		mx[p<<1]+=lazy[p];
		mx[p<<1|1]+=lazy[p];
		lazy[p<<1]+=lazy[p];
		lazy[p<<1|1]+=lazy[p];
		lazy[p]=0;
	}
}
int query(int l=1,int r=n,int p=1){
	if(l==r)return l;//n==1时特判
	down(p);
	int mid=l+r>>1;
	if(mx[p<<1]==c)return query(l,mid,p<<1);
	else if(mx[p<<1|1]==c)return query(mid+1,r,p<<1|1);
	else return n+1;
}
void update(int a,int b,int v,int l=1,int r=n,int p=1){
	if(l>b||r<a)return;
	if(l>=a&&r<=b){
		mx[p]+=v;
		lazy[p]+=v;
		return;
	}
	down(p);
	int mid=l+r>>1;
	update(a,b,v,l,mid,p<<1);
	update(a,b,v,mid+1,r,p<<1|1);
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("jiedai.in","r",stdin);
//	freopen("jiedai.out","w",stdout);
#endif
	while(scanf("%d%d%d",&n,&c,&k)!=EOF){
		for(int i=1;i<=n;i++)rd(A[i]);
		for(int i=1;i<=c;i++)vi[i].clear(),vi[i].push_back(0);
		build();
		int ans=0;
		for(int i=1;i<=n;i++){
			vi[A[i]].push_back(i);
			int sz=vi[A[i]].size();
			if(sz-k-1>=0)update(vi[A[i]][sz-k-1]+1,vi[A[i]][sz-k],+1);
			update(vi[A[i]][sz-2]+1,vi[A[i]][sz-1],-1);
			MAX(ans,i-query()+1);
		}
		printf("%d\n",ans);
	}
	return 0;
}