什么抽象题目

pystraf11 · 2025-12-04 21:14:42 · 题解

Description

给你序列 a=(a_1,a_2,\cdots,a_n)，q 次查询 (l,r,L,R,p,x)，求：

要求 强制在线。

Limitations

Solution

视 n,q 同阶。

先对 a 做 序列 分块，散块暴力算，重点在整块。由于 V 不大，考虑对 p 根号分治。

若 p\ge \sqrt V，则满足条件的数至多 \sqrt V 个。直接在 [L,R] 中逐个枚举，现在需要查询整块区间内一个数的出现次数，显然需要单次 O(1)，预处理 c(i,j) 表示前 i 个序列块中 j 出现的次数即可。

然后是 p<\sqrt V，这些 p 的余数种类数至多 \sqrt V。对 值域 分块，散块类似上面，直接查前缀和做掉，下面来到最困难的部分。

对每个 p<\sqrt V，将序列 a 按照 a_i\bmod p 做 计数 排序（相同的按 i 排），存下原下标。将得到的所有数组 d(p,x) 拼起来，记为 v，同样对 v 分块，块数 为 O(\sqrt {nV})。

指针求出 P(t,p,x) 表示 d(p,x) 中处在前 t 个 序列块 中的最后一个元素的下标。那么 序列 上的第 [l,r] 块可以被映射到 v 上的 (P(l-1,p,x),P(r,p,x)] 这段区间。

现在只需要查询 v[l,r] 中处在第 [L,R] 个 值域块 的元素数量，同样散块暴力，整块预处理 w(i,j) 表示前 i 个 v 块在第 j 个值域块出现的次数即可。

终于做完了，时空复杂度均为 O(V\sqrt n)，开内存池并加上快读即可通过，笔者的最大点在 1.3\text{s} 左右。

::::info[code]

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
    if(a < b){ a = b; return true; }
    return false;
}

template<class T>
bool chmin(T &a, const T &b){
    if(a > b){ a = b; return true; }
    return false;
}

namespace Fastio {}
using Fastio::qin;
using Fastio::qout;

namespace pool {
    constexpr int cap = 1.5e8 + 5;
    int pool[cap], *ptr = pool;

    inline int* New(int n) {
        int *res = ptr;
        ptr += n;
        return res;
    }
}
using pool::New;

constexpr int S = 512, T = 256, V = 2e5 + 10;

struct Block1 {
    int n, blocks;
    vector<int*> pre;

    inline void init(int _n, int *a) {
        n = _n, blocks = ((n - 1) >> 9) + 1;
        pre.resize(blocks);
        for (int i = 0; i < blocks; i++) {
            pre[i] = New(V);
            if (i > 0) for (int j = 0; j < V; j++) pre[i][j] = pre[i - 1][j];
            for (int j = lft(i); j <= rgt(i); j++) pre[i][a[j]]++;
        }
    }

    inline int query(int l, int r, int x) {
        return pre[r][x] - (l ? pre[l - 1][x] : 0);
    }

    inline int bel(int x) { return x >> 9; }
    inline int lft(int x) { return x << 9; }
    inline int rgt(int x) { return min(n, (x + 1) << 9) - 1; }
} b1;

struct Block2 {
    static constexpr int blocks = ((V - 1) >> 9) + 1;
    inline int bel(int x) { return x >> 9; }
    inline int lft(int x) { return x << 9; }
    inline int rgt(int x) { return min(V, (x + 1) << 9) - 1; }
} b2;

struct Block3 {
    int m, *a, blocks, *v, *l, *r;
    vector<int*> b, P;

    inline void init(int n, int *_a) {
        a = _a, m = 0;
        vector<basic_string<int>> d(T);
        v = New(n * T);
        l = New(T * T);
        r = New(T * T);

        for (int i = 1; i < T; i++) {
            for (int j = 0; j < T; j++) d[j].clear();
            for (int j = 0; j < n; j++) d[a[j] % i] += j;
            for (int j = 0; j < T; j++) {
                l[i * T + j] = m;
                for (auto u : d[j]) v[m++] = u;
                r[i * T + j] = m - 1;
            }
        }
        blocks = ((m - 1) >> 9) + 1;

        P.resize(b1.blocks);
        for (int i = 0; i < b1.blocks; i++) P[i] = New(T * T);

        for (int i = 1; i < T; i++)
            for (int j = 0; j < i; j++)
                for (int t = 0, u = l[i * T + j]; t < b1.blocks; t++) {
                    while (u <= r[i * T + j] && b1.bel(v[u]) <= t) u++;
                    P[t][i * T + j] = u - 1; 
                }

        b.resize(b2.blocks);
        for (int i = 0; i < b2.blocks; i++) b[i] = New(blocks);

        for (int i = 0; i < blocks; i++) {
            if (i > 0) for (int j = 0; j < b2.blocks; j++) b[j][i] = b[j][i - 1];
            for (int j = lft(i); j <= rgt(i); j++) b[b2.bel(a[v[j]])][i]++;
        }
    }

    inline int query(int l, int r, int L, int R) {
        int e = 0;
        if (bel(l) == bel(r)) {
            for (int i = l; i <= r; i++) e += (L <= b2.bel(a[v[i]]) && b2.bel(a[v[i]]) <= R);
            return e;
        }
        for (int i = L; i <= R; i++) e += b[i][bel(r) - 1] - b[i][bel(l)];
        return e + query(l, rgt(bel(l)), L, R) + query(lft(bel(r)), r, L, R);
    }

    inline int query(int l, int r, int L, int R, int p, int x) {
        return query((l ? P[l - 1][p * T + x] + 1 : 0), P[r][p * T + x], L, R);
    }

    inline int bel(int x) { return x >> 9; }
    inline int lft(int x) { return x << 9; }
    inline int rgt(int x) { return min(m, (x + 1) << 9) - 1; }
} b3;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, o;
    qin >> n >> o;

    int *a = New(n);
    for (int i = 0; i < n; i++) qin >> a[i];

    b1.init(n, a);
    b3.init(n, a);

    auto query = [&](int l, int r, int L, int R, int p, int x) {
        int ans = 0;
        if (b1.bel(l) == b1.bel(r)) {
            for (int i = l; i <= r; i++) ans += (L <= a[i] && a[i] <= R && a[i] % p == x);
            return ans;
        }
        int ql = b1.bel(l) + 1, qr = b1.bel(r) - 1;
        for (int i = l; i < b1.lft(ql); i++) ans += (L <= a[i] && a[i] <= R && a[i] % p == x);
        for (int i = r; i > b1.rgt(qr); i--) ans += (L <= a[i] && a[i] <= R && a[i] % p == x);
        if (ql > qr) return ans;
        if (p >= T) {
            for (int i = p * (L / p + (L % p > x)) + x; i <= R; i += p) ans += b1.query(ql, qr, i);
            return ans;
        }

        if (b2.bel(L) == b2.bel(R)) {
            for (int i = L; i <= R; ++i) ans += (i % p == x) * b1.query(ql, qr, i);
            return ans;
        }

        int qL = b2.bel(L) + 1, qR = b2.bel(R) - 1;
        for (int i = L; i < b2.lft(qL); i++) ans += (i % p == x) * b1.query(ql, qr, i);
        for (int i = R; i > b2.rgt(qR); i--) ans += (i % p == x) * b1.query(ql, qr, i);
        if (qL > qR) return ans;
        ans += b3.query(ql, qr, qL, qR, p, x);
        return ans;
    };

    int q;
    qin >> q;

    for (int i = 0, l, r, L, R, p, x, last = 0; i < q; i++) {
        qin >> l >> r >> L >> R >> p >> x, last *= o;
        l ^= last, r ^= last, L ^= last, R ^= last, p ^= last, x ^= last;
        l--, r--;
        qout << (last = query(l, r, L, R, p, x)) << '\n';
    }

    return 0;
}

::::