这里是被楼上Froggy大佬~~点名爆踩~~的做法qaq。

~~废话有点多，不想看直接跳~~

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人，人人本着正义之名。长存不灭的过去；逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。
————世界上最幸福的女孩珂朵莉

不愧是Ynoi，如此毒瘤。

这是我Ynoi一血~~初始化那题暴力艹过去的~~qaq。

~~想了一个小时，深感此题毒瘤~~

$\texttt{Description}$

给你一个序列，每次操作可以增加一个数，也可以查询对于一个数 $x$，将这个序列从小到大排序后找到最小的 $i$ 满足 $\lceil \frac{a_{i+1}}{x}\rceil -1> \lceil \frac{a_i}{x}\rceil$（若当前序列长度为 $n$，令 $a_{n+1}=\infty$）

$\texttt{Solution}$

题目说了 $h\le n\le 10^5$，因此我们盲猜这题要用权值线段树or权值树状数组。再看到每次查询一段区间的期望值，还要乘上这段区间的长度，其实就是求每种方案的总和，查询区间 $[l,r]$ 对应的答案的总和……再一看数据范围，显然要用一个支持修改和区间查询的数据结构维护答案。

$n\le 10^5,m\le 10^6$，~~Ynoi不用分块惹爷青结~~

至于如何维护答案，我们将每个随从的血量放到一个权值树状数组里面，每次增加一个随从，找到被他影响的答案，然后暴力调整即可。

为什么说是暴力调整呢？

形象的理解一下，上面向上取整可以理解为对这个权值树状数组进行分块。数组的每个值 $d_i$ 表示血量为 $d_i$ 的随从的数目。块长为 $x$，我们要求的就是最早哪个块里面的数字均为 $0$。

由于 $x$ 的取值在 $[1,n]$ 之间，所以每次暴力往后跳最多也就不跳超过 $\sum\limits^{i\le n}_{i=1}\frac{n}{i}\approx nlogn$。

每次跳的时候查询一下树状数组，当前这个块是否全部为 $0$，如果不是就往后跳。

现在的问题是不可能每加进来一个随从就把所有块往后跳，因为就算总共跳的次数少，把这些块遍历一遍也需要 $O(n)$ 的时间。因此我们需要找到对于当前血量为 $h$ 的随从，有多少块经过了 $h$ 这个点。将这些块全部删除并往后跳，再把新的块插入进去。

现在需要一种数据结构，支持三种操作：

插入一条线段
删除一条线段
查询经过了给定点的所有线段

对于给定点 $h$，经过它的线段左端点必然在 $[1,h]$ 之间，不妨把每条线段的左端点看做下标，则我们每次查询左端点在 $[1,h]$ 之间的线段右端点最大的，将它往后调整后删除，直到当前查询到的最大右端点 $<h$ 为止。就是一个动态的RMQ，我使用线段树维护。（当然可能有多个线段左端点一样，因此线段树每个叶子节点对应一个大根堆而不是一个数）。

然后维护一个表示答案的树状数组，每次暴力往后跳块后就要更新它。

貌似很多神仙用set被卡常了，显然用set常数比堆大得多啊……

$\texttt{Code}$

由于没有刻意卡常，所以是我的正常马蜂。

#include <cstdio>
#include <queue>
#define int long long
#define Re(x) (RMQ::a[x].size() ? RMQ::a[x].top() : 0)

const int N = 5e5;
int n;
namespace RMQ {
	struct Node {
		int l, r, v;
	} c[N << 4];
	std::priority_queue<int> a[N];
	void make_tree(const int O, const int L, const int R) {
		c[O].l = L, c[O].r = R;
		if (L == R) {c[O].v = L; return;}
		make_tree(O << 1, L, L + R >> 1), make_tree(O << 1 | 1, (L + R >> 1) + 1, R);
		if (Re(c[O << 1].v) >= Re(c[O << 1 | 1].v)) c[O].v = c[O << 1].v;
		else c[O].v = c[O << 1 | 1].v;
	}
	void insert(const int O, const int x, const int d) {
		if (c[O].l == c[O].r) {a[x].push(d); return;}
		if (c[O << 1].r >= x) insert(O << 1, x, d);
		else insert(O << 1 | 1, x, d);
		if (Re(c[O << 1].v) >= Re(c[O << 1 | 1].v)) c[O].v = c[O << 1].v;
		else c[O].v = c[O << 1 | 1].v;
	}
	void del(const int O, const int x) {
		if (c[O].l == c[O].r) {
			a[x].pop(), c[O].v = x;
			return;
		}
		if (c[O << 1].r >= x) del(O << 1, x);
		else del(O << 1 | 1, x);
		if (Re(c[O << 1].v) >= Re(c[O << 1 | 1].v)) c[O].v = c[O << 1].v;
		else c[O].v = c[O << 1 | 1].v;
	}
	int query(const int O, const int L, const int R) {
		if (L <= c[O].l && c[O].r <= R) return c[O].v;
		if (c[O << 1].r < L) return query(O << 1 | 1, L, R);
		else if (c[O << 1 | 1].l > R) return query(O << 1, L, R);
		int t1(query(O << 1, L, R)), t2(query(O << 1 | 1, L, R));
		return Re(t1) >= Re(t2) ? t1 : t2;
	}
}

struct BIT {
	int c[N];
	inline void update(const int x, const int d) {
		for (int i(x); i <= N; i += (i & ~i + 1)) c[i] += d;
	}
	inline int query(const int x) {
		int sum(0);
		for (int i(x); i; i -= (i & ~i + 1)) sum += c[i];
		return sum;
	}
} summary, ans;

signed main() {
	int m;
	scanf("%lld%lld", &n, &m);
	for (int i(1); i <= n; ++ i)
		ans.update(i, 1), RMQ::a[1].push(i);
	RMQ::make_tree(1, 1, n);
	while (m --) {
		int op;
		scanf("%lld", &op);
		if (op == 1) {
			int h;
			scanf("%lld", &h);
			summary.update(h, 1);
			int p;
			while ((Re(p = RMQ::query(1, 1, h))) >= h) {
				int len(RMQ::a[p].top() - p);
				ans.update(len + 1, -(p - 1) / (len + 1) - 1), RMQ::del(1, p);
				while (summary.query(p + len) - summary.query(p - 1)) p += len + 1;
				ans.update(len + 1, (p - 1) / (len + 1) + 1);
				if (p <= n) RMQ::insert(1, p, p + len);
			}
		}
		else {
			int l, r;
			scanf("%lld%lld", &l, &r);
			printf("%lld\n", ans.query(r) - ans.query(l - 1));
		}
	}
}

zqs`s blog

洛谷P5068题解

$\texttt{Description}$

$\texttt{Solution}$

$\texttt{Code}$