首页 > 代码库 > Acdream 1427 Nice Sequence
Acdream 1427 Nice Sequence
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 10 1 1 0 2 2 1 2 2 32 01 0
Sample Output
80
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 long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 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 }
Acdream 1427 Nice Sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。