Nice Sequence
Time Limit: 12000/6000MS (Java/Others)Memory Limit: 128000/64000KB (Java/Others)
Problem Description
Let us consider the sequence a1, a2,..., an of non-negative integer numbers. Denote as ci,j the number of occurrences of the number i among a1,a2,..., aj. We call the sequence k-nice if for all i1<i2 and for all j the following condition is satisfied: ci1,j ≥ ci2,j −k.
Given the sequence a1,a2,..., an and the number k, find its longest prefix that is k-nice.
Input
The first line of the input file contains n and k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ 200 000). The second line contains n integer numbers ranging from 0 to n.
Output
Output the greatest l such that the sequence a1, a2,..., al is k-nice.
Sample Input
10 1
0 1 1 0 2 2 1 2 2 3
2 0
1 0
Sample Output
8
0
Source
Andrew Stankevich Contest 23
Manager
mathlover
解题：线段树。。。哎。。。当时不知怎么写复杂了。。。。真是蛋疼。。。。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 #include <climits>
7 #include <vector>
8 #include <queue>
9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 210000;
18 struct node{
19 int lt,rt,minv,maxv;
20 };
21 node tree[maxn<<2];
22 void build(int lt,int rt,int v){
23 tree[v].lt = lt;
24 tree[v].rt = rt;
25 tree[v].minv = tree[v].maxv = 0;
26 if(lt == rt) return;
27 int mid = (lt+rt)>>1;
28 build(lt,mid,v<<1);
29 build(mid+1,rt,v<<1|1);
30 }
31 void update(int k,int v,int &val){
32 if(tree[v].lt == tree[v].rt){
33 val = tree[v].maxv = ++tree[v].minv;
34 return;
35 }
36 int mid = (tree[v].lt + tree[v].rt)>>1;
37 if(k <= mid) update(k,v<<1,val);
38 else if(k > mid) update(k,v<<1|1,val);
39 tree[v].minv = min(tree[v<<1].minv,tree[v<<1|1].minv);
40 tree[v].maxv = max(tree[v<<1].maxv,tree[v<<1|1].maxv);
41 }
42 int query_min(int lt,int rt,int v){
43 if(tree[v].lt == lt && tree[v].rt == rt) return tree[v].minv;
44 int mid = (tree[v].lt + tree[v].rt)>>1;
45 if(rt <= mid) return query_min(lt,rt,v<<1);
46 else if(lt > mid) return query_min(lt,rt,v<<1|1);
47 else return min(query_min(lt,mid,v<<1),query_min(mid+1,rt,v<<1|1));
48 }
49 int query_max(int lt,int rt,int v){
50 if(tree[v].lt == lt && tree[v].rt == rt) return tree[v].maxv;
51 int mid = (tree[v].lt + tree[v].rt)>>1;
52 if(rt <= mid) return query_max(lt,rt,v<<1);
53 else if(lt > mid) return query_max(lt,rt,v<<1|1);
54 else return max(query_max(lt,mid,v<<1),query_max(mid+1,rt,v<<1|1));
55 }
56 int n,k,val,tmp,ans;
57 int main() {
58 while(~scanf("%d %d",&n,&k)){
59 build(0,n + 1,1);
60 ans = 0;
61 bool flag = true;
62 for(int i = 1; i <= n; i++){
63 scanf("%d",&tmp);
64 update(tmp,1,val);
65 if(flag && val <= query_min(0,tmp,1)+k && val >= query_max(tmp+1,n+1,1)-k)
66 ans = i;
67 else flag = false;
68 }
69 printf("%d\n",ans);
70 }
71 return 0;
72 } View Code
zkw线段树
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 #include <climits>
7 #include <vector>
8 #include <queue>
9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 200010;
18 int tree[maxn<<2][2],M;
19 void build(int n){
20 M = 1<<((int)log2(n)+2);
21 }
22 void update(int n,int &val){
23 ++tree[n += M][0];
24 val = tree[n][1] = tree[n][0];
25 for(n >>= 1; n; n >>= 1){
26 tree[n][0] = min(tree[n<<1][0],tree[n<<1|1][0]);
27 tree[n][1] = max(tree[n<<1][1],tree[n<<1|1][1]);
28 }
29 }
30 int query_min(int s,int t){
31 s += M - 1;
32 t += M + 1;
33 int minv = INF;
34 while(s^t^1){
35 if(~s&1) minv = min(minv,tree[s^1][0]);
36 if(t&1) minv = min(minv,tree[t^1][0]);
37 s >>= 1;
38 t >>= 1;
39 }
40 return minv;
41 }
42 int query_max(int s,int t){
43 s += M - 1;
44 t += M + 1;
45 int maxv = -1;
46 while(s^t^1){
47 if(~s&1) maxv = max(maxv,tree[s^1][1]);
48 if(t&1) maxv = max(maxv,tree[t^1][1]);
49 s >>= 1;
50 t >>= 1;
51 }
52 return maxv;
53 }
54 int main() {
55 int n,k,tmp,val,ans;
56 while(~scanf("%d %d",&n,&k)){
57 memset(tree,0,sizeof(tree));
58 build(n);
59 bool flag = true;
60 ans = 0;
61 for(int i = 1; i <= n; i++){
62 scanf("%d",&tmp);
63 update(tmp+1,val);
64 if(flag && val <= query_min(1,tmp+1)+k && val >= query_max(tmp+2,n+1)-k)
65 ans = i;
66 else flag = false;
67 }
68 printf("%d\n",ans);
69 }
70 return 0;
71 } 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 #include <climits>
7 #include <vector>
8 #include <queue>
9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 200010;
18 int tree[maxn<<2] = {0},M;
19 int a[maxn] = {0};
20 void build(int n) {
21 M = 1<<((int)log2(n)+2);
22 }
23 void update(int n) {
24 ++tree[n += M];
25 for(n >>= 1; n; n >>= 1)
26 tree[n] = min(tree[n<<1],tree[n<<1|1]);
27 }
28 int query_min(int s,int t) {
29 s += M - 1;
30 t += M + 1;
31 int minv = INF;
32 while(s^t^1) {
33 if(~s&1) minv = min(minv,tree[s^1]);
34 if(t&1) minv = min(minv,tree[t^1]);
35 s >>= 1;
36 t >>= 1;
37 }
38 return minv;
39 }
40 void myscanf(int &x) {
41 char ch;
42 while((ch = getchar()) < '0' || ch > '9');
43 x = 0;
44 x = ch - '0';
45 while((ch = getchar()) >= '0' && ch <= '9')
46 x = x*10 + ch - '0';
47 }
48 int main() {
49 int n,k,tmp,ans;
50 scanf("%d %d",&n,&k);
51 build(n);
52 bool flag = true;
53 ans = 0;
54 for(int i = 1; i <= n; i++) {
55 myscanf(tmp);
56 if(flag) {
57 ++tmp;
58 ++a[tmp];
59 update(tmp);
60 if(query_min(1,tmp) < a[tmp] - k) flag = false;
61 if(flag) ans = i;
62 }
63 }
64 printf("%d\n",ans);
65 return 0;
66 } 夜空中最亮的星，照亮我前行