HDU 6070 Dirt Ratio

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);
    }
}