Description 给出n次提交的题目编号，对于一个区间，假设该区间中每个题的最后一次提交是AC，之前都是WA，求所有区间中AC数/提交次数最小值 Input 第一行一整数T表示用例组数，每组用例首先输入一整数n表示总提交次数，之后n个整数a[1]~a[n]表示这n次提交的题目编号(1<=T<=15,1<=n<=6e4,1<=a[i]<=n) Output 输出AC数/提交次数的最小值 Sample Input 1 5 1 2 1 2 3 Sample Output 0.5000000000 Solution 二分答案，设二分值为mid，num(l,r)表示区间[l,r]中的不同编号的题目数（即为AC数），那么只要存在一个区间[l,r]满足num(l,r)/(r-l+1)<=mid那么说明该二分值合法，可以寻求更小的二分值当答案，否则要找更大的二分值去找合法解，对上式转化一下变成num(l,r)+mid*l<=mid*(r+1)，当区间右端点由r-1变成r时，所有num(l,r)中只有num(pre(a[r])+1,r)~num(r,r)加一，其他的均不变（pre(a[r])表示a[r]上一次出现的位置，如果a[r]没有出现则pre(a[r])=0），故可以用线段树维护num(l,r)+mid*l的最小值，每次插入的时候对pre(a[r])+1~r做区间加一操作，每次判合法只需将区间1~r中最小值拿出来和mid*(r+1)比较即可，由于精度要求是1e-4，所以二分14次即可，时间复杂度O(14nlogn) Code
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; namespace fastIO { #define BUF_SIZE 100000 //fread -> read bool IOerror=0; inline char nc() { static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; if(p1==pend) { p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); if(pend==p1) { IOerror=1; return -1; } } return *p1++; } inline bool blank(char ch) { return ch==' '||ch=='\n'||ch=='\r'||ch=='\t'; } inline void read(int &x) { char ch; while(blank(ch=nc())); if(IOerror)return; for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0'); } #undef BUF_SIZE }; using namespace fastIO; const int INF=1e9,maxn=60001; #define ls (t<<1) #define rs ((t<<1)|1) double Min[maxn<<2]; int Lazy[maxn<<2]; void push_up(int t) { Min[t]=min(Min[ls],Min[rs]); } void build(int l,int r,int t,double x) { Lazy[t]=0; if(l==r) { Min[t]=x*l; return ; } int mid=(l+r)/2; build(l,mid,ls,x),build(mid+1,r,rs,x); push_up(t); } void push_down(int t) { if(Lazy[t]) { Lazy[ls]+=Lazy[t],Min[ls]+=Lazy[t], Lazy[rs]+=Lazy[t],Min[rs]+=Lazy[t]; Lazy[t]=0; } } void update(int L,int R,int l,int r,int t,int v) { if(L<=l&&r<=R) { Lazy[t]+=v,Min[t]+=v; return ; } push_down(t); int mid=(l+r)/2; if(L<=mid)update(L,R,l,mid,ls,v); if(R>mid)update(L,R,mid+1,r,rs,v); push_up(t); } double query(int L,int R,int l,int r,int t) { if(L<=l&&r<=R)return Min[t]; push_down(t); int mid=(l+r)/2; double ans=INF; if(L<=mid)ans=min(ans,query(L,R,l,mid,ls)); if(R>mid)ans=min(ans,query(L,R,mid+1,r,rs)); return ans; } int T,n,a[maxn],pre[maxn],pos[maxn]; bool check(double x) { build(1,n,1,x); for(int i=1;i<=n;i++) { update(pre[i]+1,i,1,n,1,1); if(query(1,i,1,n,1)<=x*(i+1))return 1; } return 0; } int main() { read(T); while(T--) { read(n); memset(pos,0,sizeof(pos)); for(int i=1;i<=n;i++) { read(a[i]); pre[i]=pos[a[i]],pos[a[i]]=i; } double l=0,r=1,mid; int t=14; while(t--) { mid=0.5*(l+r); if(check(mid))r=mid; else l=mid; } printf("%.5f\n",mid); } return 0; }