【BZOJ3048】【Usaco2013 Jan】Cow Lineup

Author Avatar
q234rty 12月 31, 2016

线段树即可。

首先，定义 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/

隐藏