2017多校4-4 Dirt Ratio
线段树,二分法
题意
给你一个数列,求一个子区间,使得:区间内不同数字种类/区间内所有数字个数最小。输出最小值。
思路
二分答案 mid ,检验是否存在一个区间满足 size(l,r)r−l+1≤mid ,也就是 size(l,r)+mid×l≤mid×(r+1) 。
从左往右枚举每个位置作为 r ,当r变化为 r+1 时,对 size 的影响是一段区间加 1 ,线段树维护区间最小值即可。
时间复杂度O(nlognlogw)。
每次二分,都重建线段树,叶子初始化为mid*l。线段树每个叶子tree[i]维护是:i到当前枚举位置 这个区间内有多少个不同的数字。
所以二分后针对每个右端点i,与其值a[i],区间更新a[i]上一次出现位置la[a[i]]到i,区间加1,代表这些区间新出现了a[i]这个值。
然后线段树维护区间最小值,每次查询就得出了所有左端点小于当前枚举的位置、构成的所有合法区间,出现不同数字最少的区间。
代码
#include<bits\stdc++.h>
#define M(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN=;
struct STree
{
double val;int lazy;
}stree[MAXN];
int a[MAXN], la[MAXN];
void pushup(int rt)
{
stree[rt].val=min(stree[rt<<].val, stree[rt<<|].val);
}
void pushdown(int rt)
{
if(stree[rt].lazy)
{
stree[rt<<].val+=stree[rt].lazy;
stree[rt<<|].val+=stree[rt].lazy;
stree[rt<<].lazy+=stree[rt].lazy;
stree[rt<<|].lazy+=stree[rt].lazy;
stree[rt].lazy=;
}
}
void build(int l, int r, int rt, double k)
{
stree[rt].lazy=;
if(l==r)
{
stree[rt].val=k*l;
return;
}
int m=(l+r)>>;
build(lson, k);
build(rson, k);
pushup(rt);
}
void update(int L, int R, int l, int r, int rt)
{
if(L<=l&&r<=R)
{
stree[rt].val++;
stree[rt].lazy++;
return;
}
pushdown(rt);
int m=(l+r)>>;
if(L<=m) update(L, R, lson);
if(m<R) update(L, R, rson);
pushup(rt);
}
double query(int L, int R, int l, int r, int rt)
{
if(L<=l&&r<=R) return stree[rt].val;
pushdown(rt);
int m=(l+r)>>;
double res=;
if(L<=m) res=min(res, query(L, R, lson));
if(m<R) res=min(res, query(L, R, rson));
return res;
}
int main()
{
int T;scanf("%d", &T);
while(T--)
{
int n;scanf("%d", &n);
for(int i=;i<=n;i++)
scanf("%d", &a[i]);
double l=, r=;int tim=;
while(tim--)
{
double mid=(l+r)/;
build(, n, , mid);
M(la, );
bool fl=;
for(int i=;i<=n&&!fl;i++)
{
update(la[a[i]]+, i, , n, );
la[a[i]]=i;
if(query(, i, , n, )<=mid*(i+)) fl=;
}
if(fl) r=mid;
else l=mid;
}
printf("%.10lf\n", l);
}
}