[AFOI]区间与除法

Posted on Edited on In Word count in article: 641 Reading time ≈ 2 mins.
字典树好题

[AFOI]区间与除法

题目大意:

给定一个序列\(A\), 叫操作序列, 序列\(B\), 叫原序列

给定一个除数\(d\), 若\(A_i\)能够通过不断整除\(d\)变成\(B_j\), 那么就称作\(A_i\)可以被\(B_j\)消除

有\(q\)次询问, 每次询问给定一个区间\([l,r]\)

求在区间\([l,r]\)中至少需要多少个原数才能消除\(A_l\sim A_r\)

分析:

拿着题的第一想法是把所有的\(A\)去操作一下, 得到可行的原数, 然后就能得到一个二进制数表示分别能被那些原数消除, 然后再贪心的求得答案

显然这样做是不好实现的

于是看看题解

真的是绝了!

那么久转化一下思路, 我们似乎可以把所有的数看成一个\(d\)进制的数

似乎这样就简单多了, 只要原数是\(A_i\)的某个前缀就可以了

如果某个原数是某个原数的真前缀, 那么我们只需要被包含的那个前缀即可

所以, 我们最后得到的每个\(A_i\)对应的原数一定是唯一的

那么这个时候, 直接或起来, 求这个二进制数有多少个\(1\)即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

ll n, m, d, q;
ll a[maxn], ys[maxn];
ll f[maxn][22], log_[maxn] = {-1};
int Ch[maxn][15], end[maxn], id;
int stk[maxn], top, cnt;
bool t[maxn];

inline void cf(ll x)
{
    top = 0;
    while (x) {
        stk[++top] = x % d;
        x /= d;
    }
}

inline void Insert(ll x)
{
    cf(x);
    int root(0);
    for (int i = top; i; --i) {
        int now = stk[i];
        if (!Ch[root][now]) Ch[root][now] = ++id;
        root = Ch[root][now];
        if (end[root]) return;
    }
    end[root] = ++cnt;
}

inline int Query(ll x)
{
    cf(x);
    int root(0);
    for (int i = top; i; --i) {
        int now = stk[i];
        if (!Ch[root][now]) break;
        root = Ch[root][now];
        if (end[root]) return end[root]; 
    }
    return -1;
}

signed main()
{
    n = __read(), m = __read(), d = __read(), q = __read();
    for (int i = 1; i <= n; ++i) a[i] = __read();
    for (int i = 1; i <= m; ++i) ys[i] = __read();
    for (int i = 1; i <= m; ++i) Insert(ys[i]);
    for (int i = 1; i <= n; ++i) {
        int k = Query(a[i]);
        log_[i] = log_[i >> 1] + 1;
        if (~k) f[i][0] = (1ll << k);
    }
    for (int j = 1; j <= log_[n]; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            f[i][j] = f[i][j - 1] | f[i + (1 << j - 1)][j - 1];
    while (q--) {
        int l = __read(), r = __read();
        int len = log_[r - l + 1];
        ll ans = f[l][len] | f[r - (1 << len) + 1][len];
        int cnt(0);
        while (ans) {
            if (ans & 1) ++cnt;
            ans >>= 1;
        }
        printf ("%d\n", cnt);
    }
    system("pause");
}