先不管那个+d,我们来考虑正常的可持久化字典树.总的思想就是贪心:用一个主席树模仿字典树,我发现当线段树总区间是2^n-1时每个小区间内部的01分布就与深度有关.比如左半边这一位都是0右边都是1这个样子.这样就可以O(1)地判断某个区间内有没有数,因为是一整个的区间,又因为向下到达根节点需要logn,总的复杂度为m*logn.
int i,k,tx,ty; int n,m,a[10000],o[10000],c[1000],sum; int tot,rt[1000],lc[1000],rc[1000]; void build(int &now,int l,int r){ tot++; now=tot; if(l==r) return; int mid=(l+r)>>1; build(lc[now],l,mid); build(rc[now],mid+1,r); return ; } int built(int now,int l,int r){ tot++; int t=tot; lc[t]=lc[now];rc[t]=rc[now];c[t]=c[now]+1; if(l==r) return t; int mid=(l+r)>>1; if(k<=mid)lc[t]=built(lc[t],l,mid); else rc[t]=built(rc[t],mid+1,r); return t; } int ask(int x,int y,int l,int r){ if(l==r) return l; int mid=(l+r)>>1; if((l^k)>(r^k)) if(c[lc[y]]-c[lc[x]]) return ask(lc[x],lc[y],l,mid); else return ask(rc[x],rc[y],mid+1,r); else if((c[rc[y]]-c[rc[x]])) return ask(rc[x],rc[y],mid+1,r); else return ask(lc[x],lc[y],l,mid); } int main(){ n=read();m=read(); for(i=1;i<=n;i++) a[i]=o[i]=read(),sum=max(sum,a[i]); sum=1<<int(log2(sum*1.0)+1); sum--; build(rt[0],0,sum); for(i=1;i<=n;i++){ k=o[i]; rt[i]=built(rt[i-1],0,sum); } for(i=1;i<=m;i++){ tx=read();ty=read();k=read(); cout<<(k^ask(rt[tx-1],rt[ty],0,sum))<<endl; } return 0; }
然后考虑偏移.这个复杂度要变成m*log2n了.这主要是由于偏移后由判断一整个区间[x,y]变成了判断区间[x-d,y-d]内是否有数,这个过程需要我们向下寻找了,每次最坏要向下查logn次,总的复杂度就要再乘上logn.
代码还是不难写的,只需要把上面的if内的判断改成一个函数就行.
using namespace std; int i,k,tx,ty,d; int n,m,a[10000],o[10000],c[1000],sum; int tot,rt[1000],lc[1000],rc[1000]; void build(int &now,int l,int r){ tot++; now=tot; if(l==r) return; int mid=(l+r)>>1; build(lc[now],l,mid); build(rc[now],mid+1,r); return ; } int built(int now,int l,int r){ tot++; int t=tot; lc[t]=lc[now];rc[t]=rc[now];c[t]=c[now]+1; if(l==r) return t; int mid=(l+r)>>1; if(k<=mid)lc[t]=built(lc[t],l,mid); else rc[t]=built(rc[t],mid+1,r); return t; } bool check(int x,int y,int tl,int tr,int l,int r) { if(l==r||(tl<=l&&r<=tr)) return c[y]-c[x]; int mid=(l+r)>>1; return (tl<=mid&&check(lc[x],lc[y],tl,tr,l,mid)||(tr>mid&&check(rc[x],rc[y],tl,tr,mid+1,r)));//运用短路的性质减少代码与时间 } int ask(int x,int y,int l,int r){ if(l==r) return l; int mid=(l+r)>>1; if((l^k)>(r^k)) //if(c[lc[y]]-c[lc[x]]) if(check(rt[tx-1],rt[ty],max(l-d,0),max(mid-d,0),0,sum) ) return ask(lc[x],lc[y],l,mid); else return ask(rc[x],rc[y],mid+1,r); else //if((c[rc[y]]-c[rc[x]])) if(check(rt[tx-1],rt[ty],max(mid+1-d,0),max(r-d,0),0,sum)) return ask(rc[x],rc[y],mid+1,r); else return ask(lc[x],lc[y],l,mid); } int main(){ n=read();m=read(); for(i=1;i<=n;i++) a[i]=o[i]=read(),sum=max(sum,a[i]); sum=1<<int(log2(sum*1.0)+1); sum=sum<<1; sum--; //cout<<sum<<endl; build(rt[0],0,sum); for(i=1;i<=n;i++){ k=o[i]; rt[i]=built(rt[i-1],0,sum); } for(i=1;i<=m;i++){ tx=read();ty=read();k=read();d=read(); cout<<(k^(ask(rt[tx-1],rt[ty],0,sum)))<<endl; } return 0; }