Vjudge11.17

ABCDE Fが離散化した後に図を建てて、dfsは環あるいは葉の結点を探して————————————————————————————Gは何も考えることができません.右ノードを遍歴して、セグメントツリーの各葉の結点は1-i、2-i、3-i...i-iメンテナンスはmaxです.それから、rt<<1|1が範囲内ではないことを知らないので、上から左の葉を見つけたいのですが、だめです.だからやはりノードメンテナンスはmaxとleftnodeで、底から上へ伝わります.

void pushup(int rt) {
	if (maxx[rt << 1] >= maxx[rt << 1 | 1]) {
		maxx[rt] = maxx[rt << 1];
		pos[rt] = pos[rt << 1];
	}
	else {
		maxx[rt] = maxx[rt << 1 | 1];
		pos[rt] = pos[rt << 1 | 1];
	}
}
void pushdown(int rt) {
	if (lazy[rt]) {
		lazy[rt << 1] += lazy[rt];
		lazy[rt << 1 | 1] += lazy[rt];
		maxx[rt << 1] += lazy[rt];
		maxx[rt << 1 | 1] += lazy[rt];
		lazy[rt] = 0;
	}
}
void build(int l, int r, int rt) {
	lazy[rt] = 0;
	if (l == r) {
		maxx[rt] = 0;
		pos[rt] = l;
		return;
	}
	int m = (l + r) >> 1;
	build(l, m, rt << 1);
	build(m + 1, r, rt << 1 | 1);
	pushup(rt);
}
void update(int L, int R, ll c, int l, int r, int rt) {
	if (L <= l && r <= R) {
		lazy[rt] += c;
		maxx[rt] += c;
		return;
	}
	pushdown(rt);
	int m = (l + r) >> 1;
	if (m >= L)update(L, R, c, l, m, rt << 1);
	if (m < R)update(L, R, c, m + 1, r, rt << 1 | 1);
	pushup(rt);
}
int leftans = 0;
ll maxxans = 0;
void query(int L, int R, int l, int r, int rt)
{
	if (L <= l && r <= R) {
		if (maxx[rt] > maxxans) {
			maxxans = maxx[rt];
			leftans = pos[rt];
		}
		return;
	}
	pushdown(rt);
	int m = (l + r) >> 1;
	if (m >= L)query(L, R, l, m, rt << 1);
	if (m < R)query(L, R, m + 1, r, rt << 1 | 1);
}

for (int i = 1; i <= m; i++) {
		update(1, i, k, 1, m, 1);
		for (int j = 0; j < leftt[i].size(); j++) {
			update(1, leftt[i][j].left, leftt[i][j].p, 1, m, 1);
		}
		query(1, i, 1, m, 1);
		if (maxxans > maxans) {
			maxans = maxxans;
			rmax = i;
			lmax = leftans;
		}
	}