ARC #008 D - タコヤキオイシクナール

問題文 : タコヤキオイシクナール

解法 :
Nに対してMが小さいので, Nの座標圧縮を前もって行なっておく.
(こうしても正しい結果が得られることは, 美味しさrのたこ焼きが(1, 0)と書かれたタコヤキオイシクナールを通っても美味しさrが保たれることから分かる.)

美味しさkのたこ焼きが(a, b), (c, d)のタコヤキオイシクナールをこの順で通ると, その美味しさは
c(ak + b) + d = (ac)k + (bc + d)となるので, 隣接するノードを併合しながら(p, q)の値をもつセグメント木を構築する.

こうすることで, 各いたずらクエリの途中に出てくる美味しさの最大値・最小値が答えとなり, これはO(MlogM)時間で求めることが出来る.

コード :

#include <map>
#include <cstdio>
#include <algorithm>

typedef __int64 ll;
typedef struct {
	double a, b;
} Node;

Node seg[1 << 21];
int size;

using namespace std;

void init(int n)
{
	size = 1;
	while (size < n) size *= 2;
	
	for (int i = 0; i < size * 2; i++){
		seg[i].a = 1; seg[i].b = 0;
	}
}

void update(int k, Node x)
{
	k += size - 1;
	seg[k] = x;
	
	while (k){
		k = (k - 1) / 2;
		seg[k].a = seg[k * 2 + 1].a * seg[k * 2 + 2].a;
		seg[k].b = seg[k * 2 + 2].a * seg[k * 2 + 1].b + seg[k * 2 + 2].b;
	}
}

int main()
{
	ll N, M;
	map<ll, int> conv;
	static Node q[100000];
	static ll t[100000], xs[100000];
	
	scanf("%I64d %I64d", &N, &M);
	
	init(M);
	
	for (int i = 0; i < M; i++){
		scanf("%I64d %lf %lf", &t[i], &q[i].a, &q[i].b);
		xs[i] = t[i];
	}
	
	sort(xs, xs + M);
	conv[xs[0]] = 0;
	int idx = 1;
	for (int i = 1; i < M; i++){
		if (xs[i] != xs[i - 1]) conv[xs[i]] = idx++;
	}
	
	double ma = 1.0, mi = 1.0;
	
	for (int i = 0; i < M; i++){
		update(conv[t[i]], q[i]);
		ma = max(ma, seg[0].a + seg[0].b);
		mi = min(mi, seg[0].a + seg[0].b);
	}
	
	printf("%lf\n%lf\n", mi, ma);
	
	return (0);
}