P7470 [NOI Online 2021 提高组] 岛屿探险
FxorG
2021-07-30 22:19:15
**不一定正确！提供一个三合一才能过的分块**
$$ a_i \ xor\ c_j \le min(b_i,d_j)$$
$$ a_i \ xor \ c_j \le b_i$$
$$ a_i \ xor \ c_j \le d_j$$
$$a_i \ xor \ c_j \le d_j$$
可以考虑 $c_j,d_j=0$ 那么 $a_i=0$。
$c_j=1,dj=0,ai=1$。
$c_j=0,d_j=1,a_i=1/0$ 如果选 $1$ 的话就接着跳， $0$ 就加上左子树的所有的元素个数。
$c_j=1,d_j=1,a_i=1/0$ $0$ 接着跳，加上 $1$ 那边子树的元素个数。
然后，区间就可持久化 01-trie。
$$ a_i \ xor \ c_j \le b_i$$
$$ c_j \ xor \ a_i \le b_i$$
$b_i,a_i$ 作为询问 就一样跳 然后整个子树可以就加计数器 一个询问符合的 $c_j$ 就是 $c_j$ 到根的路径计数器和。
可以可持久化，对于每一个 $c_j$ 去拆 $[1,r]-[1,l-1]$ 就是答案。
我们需要保证查询的时候 $a_i,b_i$ 都已经刚刚好更新完毕了，这个将 $a_i,b_i$ 的加计数器也认为操作，右端点是 $i$，然后按右端点排序就可以。
**先修改后询问！**
那么，如何分离出 $[L,x],[x+1,R]$ 使得 $[L,x]$ 是 $min\{b_i\}\ge d,i\in[L,x]$?
实际上直接分块就好了，块内从小到大排序，并且我们可以将询问离线按 $d$ 排，这样每次块内 $x$ 不降，可以双指针优化。
算下复杂度，令 $T$ 为块长。
$O(\dfrac{n}{T}T\log T+mT+\dfrac{n}{T}m\log(\dfrac{n}{T}m)+\dfrac{n}{T}m\log w)$
第一个为预处理块的复杂度，第二个为在线处理 $d\le b$ 的复杂度，第三个为离线完操作+排序的复杂度，因为有 $\dfrac{n}{T}$ 个块，假如每次每个块都被覆盖到，那么会有 $m$ 次。最后一个是处理这些操作的复杂度。
**关于块长**，我们发现瓶颈是 $\dfrac{n}{T}m\log(\dfrac{n}{T}m)$，所以我们让 $T$ 尽可能大，实测在 $1750$ 最优。
[评测记录](https://www.luogu.com.cn/record/54653671)
$\text{Code}$
```cpp
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#define ll long long
using namespace std;
int rd() {
int f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
ll lrd() {
ll f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
void pr(int x) {
if(x<0) {putchar('-');x=-x;}
if(x>9) pr(x/10);
putchar(x%10+'0');
}
void lpr(ll x) {
if(x<0) {putchar('-');x=-x;}
if(x>9) pr(x/10);
putchar(x%10+'0');
}
/*
有区间之后枚举块
之前将所有c加入trie
考虑块排序后的区间所对应的 这个可以在分块build的时候处理出来
*/
#define N (int)(1e5+2)
#define M 80
#define il inline
int ans[N],son[2][N*30],sum[N*30];
int cnt[N],rid[N],a[N],b[N],C[N],L[M],R[M],id[N];
int n,m,bl,tot=1;
struct ques {
int l,r,uid,yx;
}q[N*M]; int qtot=0;
struct node {
int x,y;
}tmp[1752];
int B[M][1752],rt[N],rttot;
bool cmp(node x,node y) {
return x.x<y.x;
}
il void ins(int x) {
int pre=rt[rttot]; rt[++rttot]=++tot;
for(int i=24;i>=0;i--) {
int c=(x>>i)&1;
sum[tot]=sum[pre]+1;
son[c^1][tot]=son[c^1][pre];
son[c][tot]=tot+1; ++tot;
pre=son[c][pre];
}
sum[tot]=sum[pre]+1;
}
il int query(int l,int r,int c,int d) {
l=rt[l-1]; r=rt[r];
int res=0;
for(int i=24;i>=0;i--) {
int r1=(c>>i)&1,r2=(d>>i)&1;
if(r2) res+=sum[son[r1][r]]-sum[son[r1][l]];
if(!r1&&!r2) l=son[0][l],r=son[0][r];
if(r1&&!r2) l=son[1][l],r=son[1][r];
if(!r1&&r2) l=son[1][l],r=son[1][r];
if(r1&&r2) l=son[0][l],r=son[0][r];
}
res+=sum[r]-sum[l];
return res;
}
il void build(int x) {
for(int i=L[x];i<=R[x];++i) {
tmp[i-L[x]+1].x=b[i]; tmp[i-L[x]+1].y=i;
}
sort(tmp+1,tmp+1+R[x]-L[x]+1,cmp);
for(int i=1;i<=R[x]-L[x]+1;++i) {
B[x][i]=tmp[i].x; rid[L[x]+i-1]=tmp[i].y;
}
cnt[x]=L[x];
}
il void update(int l,int r,int c,int d,int uid) {
if(id[l]==id[r]) {
for(int i=l;i<=r;++i) ans[uid]+=((a[i]^c)<=min(b[i],d));
} else {
for(int i=l;i<=R[id[l]];++i) ans[uid]+=((a[i]^c)<=min(b[i],d));
for(int i=L[id[r]];i<=r;++i) ans[uid]+=((a[i]^c)<=min(b[i],d));
for(int i=id[l]+1;i<id[r];++i) {
while(cnt[i]<R[i]&&B[i][cnt[i]-L[i]+1]<=d) ++cnt[i];
if(B[i][cnt[i]-L[i]+1]<d) {
q[++qtot]=ques{1,L[i]-1,uid,2}; q[++qtot]=ques{1,R[i],uid,3};
} else { //L[i]~cnt[i]-1 cnt[i]-R[i]
if(L[i]<=cnt[i]-1) q[++qtot]=ques{1,L[i]-1,uid,2},q[++qtot]=ques{1,cnt[i]-1,uid,3};
ans[uid]+=query(cnt[i],R[i],c,d);
}
}
}
}
bool cmp2(ques x,ques y) {
return x.r==y.r?x.yx<y.yx:x.r<y.r;
}
il void insC(int x) {
int p=1;
for(int i=24;i>=0;i--) {
int c=(x>>i)&1;
if(!son[c][p]) son[c][p]=++tot;
p=son[c][p];
}
}
il void solve(int x,int y) {
int p=1;
for(int i=24;i>=0;i--) {
int r1=(x>>i)&1,r2=(y>>i)&1;
if(r2) sum[son[r1][p]]++;
if(r1&&r2) p=son[0][p];
if(!r1&&r2) p=son[1][p];
if(!r1&&!r2) p=son[0][p];
if(r1&&!r2) p=son[1][p];
}
++sum[p];
}
il int query(int x) {
int res=0,p=1;
for(int i=24;i>=0;i--) {
int c=(x>>i)&1;
res+=sum[p]; p=son[c][p];
}
res+=sum[p];
return res;
}
struct ask{
int l,r,c,d,id;
}A[N];
il bool cmp3(ask x,ask y) {
return x.d<y.d;
}
int st[20][N];
il int st_qry(int l,int r) {
int qwq=log2(r-l+1);
return max(st[qwq][l],st[qwq][r-(1<<qwq)+1]);
}
il void solve1() {
for(int i=1;i<=m;++i) {
q[++qtot]=ques{1,A[i].l-1,i,2}; q[++qtot]=ques{1,A[i].r,i,3};
}
for(int i=1;i<=n;++i) q[++qtot]=ques{0,i,i,1};
sort(q+1,q+1+qtot,cmp2);
for(int i=1;i<=m;++i) insC(C[i]);
for(int i=1;i<=qtot;++i) {
if(q[i].yx==1) {
solve(a[q[i].uid],b[q[i].uid]);
} else if(q[i].yx==2) {
ans[q[i].uid]-=query(C[q[i].uid]);
} else {
ans[q[i].uid]+=query(C[q[i].uid]);
}
}
for(int i=1;i<=m;++i) pr(ans[i]),puts("");
}
namespace solve2 {
struct node {
int x,id;
}T[N];
bool cmp(node x,node y) {
return x.x<y.x;
} int tmp[N];
void sol() {
for(int i=1;i<=n;i++) T[i].x=b[i],T[i].id=i;
sort(T+1,T+1+n,cmp);for(int i=1;i<=n;i++) tmp[i]=b[i]; sort(tmp+1,tmp+1+n);
for(int i=1;i<=n;i++) ins(a[T[i].id]);
for(int i=1;i<=m;i++) {
int qwq=upper_bound(tmp+1,tmp+1+n,A[i].d)-tmp-1;
if(qwq) q[++qtot]=ques{1,qwq,i,1};
if(qwq+1<=n) ans[A[i].id]+=query(qwq+1,n,A[i].c,A[i].d);
}
for(int i=1;i<=tot;i++) sum[i]=son[0][i]=son[1][i]=0; tot=1;
for(int i=1;i<=m;i++) insC(C[i]);
for(int i=1;i<=n;i++) q[++qtot]=ques{1,i,T[i].id,0};
sort(q+1,q+1+qtot,cmp2);
for(int i=1;i<=qtot;i++) {
if(q[i].yx==0) solve(a[q[i].uid],b[q[i].uid]);
else ans[q[i].uid]+=query(C[q[i].uid]);
}
for(int i=1;i<=m;i++) pr(ans[i]),puts("");
}
}
int main() {
n=rd(); m=rd(); bl=1750;
for(int i=1;i<=n;++i) a[i]=rd(),b[i]=rd();
for(int i=1;i<=n;++i) st[0][i]=b[i];
for(int i=1;i<=18;++i)
for(int j=1;j+(1<<i)-1<=n;j++)
st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
bool fl=1,fl2=1;
for(int i=1;i<=m;++i) {
A[i].l=rd(); A[i].r=rd(); A[i].c=C[i]=rd(); A[i].d=rd(); A[i].id=i;
if(A[i].d<st_qry(A[i].l,A[i].r)) fl=0;
if(A[i].l!=1||A[i].r!=n) fl2=0;
}
if(fl) {
solve1(); return 0;
}
if(fl2) {
solve2::sol(); return 0;
}
for(int i=1;i<=n;++i) id[i]=(i-1)/bl+1;
for(int i=1;i<=id[n];++i) L[i]=(i-1)*bl+1,R[i]=i*bl; R[id[n]]=n;
for(int i=1;i<=id[n];++i) build(i);
for(int i=1;i<=n;++i) ins(a[rid[i]]);
sort(A+1,A+1+m,cmp3);
for(int i=1;i<=m;++i) update(A[i].l,A[i].r,A[i].c,A[i].d,A[i].id);
for(int i=1;i<=n;++i) q[++qtot]=ques{rid[i],i,0,1};
sort(q+1,q+1+qtot,cmp2);
for(int i=1;i<=tot;i++) sum[i]=0,son[0][i]=son[1][i]=0; tot=1;
for(int i=1;i<=m;++i) insC(C[i]);
for(int i=1;i<=qtot;++i) {
if(q[i].yx==1) {
solve(a[q[i].l],b[q[i].l]);
} else if(q[i].yx==2) {
ans[q[i].uid]-=query(C[q[i].uid]);
} else {
ans[q[i].uid]+=query(C[q[i].uid]);
}
}
for(int i=1;i<=m;++i) pr(ans[i]),puts("");
return 0;
}
```