HDU6070Dirt Ratio

题目链接

题意

​ 给定一个长度为n的数列，求 min{size[l...r]r−l+1∣1≤l≤r≤n} ,其中 size[l...r] 表示 al,al+1,...,ar 中不同数的个数

分析

​ 赛时真是太菜了。。一直想不到二分加线段树处理，纠结在了主席树上面。。

​ 二分答案，设为mid，则 size[l...r]r−l+1≤mid 对于所有 1≤l≤r≤n 成立，即

size[l...r]≤mid(r−l+1)

size[l...r]+mid×l≤mid(r−1)

​ 对于 mid×l≤mid(r−1) 可以利用线段树区间最小值快速查询，而要保证整体快速查询，考虑 size[l...r] 也能在线段树上快速计算。将 size[l...r] 的值保存在位置 l 上时，用 pre[ai] 表示 ai 上一次出现的位置，那么新增一个数 ar+1 ，其对 pre[ar+1],pre[ar+1]+1,...,r 均产一点贡献，即对一个区间中的每个值产生同样的贡献。这样就可以将 size[l...r] 也同步到线段树中，逐个枚举结尾位置，更新后再查询区间最小值即可。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define MAXN 60600 #define eps 1e-7 #define lson rt<<1 #define rson rt<<1|1 int n; int a[MAXN]; double mn[MAXN<<2]; int lazy[MAXN<<2]; int pre[MAXN]; void push_down(int rt){ if(lazy[rt]){ lazy[lson]+=lazy[rt]; lazy[rson]+=lazy[rt]; mn[lson]+=lazy[rt]; mn[rson]+=lazy[rt]; lazy[rt]=0; } } void build(int l,int r,int rt,double m){ lazy[rt]=0; if(l==r){ mn[rt]=l*m; return; } int mid=(l+r)>>1; build(l,mid,lson,m); build(mid+1,r,rson,m); mn[rt]=min(mn[lson],mn[rson]); } void update(int l,int r,int rt,int L,int R){ if(L<=l && r<=R){ mn[rt]+=1; lazy[rt]++; return; } push_down(rt); int mid=(l+r)>>1; if(mid>=L) update(l,mid,lson,L,R); if(mid<R) update(mid+1,r,rson,L,R); mn[rt]=min(mn[lson],mn[rson]); } double query(int l,int r,int rt,int L,int R){ if(L<=l && r<=R) return mn[rt]; push_down(rt); int mid=(l+r)>>1; double ret=1e9; if(mid>=L) ret=min(ret,query(l,mid,lson,L,R)); if(mid<R) ret=min(ret,query(mid+1,r,rson,L,R)); return ret; } void debug(){ for(int i=1;i<=n;++i){ printf("%lf ",query(1,n,1,i,i)); } cout<<endl; } bool judge(double m){ build(1,n,1,m); memset(pre,0,sizeof(pre)); //debug(); for(int i=1;i<=n;++i){ update(1,n,1,pre[a[i]]+1,i); //debug(); if(query(1,n,1,1,i)-m*(i+1)<eps) return true; pre[a[i]]=i; } return false; } int main(){ int T; cin>>T; while(T--){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); double l=0,r=1,mid; while(r-l>eps){ mid=(l+r)/2; if(judge(mid)) r=mid; else l=mid; } printf("%.5lf\n",l); } }