思路:
如果k不为0, 那么就是对k取模意义下的区间更新, 单点查询
否则, 就是普通的区间更新, 单点查询
代码:
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 2e4 + ;
int bit[N], up;
vector<int> vc;
piii a[N];
void add(int x, int a) {
while(x <= up) bit[x] += a, x += x&-x;
}
int sum(int x) {
int res = ;
while(x) res += bit[x], x -= x&-x;
return res;
}
int main() {
int n, k, op, l, r;
scanf("%d %d", &n, &k);
if(n == ) return *puts("fafa");
if(k) {
up = k;
for (int i = ; i <= n; i++) {
scanf("%d %d", &op, &l);
if(op == ) {
scanf("%d", &r);
if(r - l + >= k) {
add(, ), add(k+, -);
continue;
}
(l %= k) += ;
(r %= k) += ;
if(l <= r) add(l, ), add(r+, -);
else add(, ), add(r+, -), add(l, ), add(k+, -);
}
else if(op == ) {
scanf("%d", &r);
if(r - l + >= k) {
add(, -), add(k+, );
continue;
}
(l %= k) += ;
(r %= k) += ;
if(l <= r) add(l, -), add(r+, );
else add(, -), add(r+, ), add(l, -), add(k+, );
}
else {
printf("%d\n", sum(l%k + ));
}
}
}
else {
up = *n;
for (int i = ; i <= n; i++) {
scanf("%d %d", &a[i].se, &a[i].fi.fi);
vc.pb(a[i].fi.fi);
if(a[i].se <= ) {
scanf("%d", &a[i].fi.se);
vc.pb(a[i].fi.se);
}
}
sort(vc.begin(), vc.end());
vc.erase(unique(vc.begin(), vc.end()), vc.end());
for (int i = ; i <= n; i++) {
if(a[i].se == ) {
l = lower_bound(vc.begin(), vc.end(), a[i].fi.fi) - vc.begin() + ;
r = lower_bound(vc.begin(), vc.end(), a[i].fi.se) - vc.begin() + ;
add(l, );
add(r+, -);
}
else if(a[i].se == ) {
l = lower_bound(vc.begin(), vc.end(), a[i].fi.fi) - vc.begin() + ;
r = lower_bound(vc.begin(), vc.end(), a[i].fi.se) - vc.begin() + ;
add(l, -);
add(r+, );
}
else {
int x = lower_bound(vc.begin(), vc.end(), a[i].fi.fi) - vc.begin() + ;
printf("%d\n", sum(x));
}
}
}
return ;
}