题解 | 2021秋季算法入门班第十一章习题：线段树、树状数组 践踏

题意

给我们3个操作，分别是新增一个区间，删除一个已有区间，以及查询目前有多少个区间包含点$x+k\ast tx+k*t$，对于操作3，我最开始没有读懂，wa了几发，操作3的意思就是，t取任意整数，我以为其是定值。

题解

我们首先考虑k为0的情况怎么做，也就是查有多少个区间包含了点x，我们考虑什么样的区间不会对答案产生贡献，也就是右端点小于点x的区间和左端点大于点x的区间，那么我们离散化之后，利用树状数组维护差分前缀和即可，对于操作1，add(L, 1),add(R+1,-1),操作二add(L,-1),add(R+1,1),操作3，query(x)即可

我们考虑k不为0的情况，我们需要查询所有满足y = x + k * t的点，肯定是不能够暴力的，对于这一类点，我们可以发现他们在模k意义下是相等的，那么我们也可以想到将所有的区间变成模k意义下的区间，查询其是否包含点$xx\; \%\; k$模k后的值，我们所有的区间，x都是正数，所有这样肯定是没有问题的，如果有负数的话，就会复杂一些。因为我们需要使用树状数组，假如我们在树状数组上查询或者修改小于等于0的问题，就g了，建议自己试一下，所有我们取模的时候，将其模k后加1就可以避免查询或者修改为0的位置。

接下来我们考虑如何在树状数组上实现，如果区间[L, R]的长度大于等于k，对于任意的点x，我们假设其模k并加1后的值为y，我们一定是包含他的，所以我们直接add(1, 1), add(k + 1, -1), 我们设经过处理之后的L为L1,处理之后的R为R1,那么如果$L1\le R1L1\; \backslash leq\; R1$，我们直接add(L, 1), add(R + 1, -1),否则满足条件的区间是[L1, k]和[1, R1]，所以我们需要add(1,1),add(R1 + 1, -1), add(L1, 1), add(k + 1, -1); 查询的时候直接query(y)即可

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i ++ ) 
#define per(i, a, n) for (int i = n; i >= a; i -- )
#define IO ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);

constexpr int N = 3e5 + 10;
int n, k;
vector<int> v;
struct node {
	int op, l, r, x;
}a[N];
struct BIT {
	int c[N];
	void modify(int i, int t) {
		for (; i < N; i += i & -i) {
			c[i] += t;
		}
		return;
	}
	int query(int i) {
		int ans = 0;
		if (i <= 0) return ans;
		for (; i > 0; i -= i & -i) {
			ans += c[i];
		}
		return ans;
	}
}tree;

int getid(int x) {
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

void solve() {
	cin >> n >> k;
	if (n == 0) {
		cout << "fafa";
		return;
	}
	rep(i, 1, n) {
		int op, l, r, x;
		cin >> op;
		if (op == 1) {
			cin >> a[i].l >> a[i].r;
			v.pb(a[i].l);
			v.pb(a[i].r);
			a[i].op = 1;
		} else if (op == 2) {
			a[i].op = 2;
			cin >> a[i].l >> a[i].r;
			v.pb(a[i].l);
			v.pb(a[i].r);
		} else {
			cin >> x;
			a[i].op = 3;
			a[i].x = x;
			v.pb(x);
		}
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	if (k == 0) {
		rep(i, 1, n) {
			if (a[i].op == 1) {
				int l = getid(a[i].l), r = getid(a[i].r);
				tree.modify(l, 1), tree.modify(r + 1, -1);
			}
			else if (a[i].op == 2) {
				int l = getid(a[i].l), r = getid(a[i].r);
				tree.modify(l, -1), tree.modify(r + 1, 1);
			} else {
				int l = getid(a[i].x);
				cout << tree.query(l) << '\n';
			}
		}
	} else {
		rep(i, 1, n) {
			if (a[i].op == 1) {
				int l = a[i].l, r = a[i].r;
				if (r - l + 1 >= k) {
					tree.modify(1, 1);
					tree.modify(k + 1, -1);
				} else {
					l = (l % k) + 1, r = (r % k) + 1;
					if (l <= r) {
						tree.modify(l, 1);
						tree.modify(r + 1, -1);
					} else {
						tree.modify(1, 1);
						tree.modify(r + 1, -1);
						tree.modify(l, 1);
						tree.modify(k + 1, -1);
					}
				}
			} else if (a[i].op == 2) {
				int l = a[i].l, r = a[i].r;
				if (r - l + 1 >= k) {
					tree.modify(1, -1);
					tree.modify(k + 1, 1);
				} else {
					l = (l % k) + 1, r = (r % k) + 1;
					if (l <= r) {
						tree.modify(l, -1);
						tree.modify(r + 1, 1);
					} else {
						tree.modify(1, -1);
						tree.modify(r + 1, 1);
						tree.modify(l, -1);
						tree.modify(k + 1, 1);
					}
				}
			} else {
				int l = a[i].x;
				l = (l % k) + 1;
				cout << tree.query(l) << '\n';
			}
		}
	}
}	

signed main(void) {
    IO;
	int t;
	// cin >> t;
	t = 1;
	while (t -- ) {
		solve();
	}
    return 0;
}