[NOI Online 2021 提高组] 岛屿探险

遇到这种题目，就知道他是码农题目了。我们按照考场思路进行。
我们先观察部分分寻找思路。

$subtask567$:满足 $max{d_i}≤min{b_i}$
那么这个部分分怎么弄呢？
观察到这个时候我们只需要处理区间 $a_i \ xor c\ <\ d$ 即可。
具体来说我们对这部分建一棵可持久化 $Trie$ ，
插入的时候我们把所有的 $b_i$ 丢进可持久化 $Trie$ 里面去，
针对区间查询的时候我们直接查询 $d$ ，让他在 $Trie$ 上行进。
具体来说，对于我们扫到 $Trie$ 上的第 $i$ 位（ $2^i$），此时，记我们走到 $Trie$ 上是 $c(0/1)$ ，对应的的查询 $d(0/1)$
若我们查询时 $d=1$ 那么这时我们可以异或一个为这一位 $c$ 的数字肯定不会超过 $d$ ，那么 $ans+=cnt[c]$ ，我们走到 $son[c\ xor\ 1]$ 之后继续下一层。
若我们查询时 $d=0$ 那么我们一定只能异或出 这一位为 $1$ 的状态，要不就比 $d$ 大了。所以我们直接跳到 $son[c]$

$subtask8,9,10,11$ 满足$max{b_i}≤min{d_i}$
这个时候我们直接把 $a,b$ 这个二元组插入到 $Trie$ 里面去。
具体来说，我们在走 $a$ 的时候，如果此时 $b$ 的这一位 $=1$ 那么说明查询 $c$ 的时候可以直接把这一位异或成 $1$ ，于是直接 $++cnt[a^1]$ ，否则我们只能让这一位异或为 $0$ ，具体不详细阐述，推一推就出来了。统计答案就直接查询 $d$ 把路径上的 $cnt$ 都加起来就可以了。

考虑如何把这两种情况合为一体。
如果你使用分块会又 $TLE$ 又 $RE$ 的
观察到我们区分这两种贡献答案的方式就是试图满足 $d$ 和 $b$ 的大小关系。
也就是说这是第一层偏序关系。
我们如果把一条询问拆成前缀询问相减的形式的时候，这是第二层偏序 $pos_i<pos_j$ 此时 $i$ 才能对 $j$ 做出贡献。

于是问题转化为一个经典的二维偏序问题。

我们考虑如何分配两层偏序便于统计。

如果我们把 $b,d$ 的大小关系分配在 $CDQ$ 的左右区间，会发现这样子我们的 $Trie$ 树会被迫变成可持久化 $Trie$ 这显然不够优秀。
于是我们考虑把 $pos$ 的偏序放在第一层，内部分治处理 $b,d$ 的偏序关系。

如果左区间 $pos=i$ 的位置我们有一个插入操作（就是初始每个位置的值 $a,b$），右区间发现一个询问操作，

那么 $l$~$i$ 的所有插入都能对右侧的该询问产生 $b<=d$ 类的贡献，反之， $i+1$~$r$ 的所有插入都能对右侧该询问产生 $b>d$ 类的贡献。
不建议你抄因为常数太大了

Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#define cerr cout
using namespace std;
const int N=4e5+5,M=24;
inline int getint()
{
    char c;int f=0;
    while(c=getchar(),c>'9' || c<'0');
    while(f=(f<<1)+(f<<3)+c-'0',c=getchar(),c>='0' && c<='9');
    return f;
}
int n,Q,m;
int A[N],B[N];
int ans[N];
struct Ques{
    int pos,a,b,id,ty;
    bool type;
}q[N+N+N];
struct TRIE1{
    struct Trie{
        int son[2],cnt;
    }t[N*2*26];
    int Root,tot;

    inline void Clear()
    {
        Root=1;
        for(register int i=1;i<=tot;++i) t[i].son[0]=t[i].son[1]=t[i].cnt=0;
        return tot=1,void();
    }
    inline void Insert(int a,int b)
    {
        int p=Root;
        for(register int i=M;i>=0;--i){
            if(!t[p].son[0]) t[p].son[0]=++tot;
            if(!t[p].son[1]) t[p].son[1]=++tot;
            int c=(a&(1<<i))>>i;
            int d=(b&(1<<i))>>i;
            if(c && d) ++t[t[p].son[1]].cnt,p=t[p].son[0];
            if(!c && d) ++t[t[p].son[0]].cnt,p=t[p].son[1];
            if(c && !d) p=t[p].son[1];
            if(!c && !d) p=t[p].son[0];
        }
        ++t[p].cnt;
        return ;
    }
    inline int Ask(int val)
    {
        int ans=0;
        int p=Root;
        for(register int i=M;i>=0;--i){
            int c=(val&(1<<i))>>i;
            p=t[p].son[c];
            if(!p) break;
            ans+=t[p].cnt;
        }
        return ans;
    }
}T1;
struct TRIE2{
    struct Trie{
        int son[2],cnt;
    }t[N*2*26];
    int Root,tot;

    inline void Clear()
    {
        Root=1;
        for(register int i=1;i<=tot;++i)
            t[i].son[0]=t[i].son[1]=t[i].cnt=0;
        return tot=1,void();
    }
    inline void Insert(int a,int rev)
    {
        int p=Root;
        for(register int i=M;i>=0;--i){
            int c=(a&(1<<i))>>i;
            if(!t[p].son[c]) t[p].son[c]=++tot;
            (rev==1?++t[p].cnt:--t[p].cnt);
            p=t[p].son[c];
        }
        (rev==1?++t[p].cnt:--t[p].cnt);
        return ;
    }
    inline int Ask(int val,int D)
    {
        int ans=0,p=1;
        for(register int i=M;i>=0;--i){
            int c=(val&(1<<i))>>i;
            int d=(D&(1<<i))>>i;
            if(!p) break;
            if(c && d) ans+=t[t[p].son[1]].cnt,p=t[p].son[0];
            if(!c && d) ans+=t[t[p].son[0]].cnt,p=t[p].son[1];
            if(c && !d) p=t[p].son[1];
            if(!c && !d) p=t[p].son[0];
        }
        ans+=t[p].cnt;
        return ans;
    }
}T2;

inline bool cmp_pos(Ques a,Ques b) {return a.pos<b.pos || a.pos==b.pos && a.type<b.type;}
inline bool cmp(Ques a,Ques b) {return a.b<b.b;}

inline void Merge_sort(int left,int mid,int right)
{
    int l=left,r=mid+1;
    static Ques t[N+N+N];
    int top=0;
    while(l<=mid && r<=right){
        if(q[l].b<q[r].b) t[++top]=q[l],++l;
        else t[++top]=q[r],++r;
    }
    while(l<=mid) t[++top]=q[l],++l;
    while(r<=right) t[++top]=q[r],++r;
    for(register int i=left;i<=right;++i) q[i]=t[i-left+1];
    return ;
}
inline void Merge(int l,int r)
{
    if(l==r) return ;
    int mid=l+r>>1;
    Merge(l,mid);
    Merge(mid+1,r);
//  sort(q+l,q+mid+1,cmp);
//  sort(q+mid+1,q+r+1,cmp);
    T1.Clear(),T2.Clear();
    for(register int i=l;i<=mid;++i)
        if(q[i].type==0)
            T2.Insert(q[i].a,1);
    int i=l,j=mid+1;
    int last=l;
    bool left_q=0,right_q=0;
    for(register int i=l;i<=mid;++i) if(q[i].type==0) {left_q=1;break;}
    for(register int i=mid+1;i<=r;++i) if(q[i].type==1) {right_q=1;break;}
    if(!(left_q && right_q)) return Merge_sort(l,mid,r);
    for(;j<=r;++j){
        while(q[i].b<=q[j].b && i<=mid){
            if(!q[i].type)
                T2.Insert(q[i].a,-1),T1.Insert(q[i].a,q[i].b);
            ++i;
        }
        if(q[j].type==1){
            (q[j].ty==1?ans[q[j].id]+=T1.Ask(q[j].a)+T2.Ask(q[j].a,q[j].b)
            :
            ans[q[j].id]-=T1.Ask(q[j].a)+T2.Ask(q[j].a,q[j].b));
        }
    }
    Merge_sort(l,mid,r);

    return ;
}
int main()
{
    n=getint(),Q=getint();
    for(register int i=1;i<=n;++i) A[i]=getint(),B[i]=getint();
    for(register int i=1;i<=n;++i){
        ++m;
        q[m].a=A[i],q[m].b=B[i],q[m].type=0,q[m].pos=i;
    }
    for(register int i=1,l,r,c,d;i<=Q;++i){
        l=getint(),r=getint(),c=getint(),d=getint();
        ++m;
        q[m].pos=r,q[m].a=c,q[m].b=d,q[m].id=i;
        q[m].type=1;q[m].ty=1;
        ++m;
        q[m].pos=l-1,q[m].a=c,q[m].b=d,q[m].id=i;
        q[m].type=1;q[m].ty=-1;
    }
    sort(q+1,q+1+m,cmp_pos);
    Merge(1,m);
    for(register int i=1;i<=Q;++i)
        printf("%d\n",ans[i]);
    return 0;
}