【BZOJ3048】【Usaco2013 Jan】Cow Lineup

线段树即可。

首先,定义 nxt[i] 为和 a[i] 相同的下一个数的位置, lst[i] 为和 a[i] 相同的上一个数的位置。

从大到小枚举删数后的最长完美序列在原序列中的右端点 r ,同时用线段树维护每个位置 i 是否对不同数的个数有贡献(也就是 nxt[i] 是否大于 r ),不难发现 r 左移之后只有 lst[r] 变得有了贡献。在线段树上寻找一个 i 使得 rank(r)-rank(i)>k+1 i 最大,最后数一下 [i+1,r] 中满足 a[p]=a[r] p 有多少个来更新答案。

时间复杂度 O(n \log n) ,空间复杂度 O(n)

Code

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <utility>
  4. using namespace std;
  5. const int maxn=100001;
  6. struct segtree{
  7. int sumv[maxn*4];
  8. int n;
  9. int kth(int k){
  10. int o=1,l=1,r=n;
  11. while(l<r){
  12. int mid=(l+r)/2;
  13. if(k<=sumv[o*2])
  14. o*=2,r=mid;
  15. else k-=sumv[o*2],o=o*2+1,l=mid+1;
  16. }
  17. return l;
  18. }
  19. int ql,qr;
  20. int query(int o,int l,int r){
  21. if (ql<=l && qr>=r)
  22. return sumv[o];
  23. int mid=(l+r)/2;
  24. int ans=0;
  25. if (ql<=mid)
  26. ans+=query(o*2,l,mid);
  27. if (qr>mid)
  28. ans+=query(o*2+1,mid+1,r);
  29. return ans;
  30. }
  31. int rank(int x){
  32. ql=1,qr=x;
  33. return query(1,1,n);
  34. }
  35. int p,v;
  36. void add(int o,int l,int r){
  37. if (l==r){
  38. sumv[o]+=v;
  39. return;
  40. }
  41. int mid=(l+r)/2;
  42. if (p<=mid)
  43. add(o*2,l,mid);
  44. else add(o*2+1,mid+1,r);
  45. sumv[o]+=v;
  46. }
  47. void add(int p,int v){
  48. this->p=p;
  49. this->v=v;
  50. add(1,1,n);
  51. }
  52. }t;
  53. int a[maxn],lst[maxn],nxt[maxn];
  54. int now[maxn];
  55. int nums[maxn],cur;
  56. pair<int,int> x[maxn];
  57. int main(){
  58. int n,k;
  59. scanf("%d%d",&n,&k);
  60. k++;
  61. t.n=n;
  62. for(int i=1;i<=n;i++)
  63. scanf("%d",a+i),nums[i]=a[i];
  64. cur=n;
  65. sort(nums+1,nums+cur+1);
  66. cur=unique(nums+1,nums+cur+1)-nums-1;
  67. for(int i=1;i<=n;i++)
  68. a[i]=lower_bound(nums+1,nums+cur+1,a[i])-nums;
  69. for(int i=1;i<=n;i++)
  70. x[i].first=a[i],x[i].second=i;
  71. sort(x+1,x+n+1);
  72. for(int i=1;i<=n;i++){
  73. lst[i]=now[a[i]];
  74. nxt[now[a[i]]]=i;
  75. now[a[i]]=i;
  76. }
  77. for(int i=1;i<=n;i++)
  78. if (!nxt[i]){
  79. //printf("%d\n",i);
  80. t.add(i,1);
  81. }
  82. int ans=0;
  83. for(int i=n;i>=1;i--){
  84. int q=t.rank(i),y=q>k?t.kth(q-k):0;
  85. int r=upper_bound(x+1,x+n+1,make_pair(a[i],i))-x-1,l=upper_bound(x+1,x+n+1,make_pair(a[i],y))-x-1;
  86. //printf("i=%d q=%d y=%d l=%d r=%d\n",i,q,y,l,r);
  87. ans=max(ans,r-l);
  88. if (lst[i])
  89. t.add(lst[i],1);
  90. }
  91. printf("%d",ans);
  92. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

本文链接:https://www.q234rty.top/2016/12/31/bzoj3048/

隐藏