牛客 NC21125 践踏

分析

• $x+k?t,t\in Z$ 对于 $y\in [0,k?1]$ 存在 $?x=y+k?t$ ，所以对于一个区间 $[l,r]$ 只用记录该区间所包含的对应的 $y\in [0,k?1]$ 。
• 如果区间长度 $\ge k$ ，一定包含了整个 $[0,k?1]$ ，如果区间长度 $\le k$ ，对 $l,r$ 取模后会有两种情况。
• • $l\le r$ ，正常操作。
• • $l>r$ ，分为 $[0,r],[l,k]$ 操作。
• 查询只需要查询 $x\%k$ 即可。
• 那么就是一个区间加，单点查询的操作，用树状数组维护一个差分数组即可。
• 对于 $k=0$ ，就是正常的不用取模的操作，但是数据比较大，离散化即可。
• 有个小细节，一般树状数组是以 $0$ 退出循环，但是 $x,l,r$ 的取值可以为 $0$ ，所以向后退一位即可。见代码。

Think Twice, Code Once

vector<int> tr(N);
signed main() {
    auto add = [] (int x, int v, int n) {
        for (int i = x + 1; i <= n; i += lowbit(i)) tr[i] += v;
    };
    auto query = [&] (int r) {
        int ans = 0;
        for (int i = r + 1; i; i -= lowbit(i)) ans += tr[i];
        return ans;
    };
    int T = 1;
//    T = read();
    while (T--) {
        int n = read(), k = read();
        if (!n) return puts("fafa"), 0;
        if (!k) {
            vector<int> vec;
            vector<tuple<int, int, int>> Opt;
            while (n--) {
                int op = read();
                if (op ^ 3) {
                    int l = read(), r = read();
                    Opt.push_back({op, l, r});
                    vec.push_back(l), vec.push_back(r);
                }
                else {
                    int x = read();
                    Opt.push_back({op, x, 0});
                    vec.push_back(x);
                }
            }
            sort(vec.begin(), vec.end());
            vec.erase(unique(vec.begin(), vec.end()), vec.end());
            for (auto [op, l, r]: Opt) {
                if (op ^ 3) {
                    int pos1 = lower_bound(vec.begin(), vec.end(), l) - vec.begin();
                    int pos2 = lower_bound(vec.begin(), vec.end(), r) - vec.begin();
                    if (op ^ 1) add(pos1, -1, vec.size()), add(pos2 + 1, 1, vec.size());
                    else add(pos1, 1, vec.size()), add(pos2 + 1, -1, vec.size());
                }
                else {
                    int pos = lower_bound(vec.begin(), vec.end(), l) - vec.begin();
                    writeln(query(pos));
                }
            }
        }
        else {
            while (n--) {
                int op = read();
                if (op ^ 3) {
                    int l = read(), r = read();
                    if (r - l + 1 >= k) {
                        if (op ^ 1) add(0, -1, k);
                        else add(0, 1, k);
                    }
                    else {
                        l %= k, r %= k;
                        if (l <= r) {
                            if (op ^ 1) add(l, -1, k), add(r + 1, 1, k);
                            else add(l, 1, k), add(r + 1, -1, k);
                        }
                        else {
                            if (op ^ 1) {
                                add(0, -1, k), add(r + 1, 1, k);
                                add(l, -1, k);
                            }
                            else {
                                add(0, 1, k), add(r + 1, -1, k);
                                add(l, 1, k);
                            }
                        }
                    }
                }
                else {
                    int x = read() % k;
                    writeln(query(x));
                }
            }
        }
    }
    return 0;
}