【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

#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
const int maxn=100001;
struct segtree{
	int sumv[maxn*4];
	int n;
	int kth(int k){
		int o=1,l=1,r=n;
		while(l<r){
			int mid=(l+r)/2;
			if(k<=sumv[o*2])
				o*=2,r=mid;
			else k-=sumv[o*2],o=o*2+1,l=mid+1;
		}
		return l;
	}
	int ql,qr;
	int query(int o,int l,int r){
        	if (ql<=l && qr>=r)
            		return sumv[o];
        	int mid=(l+r)/2;
        	int ans=0;
        	if (ql<=mid)
            		ans+=query(o*2,l,mid);
        	if (qr>mid)
            		ans+=query(o*2+1,mid+1,r);
        	return ans;
	}
	int rank(int x){
        	ql=1,qr=x;
        	return query(1,1,n);
	}
	int p,v;
	void add(int o,int l,int r){
		if (l==r){
			sumv[o]+=v;
			return;
		}
		int mid=(l+r)/2;
		if (p<=mid)
			add(o*2,l,mid);
		else add(o*2+1,mid+1,r);
		sumv[o]+=v;
	}
	void add(int p,int v){
		this->p=p;
		this->v=v;
		add(1,1,n);
	}
}t;
int a[maxn],lst[maxn],nxt[maxn];
int now[maxn];
int nums[maxn],cur;
pair<int,int> x[maxn];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    k++;
    t.n=n;
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),nums[i]=a[i];
    cur=n;
    sort(nums+1,nums+cur+1);
    cur=unique(nums+1,nums+cur+1)-nums-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(nums+1,nums+cur+1,a[i])-nums;
    for(int i=1;i<=n;i++)
        x[i].first=a[i],x[i].second=i;
    sort(x+1,x+n+1);
    for(int i=1;i<=n;i++){
        lst[i]=now[a[i]];
        nxt[now[a[i]]]=i;
        now[a[i]]=i;
    }
    for(int i=1;i<=n;i++)
        if (!nxt[i]){
            //printf("%d\n",i);
            t.add(i,1);
        }
    int ans=0;
    for(int i=n;i>=1;i--){
        int q=t.rank(i),y=q>k?t.kth(q-k):0;
        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;
        //printf("i=%d q=%d y=%d l=%d r=%d\n",i,q,y,l,r);
        ans=max(ans,r-l);
        if (lst[i])
            t.add(lst[i],1);
    }
    printf("%d",ans);
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2016/12/31/bzoj3048/

隐藏