比赛时会错题意+不知道怎么线段树维护分数- -
思路来自题解
/*
HDU 6070 - Dirt Ratio [ 二分,线段树 ] | 2017 Multi-University Training Contest 4
题意：
给出 a[N];
设 size(l,r)为区间(l,r)不同数字的个数，求 size(l,r)/(r-l+1) 的最小值
限制： N <= 6e5, a[i] <= 6e5
分析：
二分答案 mid
则判定条件为是否存在 size(l,r)/(r-l+1) <= mid
变换一下： size(l,r) + mid*l <= mid * (r+1)
将左式存入线段树中，枚举 r，对某段 l 进行更新（last[a[r]+1] 到 r），更新操作为值+1
再对每个 r 判断一下上式是否成立
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 6e4+5;
const double eps = 1e-5;
const double INF = 1e18;
namespace SegT {
double val[N];
double Min[N<<2]; int add[N<<2];
void up(int x) {
Min[x] = min(Min[x<<1], Min[x<<1|1]);
}
void down(int x) {
if (add[x]) {
add[x<<1] += add[x];
Min[x<<1] += add[x];
add[x<<1|1] += add[x];
Min[x<<1|1] += add[x];
add[x] = 0;
}
}
void build(int l, int r, int x) {
add[x] = 0;
if (l == r) {
Min[x] = val[l]; return;
}
int mid = (l+r) >> 1;
build(l, mid, x<<1);
build(mid+1, r, x<<1|1);
up(x);
}
void change(int L, int R, int num, int l, int r, int x) {
if (L <= l && r <= R) {
add[x] += num;
Min[x] += num;
return;
}
down(x);
int mid = (l+r) >> 1;
if (L <= mid) change(L, R, num, l, mid, x<<1);
if (mid < R) change(L, R, num, mid+1, r, x<<1|1);
up(x);
}
double query(int L, int R, int l, int r, int x) {
if (L <= l && r <= R) return Min[x];
down(x);
int mid = (l+r) >> 1;
double res = INF;
if (L <= mid) res = min(res, query(L, R, l, mid, x<<1));
if (R > mid) res = min(res, query(L, R, mid+1, r, x<<1|1));
return res;
}
}
int t, n, a[N];
int last[N];
bool solve(double mid)
{
for (int i = 1; i <= n; i++)
SegT::val[i] = i*mid;
SegT::build(1, n, 1);
memset(last, 0, sizeof(last));
for (int i = 1; i <= n; i++)
{
SegT::change(last[a[i]]+1, i, 1, 1, n, 1);
last[a[i]] = i;
double res = SegT::query(1, i, 1, n, 1);
if (res < (i+1)*mid - eps) return 1;
}
return 0;
}
double BinaryFind(double l, double r)
{
double mid;
while ((r-l) > eps) {
mid = (l+r) / 2;
if (solve(mid)) r = mid;
else l = mid;
}
return mid;
}
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
printf("%.9f
", BinaryFind(0, 1));
}
}