HDU 6964. I love counting

发表于 分类于

链接

https://acm.hdu.edu.cn/showproblem.php?pid=6964

题意

长度为 $n$ 的数组 $c$，$q$ 次询问。

求区间 $[l,r]$ 中 $c_i\oplus a\le b$ 的值不同的 $c_i$ $(l\le i\le r)$ 的个数。

$(1\le n,q\le 1e5,1\le c_i\le n,1\le l\le r\le n,a\le n+1,b\le n+1)$

思路

统计区间不同数的个数，可以离线询问用树状数组解决。

枚举右端点，树状数组维护前缀中不同数的个数，右端点每次移动，更新树状数组，使当前值上次出现的位置 $-1$，当前位置 $+1$。

而要满足 $c\oplus a\le b$，需按照下表在 Trie 上走。

a b c
0 0 0
0 1 1（取 0 必小，直接统计贡献）
1 0 1
1 1 0（取 1 必小，直接统计贡献）

对树状数组中每个点建立 Trie 即可。

代码

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
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const int N=1e5+5;
int n,a[N],cnt,tr[N*400][2],tot[N*400],pre[N],rt[N],res[N];
struct R {
    int l,a,b,id;;
    R() {}
    R(int l,int a,int b,int id):l(l),a(a),b(b),id(id) {}
};
vector<R> q[N];
void insert(int u,int d,int w) {
    for(int i=17;~i;i--) {
        int v=(d>>i)&1;
        if(!tr[u][v]) tr[u][v]=++cnt;
        u=tr[u][v];
        tot[u]+=w;
    }
}
void update(int x,int d,int w) {
    for(int i=x;i<=n;i+=i&-i) insert(rt[i],d,w);
}
int ask(int u,int a,int b) {
    int ret=0;
    for(int i=17;~i;i--) {
        int t1=(a>>i)&1,t2=(b>>i)&1;
        if(t1==0&&t2==0) u=tr[u][0];
        else if(t1==0&&t2==1) ret+=tot[tr[u][0]],u=tr[u][1];
        else if(t1==1&&t2==0) u=tr[u][1];
        else ret+=tot[tr[u][1]],u=tr[u][0];
        if(!u) break;
    }
    return ret+=tot[u];
}
int query(int l,int r,int a,int b) {
    int ret=0;
    for(int i=r;i;i-=i&-i) ret+=ask(rt[i],a,b);
    int t=ret;
    for(int i=l-1;i;i-=i&-i) ret-=ask(rt[i],a,b);
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) {
        q[i].clear();
        rt[i]=++cnt;
    }
    int m;cin>>m;
    for(int i=1;i<=m;i++) {
        int l,r,a,b;cin>>l>>r>>a>>b;
        q[r].EB(l,a,b,i);
    }
    for(int i=1;i<=n;i++) {
        if(pre[a[i]]) update(pre[a[i]],a[i],-1);
        update(i,a[i],1);
        pre[a[i]]=i;
        for(auto x:q[i]) res[x.id]=query(x.l,i,x.a,x.b);
    }
    for(int i=1;i<=m;i++) cout<<res[i]<<'\n';
    return 0;
}