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
解题：线段树。。。哎。。。当时不知怎么写复杂了。。。。真是蛋疼。。。。
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 ",ans); 70 } 71 return 0; 72 }
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 ",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 ",ans); 65 return 0; 66 }