2024 年 8 月做题记录

C++ / OI / 月度做题记录 无分类
文章系列：月度做题记录

为了防止版权纠纷，部分内容已修改或匿名化。

0818A

大意是给你一个数组，然后每次查询给区间加上/减去一个固定数值（保证修改后数组严格单调递增），查询是否包含一个下标等于值的数（即 ai=ia_i = i）。

然后发现 ai−ia_i - i 也是单调的，然后可以打懒标记（我用的线段树）然后二分。

struct Sg {
	struct { int lz, val; } tr[MAXN * 4];
	void build(int l, int r, int p = 1);
	inline void pushdown(int p);
	void upd(int l, int r, int val, int p = 1, int sl = 1, int sr = -1);
	int query(int x, int p = 1, int sl = 1, int sr = -1);
} sg;

vector<int> rd;

struct myLess {
	bool operator()(const int& idx, const int& val) const {
		return sg.query(idx) - idx < val;
	}
};

inline void query()
{
	int res = *lower_bound(rd.begin(), rd.end(), 0, myLess {});
	if (sg.query(res) != res) cout << "NO\n";
	else cout << "YES\n";
}

int main()
{
	ioin();
	cin >> k >> n;
	k--;
	rd.reserve(n);
	for (int i = 1; i <= n; i++) {
		cin >> dat[i];
		rd.push_back(i);
	}
	sg.build(1, n);
	query();
	while (k--) {
		int l, r, df;
		cin >> l >> r >> df;
		sg.upd(l, r, df);
		query();
	}
}

0818B

要求写一个查询区间内出现次数为奇数的数的个数的一个结构。

赛时随便糊了一个 bitset 上去然后发现时限开 2 秒就能冲过去。

int n, q, cnt, tp, l, r;

bitset<100> pf[100001]; // 60pts
map<int, int> mp;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> tp;
		pf[i] = pf[i - 1];
		const int id = mp.count(tp) ? mp[tp] : mp[tp] = cnt++;
		pf[i][id] = pf[i][id] ^ 1;
	}
	cin >> q;
	while (q--) {
		cin >> l >> r;
		cout << (pf[r] ^ pf[l - 1]).count() << '\n';
	}
}

但不幸的是时限只有 1 秒。

然后改题的时候看见题解写得非常简略。看了 std 之后发现是莫队。于是把询问离线下来然后莫队搞一下。

然后顺便把莫队一直没看懂的时间复杂度证明搞懂了。

map<int, int> ls;
int dat[100005], lscnt;

struct Query {
	int l, r, id, ans;
	bool operator<(const Query& rhs) const {
		int ll = l / 400, rr = rhs.l / 400;
		return ll == rr ? r < rhs.r : ll < rr;
	}
} qr[100005];
int res, cnt[100005];
inline void add(int x) { cnt[dat[x]]++; cnt[dat[x]] & 1 ? res++ : res--; }
inline void del(int x) { cnt[dat[x]] & 1 ? res-- : res++; cnt[dat[x]]--; }

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> dat[i];
		dat[i] = ls.count(dat[i]) ? ls[dat[i]] : ls[dat[i]] = lscnt++;
	}

	int q;
	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> qr[i].l >> qr[i].r;
		qr[i].id = i;
	}
	sort(qr + 1, qr + 1 + q);
	int l = 1, r = 0;
	for (int i = 1; i <= q; i++) {
		while (r < qr[i].r) add(++r);
		while (r > qr[i].r) del(r--);
		while (l > qr[i].l) add(--l);
		while (l < qr[i].l) del(l++);
		qr[i].ans = res;
	}
	sort(qr + 1, qr + q + 1, [](auto l, auto r) {
		return l.id < r.id;
	});
	for (int i = 1; i <= q; i++) cout << qr[i].ans << '\n';
}

[清华集训2012] 序列操作

Luogu

题意：

实现一个数据结构

  1. 区间加
  2. 区间变成相反数
  3. 询问区间中选择 x (x≤20)x\space (x \le 20) 个数相乘的所有方案的和对 1994041719940417 取模的值。

n,q≤50000n, q \le 50000，值域 1e9。

这个题一开始看上去很没有头绪。试着往数据结构方向去想，但是要维护的东西是完全没思路。

然后发现 xx 的范围很小，所以尝试往这方面思考：可以尝试用线段树把所有 0~20 的答案维护下来。那么现在需要解决几个问题。

  • 第一：初始状态。很简单，f0=1,f1=aif_0 = 1, f_1 = a_i。
  • 第二：如何合并区间。假如说我们要处理 fif_i 的答案，就相当于在 ii 个数字中间和两边加一个隔板，左右相乘并求和。形式化地，记 fl,frfl, fr 分别为左右子树的 ff，有 fx=∑i=0xfli×frx−if_x = \sum_{i=0}^{x} fl_i \times fr_{x - i} 。可以证明两边区间的贡献是可以被乘起来的。
  • 第三：取反操作。因为负负得正，所以只需要将选取奇数个数字乘起来的值取相反数即可。形式化地，fx=(−1)xfxf_x = (-1)^xf_x。
  • 第四：区间加操作。这个可以找个规律，参见 题解 P4247 【[清华集训2012]序列操作】 by Limit，然后拆一下贡献。

然后就只需要实现了。

const int MODN = 19940417;
const int MAXN = 50006;
int C[MAXN][21];
int arr[MAXN];

struct Sgt;

struct Sgt {	
	struct Data { int len; array<i64, 21> f; Data() { len = -1; } };
	struct Lazy { i64 add; int rev; Lazy() { add = rev = 0; } typedef void(*Updater)(Data&, Lazy&, i64); };
	struct Node { int l, r; Data dat; Lazy lz; } tr[MAXN * 4];
	static inline Data merge(const Data& lhs, const Data& rhs) {
		Data result; fill(result.f.begin(), result.f.end(), 0);
		result.len = lhs.len + rhs.len;
		const int limit = min(result.len, 20);
		for (int i = 0; i <= limit; i++) {
			for (int j = 0; j <= limit; j++) {
				if (i + j <= 20) (result.f[i + j] += lhs.f[i] * rhs.f[j] % MODN) %= MODN;
			}
		}
		return result;
	}
	static inline void updlz_add(Data& dat, Lazy& lz, i64 delta) {
		for (int i = min(dat.len, 20); i > 0; i--) {
			i64 tp = delta;
			for (int j = i - 1; j >= 0; j--) {
				((dat.f[i] += dat.f[j] * C[dat.len - j][i - j] % MODN * tp % MODN) += MODN) %= MODN;
				(tp *= delta) %= MODN;
			}
		}
		(lz.add += delta) %= MODN;
	}
	static inline void updlz_rev(Data& dat, Lazy& lz, i64 val = 0) {
		for (int i = 0; i <= min(dat.len, 20); i++) { if (i & 1) dat.f[i] = ((-dat.f[i]) % MODN + MODN) % MODN; }
		lz.rev ^= 1; lz.add = (-lz.add % MODN + MODN) % MODN;
	}

	inline void pushdown(int p) {
		if (tr[p].lz.rev) {
			updlz_rev(tr[p << 1].dat, tr[p << 1].lz), updlz_rev(tr[p << 1 | 1].dat, tr[p << 1 | 1].lz);
			tr[p].lz.rev = 0;
		}
		if (tr[p].lz.add) {
			updlz_add(tr[p << 1].dat, tr[p << 1].lz, tr[p].lz.add), updlz_add(tr[p << 1 | 1].dat, tr[p << 1 | 1].lz, tr[p].lz.add);
			tr[p].lz.add = 0;
		}
	}
	
	template<Lazy::Updater updlz> void update(int l, int r, i64 val, int p = 1) {
		if (tr[p].l > r || tr[p].r < l) return;
		if (l <= tr[p].l && tr[p].r <= r) { updlz(tr[p].dat, tr[p].lz, val); return; }
		pushdown(p);
		update<updlz>(l, r, val, p << 1), update<updlz>(l, r, val, p << 1 | 1);
		tr[p].dat = merge(tr[p << 1].dat, tr[p << 1 | 1].dat);
	}

	Data query(int l, int r, int p = 1) {
		if (l <= tr[p].l && tr[p].r <= r) return tr[p].dat;
		pushdown(p);
		int mid = (tr[p].l + tr[p].r) >> 1;
		if (r <= mid) return query(l, r, p << 1); // [l, r] ...mid
		if (l >= mid + 1) return query(l, r, p << 1 | 1); // mid... [l, r]
		// l...mid...r
		return merge(query(l, r, p << 1), query(l, r, p << 1 | 1));
	}
	
	void build(int l, int r, int p = 1) {
		tr[p].l = l, tr[p].r = r;
		if (l == r) {
			tr[p].dat.len = 1; tr[p].dat.f[0] = 1;
			tr[p].dat.f[1] = arr[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, p << 1); build(mid + 1, r, p << 1 | 1);
		tr[p].dat = merge(tr[p << 1].dat, tr[p << 1 | 1].dat);
	}
} sg;

signed main()
{
	C[0][0] = 1;
	for (int i = 1; i <= 50000; i++) {
		for (int j = 0; j <= min(i, 20); j++) {
			C[i][j] += C[i - 1][j];
			if (j - 1 >= 0) C[i][j] += C[i - 1][j - 1];
			C[i][j] %= MODN;
		}
	}
	// 节约篇幅，不贴更多了
}

[SCOI2016] 萌萌哒

Luogu

题意：

告诉你一些限制条件，每个条件表示为四个数，l1,r1,l2,r2l_1,r_1,l_2,r_2，即两个长度相同的区间，表示子串 Sl1Sl1+1Sl1+2⋯Sr1S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1} 与 Sl2Sl2+1Sl2+2⋯Sr2S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2} 完全相同。然后统计长度为 nn 且满足这些约束条件的数字有多少个。

题解有人说暴力并查集做法是普及组的水平，但是我想了很久才想到，所以我的水平是普及-------。

30pts 的暴力：

int fa[10005];
int findfa(int x) { return fa[x] == x ? x : fa[x] = findfa(fa[x]); }
inline bool check(int x, int y) { return findfa(x) == findfa(y); }
inline void merge(int x, int y) { check(x, y) || (fa[findfa(x)] = findfa(y)); }
inline void init(int x) { for (int i = 1; i <= x; i++) fa[i] = i; }
char vis[10005];
const int MODN = 1e9 + 7;

int main()
{
	int n, m;
	cin >> n >> m;
	init(n);
	for (int i = 1; i <= m; i++) {
		int l1, r1, l2, r2;
		cin >> l1 >> r1 >> l2 >> r2;
		for (int j = l1; j <= r1; j++) {
			merge(j, j - l1 + l2);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (!vis[findfa(i)]) ans += vis[fa[i]] = 1;
	}
	cout << 9ll * powmod(10, ans - 1) % MODN << '\n';
}

发现时间瓶颈在 每一个区间都要暴力连边。于是想，如果可以区间连区间就好了！于是注意力惊人的你注意到了 并查集的合并是一个可重复贡献的过程。然后你就想到了 ST 表，真是令人感到惊叹的注意力。

现在需要解决两个问题。

  1. 怎样区间连接区间？写一个看上去有点像二进制拆分的东西，但是我好像说不清楚，所以直接看代码。
  2. 怎样统计答案？只需要把这个区间的合并的信息传到下一个区间就可以了，可以理解成一个倍增的逆过程。具体见代码。
int main()
{
	int n, m;
	cin >> n >> m;
	init(n);
	const int top = floor(log2(n));
	for (int i = 1; i <= m; i++) {
		int l1, r1, l2, r2;
		cin >> l1 >> r1 >> l2 >> r2;
		for (int k = top; k >= 0; k--)
			if (l1 + (1 << k) - 1 <= r1) {
				merge(l1, l2, k);
				l1 += 1 << k;
				l2 += 1 << k;
			}
	}
	for (int k = top; k; k--)
		for (int i = 1; i + (1 << k) - 1 <= n; i++) {
			int pos = findfa(i, k);
			merge(i, pos, k - 1);
			merge(i + (1 << (k - 1)), pos + (1 << (k - 1)), k - 1);
		}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (fa[i][0] == i) ans++;
	}
	cout << 9ll * powmod(10, ans - 1) % MODN << '\n';
}

08??A

题意：给定一张无向图和 m (3×105)m\space (3\times 10^5) 次加边（带权边）操作，如果某次操作之后这张图的 1→n (5×104)1\to n\space (5\times 10^4) 的最短路小于等于 TT，则清空所有边。

找到所有删边的操作的时刻。

这道题数据比较水，让我们来看看赛时代码：

赛时代码：可以证明最短路是单调不上升的，所以二分可以拿到很多分。

#define unlikely(cond) (__builtin_expect((cond), 0))
using namespace std;

const int MAXN = 5e4 + 2, MAXM = 3e5 + 5;

int dis[MAXN], T, n;
uint8_t vis[MAXN];

int head[MAXN], edcnt;
int lowerE, upperE;
struct Ed { int v, w, nxt; } edge[MAXM * 2];
vector<int> result, erfe;

// 1, 2 为同一条边 
inline void add_edge(int u, int v, int w) { edge[++edcnt] = { v, w, head[u] }; head[u] = edcnt; }

using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;

inline int dij()
{
	fill(vis, vis + n + 1, 0), fill(dis, dis + n + 1, 0x3f3f3f3f);
	dis[1] = 0;
	q.push({ 0, 1 });
	while (!q.empty()) {
		const pii top = q.top(); q.pop();
		const int u = top.second, ow = top.first;
		if (vis[u]) continue;
		vis[u] = 1;
		for (int e = head[u]; e; e = edge[e].nxt) {
			if (lowerE > e) break;
			if (e <= upperE) {
				int v = edge[e].v, w = edge[e].w;
				if (dis[v] > ow + w) {
					dis[v] = ow + w;
					q.push({ dis[v], v });
				}
			}
		}
	}
	return dis[n];
}

struct my_greater {
	bool operator()(const int idx, const int val) const {
		upperE = idx * 2;
		return dij() > val;
	}
} gt;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	int u, v, w, q;
	cin >> n >> q >> T;
	erfe.reserve(q);
	for (int i = 1; i <= q; i++) {
		cin >> u >> v >> w;
		add_edge(u, v, w);
		add_edge(v, u, w);
		erfe.push_back(i);
	}
	int lowerq = 0;
	do {
		auto pos_iter = lower_bound(erfe.begin() + lowerq, erfe.end(), T, gt);
		if (pos_iter == erfe.end()) break;
		lowerq = *pos_iter;
		result.push_back(lowerq);
		lowerE = 2 * lowerq + 1;
	} while (true);
	cout << result.size() << '\n';
	for (auto x : result) cout << x << ' '; 
}

然后拿到了 60pts 的好分数。但是另一位神仙赛时二分搞过了，所以问了一下加了哪些优化（下面呈现到代码里了）。

只有两个小小的优化。

#define unlikely(cond) (__builtin_expect((cond), 0))
using namespace std;

const int MAXN = 5e4 + 2, MAXM = 3e5 + 5;

int dis[MAXN], T, n;
uint8_t vis[MAXN];

int lowerE, upperE;
vector<int> result, erfe;
struct Edge {
	int v, w, id;
	bool operator<(const Edge &s2) const { return id < s2.id; }
};
vector<Edge> gr[MAXN];

inline void add_edge(int u, int v, int w, int id) { gr[u].push_back({ v, w, id }); }

using pii = pair<int, int>;

inline bool dij()
{
	memset(vis + 1, 0, sizeof(char) * n);
	memset(dis + 2, 0x3f, sizeof(int) * (n - 1));
	priority_queue<pii, vector<pii>, greater<pii>> q;
	q.push({ 0, 1 });
	while (!q.empty()) {
		const pii top = q.top(); q.pop();
		const int u = top.second, ow = top.first;
		if (vis[u]) continue;
		vis[u] = 1;
		// Optimize 1. 二分到序号在现存边的位置
		auto it = lower_bound(
			gr[u].begin(),
			gr[u].end(),
			Edge { 0, 0, lowerE }
		);
		const auto end = gr[u].end();
		for (; it != end; it++) {
			// Optimize 2
			if (upperE < it->id) break;
			int v = it->v, w = it->w;
			if (dis[v] > ow + w) {
				dis[v] = ow + w;
				if (dis[n] <= T) return false;
				q.push({ dis[v], v });
			}
		}
	}
	return dis[n] > T;
}

struct {
	bool operator()(const int& idx, const int& val) const {
		upperE = idx * 2;
		return dij();
	}
} my_greater;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	int u, v, w, q;
	cin >> n >> q >> T;
	erfe.reserve(q);
	for (int i = 1; i <= q; i++) {
		cin >> u >> v >> w;
		add_edge(u, v, w, 2 * i - 1);
		add_edge(v, u, w, 2 * i);
		erfe.push_back(i);
	}
	int lowerq = 0;
	while (true) {
		auto pos_iter = lower_bound(erfe.begin() + lowerq, erfe.end(), T, my_greater);
		if (pos_iter == erfe.end()) break;
		lowerq = *pos_iter;
		result.push_back(lowerq);
		lowerE = 2 * lowerq + 1;
	}
	cout << result.size() << '\n';
	for (auto x : result) cout << x << ' '; 
}

取得 100 分的好成绩！虽然不是正解，但是懒得写了

[Ynoi2017] 由乃打扑克

Luogu

年轻人的第一道 Ynoi！

给你一个长为 nn 的序列 aa，需要支持 mm 次操作，操作有两种：

  1. 查询区间 [l,r][l,r] 的第 kk 小值。
  2. 区间 [l,r][l,r] 加上 kk。

n,q≤1×105n, q \le 1\times 10^5

思路：分块之后二分值域。对于每一个整块二分，边界暴力。

感谢 #pragma GCC unroll(8) 帮助我这样我就不需要手动展开了。

Record 有点慢但是过了。

优化：

  1. 在二分值域的 check 过程中，如果 需要查找的值 大于 这个块中的最大值 或者 小于 这个块中的最小值，可跳过。
  2. 维护区间最大值/最小值，这样可以减少二分的值域。
  3. #pragma GCC unroll(8) 激发了计算机的并行性能。
  4. 块长 360 的效率对于我这份暴力东西还是是足够的。
  5. 懒标记不要下传。
  6. 没用 long long。
int n, m;
#ifdef ONLINE_JUDGE
const int bklen = 360;
#else
const int bklen = 3;
#endif
int bkd[1005][bklen + 3], blen[1005], bkl[10005], bkr[10005], dat[100005], bkcnt;
int lz[1005], nk[100005];

template<class T = int>
struct int_iterator
{
public:
	using value_type = const T;
	using difference_type = T;	
	using pointer = const T*;
	using reference = const T;
	using iterator_category = std::random_access_iterator_tag;
	int_iterator(T x) : _val(x) {}
	value_type operator*() const { return _val; }
	int_iterator &operator+=(difference_type n) { _val += n; return *this; }
	int_iterator &operator++() { return *this += 1; }
	int_iterator &operator--() { return *this += -1; }
	difference_type operator-(const int_iterator &iit) const { return _val - iit._val; }
private:
	T _val;
};

inline int query_single(int val, int p) { return upper_bound(bkd[p] + 1, bkd[p] + blen[p] + 1, val - lz[p]) - bkd[p] - 1; }
inline void pushdown(int p) {
	int l = bkl[p], r = bkr[p];
	for (int i = l; i <= r; i++) bkd[p][i - l + 1] = dat[i];
	sort(bkd[p] + 1, bkd[p] + blen[p] + 1);
}

inline pair<int, int> get_range(int l, int r)
{
	int lb = bkl[nk[l]] < l ? nk[l] + 1 : nk[l];
	int rb = bkr[nk[r]] > r ? nk[r] - 1 : nk[r];
	int ll = 2e9, rr = -2e9;
	if (lb > rb) {
		#pragma GCC unroll(8)
		for (int i = l; i <= r; i++) {
			const int val = dat[i] + lz[nk[i]];
			if (ll > val) ll = val;
			if (rr < val) rr = val;
		}
		return { ll, rr };
	}
	int llz = lz[nk[l]], rlz = lz[nk[r]], lc = bkl[lb];
	#pragma GCC unroll(8)
	for (int i = l; i < lc; i++) {
		const int val = dat[i] + llz;
		if (ll > val) ll = val;
		if (rr < val) rr = val;
	}
	#pragma GCC unroll(8)
	for (int i = lb; i <= rb; i++) {
		ll = min(ll, bkd[i][1] + lz[i]);
		rr = max(rr, bkd[i][blen[i]] + lz[i]);
	}
	#pragma GCC unroll(8)
	for (int i = bkr[rb] + 1; i <= r; i++) {
		const int val = dat[i] + rlz;
		if (ll > val) ll = val;
		if (rr < val) rr = val;
	}
	return { ll, rr };
}

inline int query(int l, int r, int k)
{
	const int lb = bkl[nk[l]] < l ? nk[l] + 1 : nk[l];
	const int rb = bkr[nk[r]] > r ? nk[r] - 1 : nk[r];
	const auto ran = get_range(l, r);
	const int mn = ran.first, mx = ran.second;
	const auto cmp = [lb, rb, l, r, k](int _, int rval) -> bool {
		int cnt = 0;
		if (lb > rb) {
			#pragma GCC unroll(8)
			for (int i = l; i <= r; i++) if (dat[i] + lz[nk[i]] <= rval) cnt++;
		} else {
			int llz = lz[nk[l]], rlz = lz[nk[r]], lc = bkl[lb];
			#pragma GCC unroll(8)
			for (int i = l; i < lc; i++) if (dat[i] + llz <= rval) cnt++;
			#pragma GCC unroll(8)
			for (int i = lb; i <= rb; i++) {
				if (rval <  bkd[i][1]) continue;
				if (rval >= bkd[i][blen[i]] + lz[i]) { cnt += blen[i]; continue; }
				cnt += query_single(rval, i);
			}
			#pragma GCC unroll(8)
			for (int i = bkr[rb] + 1; i <= r; i++) if (dat[i] + rlz <= rval) cnt++;
		}
		return cnt >= k;
	};
	return *upper_bound(int_iterator<int>(mn), int_iterator<int>(mx), k, cmp);
}

inline void add(int l, int r, int k)
{
	int lb = bkl[nk[l]] < l ? nk[l] + 1 : nk[l];
	int rb = bkr[nk[r]] > r ? nk[r] - 1 : nk[r];
	if (lb > rb) {
		#pragma GCC unroll(8)
		for (int i = l; i <= r; i++) dat[i] += k;
		pushdown(nk[l]);
		if (nk[l] != nk[r]) pushdown(nk[r]);
		return;
	}
	#pragma GCC unroll(8)
	for (int i = lb; i <= rb; i++) lz[i] += k;
	if (l < bkl[lb]) {
		int lim = bkl[lb];
		#pragma GCC unroll(8)
		for (int i = l; i < lim; i++) dat[i] += k;
		pushdown(nk[l]);
	}
	if (r > bkr[rb]) {
		#pragma GCC unroll(8)
		for (int i = bkr[rb] + 1; i <= r; i++) dat[i] += k;
		pushdown(nk[r]);
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> dat[i];
	}

	for (int i = 1; i <= n; i += bklen) {
		++bkcnt;
		bkl[bkcnt] = i, bkr[bkcnt] = min(i + bklen - 1, n);
		int len = bkr[bkcnt] - bkl[bkcnt] + 1;
		const int top = bkr[bkcnt];
		#pragma GCC unroll(8)
		for (int j = i; j <= top; j++) {
			bkd[bkcnt][j - i + 1] = dat[j];
			nk[j] = bkcnt;
		}
		blen[bkcnt] = len;
		sort(bkd[bkcnt] + 1, bkd[bkcnt] + len + 1);
	}

	int opt, l, r, k;
	for (int i = 1; i <= m; i++) {
		cin >> opt >> l >> r >> k;
		if (opt == 1) {
			cout << query(l, r, k) << '\n';
		} else {
			add(l, r, k);
		}
	}
}
Copyright (C) Imken Luo
This post is licensed under CC-BY-NC-SA 4.0.
本系列：月度做题记录