题目传送门

Description

首先给定一个定值k,支持如下操作(在数轴上)

  1. 加入一条线段[l,r]
  2. 删除一条已经存在的线段
  3. 给定x,问有多少个区间包含x+kt,其中t是一个整数变量,即t ∈ Z
    比如说当x=2,k=3的时候,区间[7,10]是应该算入答案的,因为x+2k=8,且7 ≤ 8 ≤ 10

如果n=0,那么你只需要输出一行"fafa"然后结束程序即可(注意不输出双引号)

Solution

很妙地,我们把所有下标对 $k$ 取模。

那么所有操作就合并到一个我们能接受的范围内。

注意一条线段可能被分为前后两段。

用树状数组统计一下。

$k=0$ 的情况就离散化一下就行了。

Code

/*
 * @Name: 270B.cpp
 * @Author: Lovely_XianShen
 * @Date: 2019-11-06 16:15:16
 * @Aqours!Sunshine!!
 */
#include<bits/stdc++.h>
using namespace std;

inline int read() {
    int a = 0; char x = getchar();
    while (x < '0' || x > '9')x = getchar();
    while (x >= '0' && x <= '9')a = (a << 3) + (a << 1) + x - 48, x = getchar();
    return a;
}

const int N = 1e5 + 5;
typedef long long ll;

int c[N];

inline int lowbit(int x) {
    return x & (-x);
}

int n, k;

inline void add(int x, int d) {
    while (x <= 100000) {
        c[x] += d;
        x += lowbit(x);
    }
    return;
}

inline int query(int x) {
    ll res = 0;
    while (x) {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

struct askq {
    int f, l, r;
} ask[N << 1];
int A[N];

void Add(int l, int r, int d) {
    if (r - l + 1 >= k) {
        add(1, d);
        return ;
    }
    r %= k;
    l %= k;
    if (!r)r = k;
    if (!l)l = k;
    if (r >= l) {
        add(l, d);
        add(r + 1, -d);
    } else {
        add(1, d);
        add(r + 1, -d);
        add(l, d);
    }
    return ;
}

void solve(int x) {
    x %= k;
    if (!x)x = k;
    printf("%d\n", query(x));
    return ;
}

int main() {
    n = read();
    k = read();
    if (n == 0) {
        cout << "fafa" << endl;
        return 0;
    }
    if (k == 0) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            ask[i].f = read();
            if (ask[i].f == 1 || ask[i].f == 2)
                ask[i].l = read(), ask[i].r = read();
            else
                ask[i].l = read(), A[++cnt] = ask[i].l;
        }
        sort(A + 1, A + cnt + 1);
        cnt = unique(A + 1, A + cnt + 1) - A - 1;
        int num = cnt + 1;
        for (int i = 1; i <= n; i++) {
            ask[i].l = lower_bound(A + 1, A + cnt + 1, ask[i].l) - A;
            ask[i].r = upper_bound(A + 1, A + cnt + 1, ask[i].r) - A - 1;
            if ((ask[i].f < 3 && ask[i].l > ask[i].r))
                continue;
            if (ask[i].f == 1)
                add(ask[i].l, 1), add(ask[i].r + 1, -1);
            if (ask[i].f == 2)
                add(ask[i].l, -1), add(ask[i].r + 1, 1);
            if (ask[i].f == 3)
                printf("%d\n", query(ask[i].l));
        }
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        int f, l, r;
        f = read();
        if (f == 1) {
            l = read();
            r = read();
            Add(l, r, 1);
        }
        if (f == 2) {
            l = read();
            r = read();
            Add(l, r, -1);
        }
        if (f == 3) {
            l = read();
            solve(l);
        }
    }
    return 0;
}