题目大意：

就是给你一个区间，让你找出一个子区间，使得区间内不同元素个数/区间长度最大。15组测试数据，每组区间长度6e4。要求答案精确到1e-4。

分析：

首先是要二分查找答案，每次枚举一个答案作为上界，判断是否存在满足条件的区间。这里枚举出答案大概需要20次。

下面说明对于某次枚举的答案mid，如何确定它的可行性：

定义：

dif[ i ][ j ] 表示区间 [ i , j ] 里的不同的元素的个数。

那么我只需要验证：

dif[l,r]/{r-l+1}>=mid;

即：

l*mid + dif[ l ][ r ] >= mid*(r+1);

那么对于每一个即将被判断可行性的 mid ，我就枚举所有的 r ，每次都取 max { i*mid + dif[ i ][ r ] | 1<=i<=r }，将它和 mid*(r+1) 进行比较即可判断其可行性。总时间复杂度：O(logw*n*logn);

代码：

#include<bits/stdc++.h>
#define MAXN 60050
#define inf 0x3f3f3f3f
using namespace std;

int test,n,a[MAXN],pre[MAXN],last[MAXN];
double  tree[MAXN<<2],lazy[MAXN<<2];

void Push_up(int x)
{
    tree[x]=min(tree[x<<1],tree[x<<1|1]);
}
/*void Build(int l,int r,int rt) { if(l==r) { tree[rt]=a[l]; return; } int mid=(l+r)>>1; Build( l , mid , rt<<1 ); Build( mid+1 , r , rt<<1|1 ); Push_up( rt ); }*/
void Push_down(int rt)
{
    if(lazy[rt])
    {
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        tree[rt<<1]+=lazy[rt];
        tree[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
    }

}
void Add_interval(int L,int R,int C,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        tree[rt]+=C;
        lazy[rt]+=C;
        return;
    }
    int mid=(l+r)>>1;
    Push_down(rt);
    if(L<=mid)Add_interval(L,R,C,l,mid,rt<<1);
    if(R>mid)Add_interval(L,R,C,mid+1,r,rt<<1|1);
    Push_up(rt);
}
double Qurey_interval(int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)return tree[rt];
    int mid=(r+l)>>1;
    Push_down(rt);
    double ans=inf;
    if(L<=mid)ans=min(ans,Qurey_interval(L,R,l,mid,rt<<1));
    if(R>mid)ans=min(ans,Qurey_interval(L,R,mid+1,r,rt<<1|1));
    Push_up(rt);
    return ans;
}
void Add_point(int L,double C,int l,int r,int rt)
{
    if (l==r)
    {
        tree[rt]+=C;
        return;
    }
    int mid=(l+r)>>1;
    Push_down(rt);
    if (L<=mid)
        Add_point(L,C,l,mid,rt<<1);
    else
        Add_point(L,C,mid+1,r,rt<<1|1);
    Push_up(rt);
}


bool run(double mid)
{
    memset(tree,0,sizeof(tree));
    memset(lazy,0,sizeof(lazy));
    for(int i=1;i<=n;i++)
    {
        double flag=mid*(i+1);
        //cout<<flag<<endl;
        double t=0;
        Add_interval(pre[i]+1,i,1,1,n,1);
        //cout<<pre[i]+1<<" "<<i<<endl;
        //cout<<tree[1];
        Add_point(i,i*mid ,1,n,1);
        //cout<<tree[1];
        t=Qurey_interval(1,i,1,n,1);


       // cout<<t<<" "<<flag<<endl;
        if(t<flag)
        {
            //cout<<1;
            return 1;
        }
    }
    //cout<<0;
    return 0;
}

int main()
{
    scanf("%d",&test);
    while(test--)
    {
        memset(last,0,sizeof(last));
        memset(pre,0,sizeof(pre));

        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            pre[i]=last[a[i]];
            last[a[i]]=i;
        }
        double mid;
        double l=0,r=1;
        for(int i=0;i<30;i++)//为了保险起见，决定循环30次
        {

            mid=(l+r)/2.0;
            if(run(mid)==1)//如果能跑出来
            {
                r=mid;
            }
            else
            {
                l=mid;
            }
            //cout<<mid<<endl;
        }
        printf("%lf\n",mid);
    }
}
/* 1 5 1 2 1 2 3 */