hdu6602 Longest Subarray(线段树+思维)_longestsubarray

题目链接
大意：给你一个长度为n的数组，然后每个元素都是$[1,c]$之间的整数，然后让你求一个最大的子数组使得这个子数组中每种数出现的次数大于k次，问你满足条件的最长子数组。
思路：先假设右端点为n，对所有的数预处一遍，枚举每种数，如果没出现的话显然$[1,n]$的每个数当左端点都可以，若出现超过k次，那么显然有两端封闭的区间可以满足条件，一个是没出现过这个数的所有位置，一个是出现多于k次的，我们假设集合$S_i$是i这个数字出现位置的集合(从大到小排序),大小为k,那么$[1,po{s}_i{}_s]$，和$[po{s}_i{}_1+1,n]$都是可以满足条件的左端点.
我们在线段树上维护一个区间加和一个区间最大值，每次对可行区间进行更新，查询我们需要找一个最小的位置且这个位置的值为C,（即这个点满足所有数的条件）,然后更新答案即可；
细节见代码

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
vector<int>v[N];
int n,a[N],ans,c,k,cnt[N];
struct uzi{
	int a,b,c;
}T[N<<2];
int laz[N<<2];
void push_up(int now){
	T[now].b=max(T[now<<1].b+laz[now<<1],T[now<<1|1].b+laz[now<<1|1]);
	return ;
}
void push_down(int now){
	if(!laz[now])return ;
	T[now].b+=laz[now];
	laz[now<<1]+=laz[now];
	laz[now<<1|1]+=laz[now];
	laz[now]=0;
	return ;
}
void build(int now,int l,int r){
	laz[now]=0;
	if(l==r){
		T[now].a=T[now].b=T[now].c=0;
		return ;
	}
	int mid=l+r>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	push_up(now);
}
void add(int now,int l,int r,int x,int y,int d){
	if(l>=x&&r<=y){
		laz[now]+=d;
		return ;
	}
	int mid=l+r>>1;
	push_down(now);
	if(mid>=x)add(now<<1,l,mid,x,y,d);
	if(mid<y)add(now<<1|1,mid+1,r,x,y,d);
	push_up(now);
}
int ge(int now,int l,int r,int x,int y){
	if(l==r&&T[now].b+laz[now]==c)return l;
	int mid=0;
	mid=l+r>>1;
	push_down(now);
	int an=1e9;
	if(mid>=x)if(T[now<<1].b+laz[now<<1]==c)return ge(now<<1,l,mid,x,y);
	if(mid<y)if(T[now<<1|1].b+laz[now<<1|1]==c)return ge(now<<1|1,mid+1,r,x,y);
	return an;
}
int g(int now,int l,int r,int x,int y){
	if(l>=x&&r<=y){return T[now].b+laz[now];}
	int mid=0;
	mid=l+r>>1;
	push_down(now);
	int an=0;
	if(mid>=x)an=max(an,g(now<<1,l,mid,x,y));
	if(mid<y)an=max(an,g(now<<1|1,mid+1,r,x,y));
	return an;
}
int main(){
	ios::sync_with_stdio(false);
	while(cin>>n>>c>>k){
		ans=0;
		for(int i=1;i<=c;i++)cnt[i]=0,v[i].clear();
		for(int i=1;i<=n;i++)cin>>a[i],v[a[i]].pb(i);
		for(int i=1;i<=c;i++)reverse(v[i].begin(),v[i].end());
		build(1,1,n);
		for(int i=1;i<=c;i++){
			if(!v[i].size()){
				add(1,1,n,1,n,1);
			}
			else if(v[i].size()>=k){
				if(v[i][0]<n)add(1,1,n,v[i][0]+1,n,1);
				if(v[i].size()>=k){
					add(1,1,n,1,v[i][k-1],1);
				}
			}else{
				if(v[i][0]<n){
					add(1,1,n,v[i][0]+1,n,1);
				}
			}
		}
		for(int i=n;i>=1;i--){
			ans=max(ans,i-ge(1,1,n,1,i)+1);
			if(v[a[i]].size()-cnt[a[i]]>=k){
				if(v[a[i]][cnt[a[i]]]<n)add(1,1,n,v[a[i]][cnt[a[i]]]+1,n,-1);
				if(v[a[i]].size()>=k){
					add(1,1,n,1,v[a[i]][k-1+cnt[a[i]]],-1);
				}				
			}else{
				if(v[a[i]][cnt[a[i]]]<n){
					add(1,1,n,v[a[i]][cnt[a[i]]]+1,n,-1);
				}
			}
			cnt[a[i]]++;
			if(v[a[i]].size()-cnt[a[i]]>=k&&k){
				if(v[a[i]][cnt[a[i]]]<n)add(1,1,n,v[a[i]][cnt[a[i]]]+1,n,1);
				if(v[a[i]].size()-cnt[a[i]]>=k){
					add(1,1,n,1,v[a[i]][k-1+cnt[a[i]]],1);
				}				
			}
			if(v[a[i]].size()-cnt[a[i]]==0){
				add(1,1,n,1,n,1);				
			}else if(v[a[i]].size()-cnt[a[i]]<k){
				add(1,1,n,v[a[i]][cnt[a[i]]]+1,n,1);
			}	
		}	
		cout<<ans<<endl;
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127