[Ynoi2015]ただいま帰りました

題目大意

維護一個序列 $a_i$ ，兩個操作：插入一個數、求：

$$\sum_{d=L}^R\text{mex}\left(\left\{\left\lceil\frac{a_i}{d}\right\rceil\right\}\right) $$

題解

離綫。考慮整除后分塊，用 $t_{d,i}$ 分別維護每個塊最早存在數（即題目中的隨從）時是第幾個操作。

設 $a_i$ 表示存在血量為 $i$ 的最早操作，則有：

$$t_{d,i}=\min_{(i-1)d+1\leq j\leq\min(id,n)}\{a_j\} $$

可以用 ST 表維護。

設 $g_{d,i}$ 表示傷害 $d$ 被觸發至少 $i$ 次的最早操作，有 $g_{d,i}=\max\{g_{d,j-1},t_{d,i}\}$ 。對於一個區間 $(d,i)$ ，會在 $g_{d,i}$ 后產生 1 貢獻。

代碼

const int N = 1e5 + 5, M = 1e6 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	vector <int> vec[M];
	int t[N];
	void Add (int x) { for (; x <= n; x += x & -x) t[x]++; }
	int Query (int x) {int ans = 0; for (; x; x -= x & -x) ans += t[x]; return ans;}
	
	int f[N][25];

	struct Question {
		int op, a, b;
	} q[M];

	int STmin (int l, int r) {
		int t = log2(r - l + 1);
		return min (f[l][t], f[r - (1 << t) + 1][t]);
	}
	
	int main () {
		n = Read(), m = Read();
		for (int i = 1; i <= n; i++) f[i][0] = m + 1;
		for (int i = 1; i <= m; i++) {
			q[i].op = Read(), q[i].a = Read();
			if (q[i].op == 2) q[i].b = Read();
			else f[q[i].a][0] = min (f[q[i].a][0], i);
		}
		for (int j = 1; j <= 20; j++)
			for (int i = 1; i + (1 << j) - 1 <= n; i++)
				f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
		for (int d = 1; d <= n; d++) {
			Add(d);
			int last = 0;
			for (int i = 1; i <= n; i += d)
				vec[last = max(last, STmin(i, min(d + i - 1, n)))].push_back(d);
		}
		for (int i = 1; i <= m; i++) {
			for (int j : vec[i]) Add(j);
			if (q[i].op == 2) printf ("%d\n", Query(q[i].b) - Query(q[i].a - 1));
		}
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}