链接：http://acm.hdu.edu.cn/showproblem.php?pid=6070

大意是给你 n 个数，让你从这ｎ个数中选出一段连续的数，使得这段连续的数中，不相同数的个数比上这段连续数的总个数的值最小．输出这个最小值．

本蒟蒻表示半天没看懂题解．用自己的语言组织下题解：
这是道分数规划类型的题目，分数规划通常采用二分答案来求．就这道题来说，二分答案mid，检验是否存在一个区间满足\\frac{size(l,r)}{r – l + 1}\\leq mid．如果存在，则更新 mid的值，如果不存在，那这个值就是答案了．

对 \\frac{size(l,r)}{r – l + 1}\\leq mid 这个不等式进行变换，可以得到

size(l,r)+mid\\times l \\leq mid \\times (r + 1)

在变换后的这个不等式中，用线段树来维护这个不等式左边的式子的最小值．建树时树中节点的值为 mid \\times l．
如何维护 size(l, r)? 注意到，当 r 从 r 到 r + 1时，只需要将线段树上区间为 [last[a[i]] + 1,i]的值加一即可，last[]数组记录了上一个 a[i]出现的位置．

#include <bits/stdc++.h>
using namespace std;
const int N = 60005;
const double eps = 1e-10;
double mi[N << 2];
double laze[N << 2];
int a[N];
int last[N];
void push_down(int rt)
{
    if (laze[rt]) {
        laze[rt << 1] += laze[rt];
        laze[rt << 1 | 1] += laze[rt];
        mi[rt << 1] += laze[rt];
        mi[rt << 1 | 1] += laze[rt];
        laze[rt] = 0;
    }
}
void build(int l, int r, int rt, double x)
{
    if (l == r) {
        mi[rt] = l * x;
        return;
    }
    int m = l + r >> 1;
    build(l, m, rt << 1, x);
    build(m + 1, r, rt << 1 | 1, x);
    mi[rt] = min(mi[rt << 1], mi[rt << 1 | 1]);
}
void update(int ll, int rr, double v, int l, int r, int rt)
{
    if (ll <= l && r <= rr) {
        laze[rt] += v;
        mi[rt] += v;
        return;
    }
    push_down(rt);
    int m = l + r >> 1;
    if (ll <= m)
        update(ll, rr, v, l, m, rt << 1);
    if (rr > m)
        update(ll, rr, v, m + 1, r, rt << 1 | 1);
    mi[rt] = min(mi[rt << 1], mi[rt << 1 | 1]);
}
double query(int ll, int rr, int l, int r, int rt)
{
    if (ll <= l && r <= rr) {
        return mi[rt];
    }
    push_down(rt);
    int m = l + r >> 1;
    double res = 1e9;
    if (ll <= m)
        res = min(res, query(ll, rr, l, m, rt << 1));
    if (rr > m)
        res = min(res, query(ll, rr, m + 1, r, rt << 1 | 1));
    return res;
}
int main()
{
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
        }
        double low = 0, high = 1.0;
        while (high - low > eps) {
            double mid = (low + high) / 2;
            memset(laze, 0, sizeof(laze));
            memset(last, 0, sizeof(last));
            build(1, n, 1, mid);
            int ok = 0;
            for (int i = 1; i <= n; i++) {
                update(last[a[i]] + 1, i, 1, 1, n, 1);
                last[a[i]] = i;
                if (query(1, i, 1, n, 1) <= mid * (i + 1)) {
                    ok = 1;
                    break;
                }
            }
            if (ok)
                high = mid;
            else
                low = mid;
        }
        printf("%.9lf\n", low);
    }
    return 0;
}