HDU_6070_Dirt Ratio_二分_セグメントツリーの最適化
3541 ワード
テーマ:
長さ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
長さ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);
}
}