HDU_6070_Dirt Ratio_二分_セグメントツリーの最適化

テーマ:
長さnの整数数列(1<=ai<=n)を1列与え、繰り返し可能で、連続サブ列のX/Yの最小値を計算し、Xはサブ列に異なる数字が現れる個数であり、Yは数列長である.
考え方:
0~1内において、最小値を二分する毎に、サブストリングが1つ存在するか否かを判定する値がmid以下である.
X/Y <= mid
X <= mid * Y
X <= mid * (r - l + 1)
X + mid * (l - 1) <= mid * r
右境界rを左から右へ列挙する、現在のrまで列挙すると、線分ツリーにおける0~r区間内の保存lから現在rまでの間に異なる数の個数とmid*(l-1)の和が現れる、線分ツリーで区間最小値をmid*rと比較する.
pre[]配列で現在の数字が前回現れた位置を記録し、pre[temp]+1~i区間+1

#include 
#include 
#include 
#define MAXN 60000 + 10
using namespace std;
struct Node
{
    double val;
    double lazy;

} nodes[MAXN << 2];
void build (int l, int r, int root)
{
    Node& n = nodes[root];
    n.val = n.lazy = 0;

    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(l, mid, root * 2 + 1);
    build(mid + 1, r, root * 2 + 2);

}
void push_down(int l, int r, int root)
{
    Node& n = nodes[root];
    if (l == r)
    {
        n.lazy = 0;
        return;
    }
    else
    {
        nodes[root * 2 + 1].val += n.lazy;
        nodes[root * 2 + 1].lazy += n.lazy;
        nodes[root * 2 + 2].val += n.lazy;
        nodes[root * 2 + 2].lazy += n.lazy;
        n.lazy = 0;

    }

}
void update(int ul, int ur, double val, int l, int r, int root)
{
    Node& n = nodes[root];
    if (ul <= l && r <= ur)
    {
        nodes[root].val += val;
        nodes[root].lazy += val;
        return;
    }
    int mid = (l + r) >> 1;
    if (n.lazy > 0)
        push_down(l, r, root);
    if (ur <= mid)
        update(ul, ur, val, l, mid, root * 2 + 1);
    else if (ul > mid)
        update(ul, ur, val, mid + 1, r, root * 2 + 2);
    else
    {
        update(ul, ur, val, l, mid, root * 2 + 1);
        update(ul, ur, val, mid + 1, r, root * 2 + 2);
    }

    nodes[root].val = min(nodes[root * 2 + 1].val, nodes[root * 2 + 2].val);

}
double query(int ql, int qr, int l, int r, int root)
{
    if (ql <= l && r <= qr)
        return nodes[root].val;
    int mid = (l + r) >> 1;
    if (nodes[root].lazy > 0)
        push_down(l, r, root);
    if (qr <= mid)
        return query(ql, qr, l, mid, root * 2 + 1);
    else if (ql > mid)
        return query(ql, qr, mid + 1, r, root * 2 + 2);
    else
        return min(query(ql, qr, l, mid, root * 2 + 1), query(ql, qr, mid + 1, r, root * 2 + 2));

}
int a[MAXN], pre[MAXN];
int main()
{
    int t, n;
    freopen("in.txt", "r", stdin);

    scanf("%d", &t);

    while (t--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", a + i);
        double l = 0, r = 1;
        while (r - l > 1e-5)
        {

            build(0, n - 1, 0);
            memset(pre, -1, sizeof(pre));

            double mid = (r + l) / (double)2;
            for (int i = 0; i < n; i++)
                update(i, i, mid * (double)(i - 1), 0, n - 1, 0);

            int flag = 0;

            for (int i = 0; i < n; i++)
            {

                int temp = a[i];
                update(pre[temp] + 1, i, (double)1, 0, n - 1, 0);
                pre[temp] = i;


                if (query(0, i, 0, n - 1, 0) <= mid * (double)i)
                {
                    flag = 1;
                    break;
                }


            }
            if (flag)
                r = mid;
            else
                l = mid;

        }

        printf("%f
", l);
    }

}