[hdu] P6964 I love counting

Tree array +trie Trees .

The title has two requirements ：
1. Find the kind number of a certain interval
2. On this basis, certain conditions must be met
If you take this problem apart , These two questions are easy to do . For question 1 , You can use a tree array offline , stay $O(nlogn)$ Get the answer in less time . For question 2 , Judge $a⨁b\le c$, It can be used 01trie The tree judges bit by bit . So for the combination of the two , Whether the type of a specific interval can be obtained from a data structure , You can also judge the XOR relation ？

The answer is yes , You can use a tree array +trie Trees .
Specifically, the tree array is created on each node 01trie Trees . Take the example , The completed data structure is shown in the figure below ：

Only established trie Trees are obviously not enough , because trie The tree can only let us know the set of binary digits in the range governed by the tree array node . So how to get from trie Get information about the number of numbers on the tree ？ Just record every number you add , The number of passes through the node . Here is an example ：
Then there is how to judge $a⨁b\le c$, Old ways , On the dictionary tree with c Compare bit by bit .

Let's talk about the details
1. On how to create a tree array on each node trie Trees .
At first I defined an array of structures , This is shown below ：

struct t
{
    
    int trie[maxn][2];
    int size[maxn];
    int cnt;
}tr[1000];

Although it is easy to understand , But will mle. The optimization method is similar to the chained forward star , To put $n$ individual trie The trees are in one trie on the tree . Specifically, use rt[] Represents the root node of the tree in the subscript .
2. About array size
Tree array has $n$ Nodes , On average, each node governs $logn$ Nodes , So there is $32nlogn$ Nodes , that trie The first dimension of the array must be opened 1e5*400.

Complete code ：

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn = 1e5+5;

using namespace std;

int cnt;
int trie[maxn*400][2];
int rt[maxn],size[maxn*400],ans[maxn];

struct que
{
    
    int l,r;
    int a,b;
    int id;
}q[maxn];

bool cmp(que x, que y) {
     return x.r<y.r; }

int n,m;
int a[maxn],have[maxn];

void insert(int &pos, int num, int val)
{
    
    if (!pos) pos=++cnt;
    int now=pos;
     for (int j=16; j>=0; j--)
    {
    
        int bit=(num>>j)&1;
		if (!trie[now][bit]) trie[now][bit]=++cnt;
		now=trie[now][bit];
		size[now]+=val;
     }
}

ll query(int pos, int a, int b)
{
    
    if (!pos) return 0;
    int now=pos;
    ll ans=0;
    for (int j=16; j>=0; j--)
    {
    
        int bt1=(b>>j)&1;
        int bt2=(a>>j)&1;
        if (bt1==0) now=trie[now][bt2];
        else if (bt1==1)
        {
    
            ans+=size[trie[now][bt2]];
            now=trie[now][bt2^1];
        }
        if (now==0) break;
    }
    return ans+size[now];
}

ll lowbit(ll x) {
     return (x&(-x)); }

void add(int pos, int num, int val)
{
    
    int x=pos;
    while(x<=n)
    {
    
        insert(rt[x],num,val);
        x+=lowbit(x);
    }
}

ll ask(int x, int a, int b)
{
    
    ll ans=0;
    while(x)
    {
    
        ans+=query(rt[x],a,b);
        x-=lowbit(x);
    }
    return ans;
}

int main()
{
    
       FAST; 
       cin>>n;
       for (int i=1; i<=n; i++) cin>>a[i];
       cin>>m;
       for (int i=1; i<=m; i++)
       {
    
        cin>>q[i].l>>q[i].r>>q[i].a>>q[i].b;    
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    
    int last=0;
    for (int i=1; i<=m; i++)
    {
    
        for (int j=last+1; j<=q[i].r; j++)    
        {
    
            if (have[a[j]]) add(have[a[j]],a[j],-1);
            add(j,a[j],1);
            have[a[j]]=j;
        }
        last=q[i].r;
        ans[q[i].id]=ask(q[i].r,q[i].a,q[i].b)-ask(q[i].l-1,q[i].a,q[i].b);
    } 
    
    for (int i=1; i<=m; i++) cout<<ans[i]<<endl;
    
return 0;
}