题解 【P5065 [Ynoi2014] 不归之人与望眼欲穿的人们】

本题的复杂度（相较于题面中给出的）更优的做法！ **题意** ： 维护长为 $n$ 的序列 $A$。支持 ： - 单点修改。 - 询问满足区间 or 和大于等于一个数的区间的最短可能长度，或指出无解。 $n,m\leq 5\times 10^4,A\leq 2^{30}$ ，时限$\texttt{1s}$。 ------------ 相关题目 ： [P3794 签到题IV](https://www.luogu.com.cn/problem/P3794) - ## 分块 ： $O(n\sqrt{n}w)$ 记块长为 $B$。 先考虑如何求解静态全局询问。 对于一个右端点，左端点对应的本质不同 or 值只有 $O(w)$ 个，于是容易双指针 $O(Bw)$ 计算。 对于每个块，记录每个长度的最大 or 和，前后缀本质不同 or 和。 查询时，对两边的散块内部可以单独跑一次，将其合成整块。 考虑答案区间在块内的情况，大力枚举每个块，若当前答案能减小则不断减小，复杂度为 $O(B+n/B)$。 考虑答案区间跨过两块的情况，枚举右端点所在的块，维护该块之前左端点的本质不同 or 和。 每经过一个块，将之前的左端点 or 上这个块，再加入这个块内部的后缀，然后去重。 在每个分界线处，双指针求出答案。复杂度为 $O(nw/B)$。 令 $B=O(\sqrt{n})$ 即可做到 $O(n\sqrt{n}w)$。 - ## 线段树 ：$O(w^2\log^2n)$ 用线段树维护序列 $A$ ，对于每个线段树节点，维护本质不同的前缀 or 和与后缀 or 和。 每次修改后，在每个受到影响的节点处暴力计算跨越分界线 $mid$ 的区间的 or 和。这些区间有 $O(w^2)$ 个。 对于每个长度，用堆来维护最大值。将这些最大值再用线段树维护，查询时只需线段树上二分。 修改的复杂度为 $O(w^2\log^2n)$ ，查询的复杂度为 $O(\log n)$。 - ## 拼在一起？：$O(n\sqrt{nw}+nw^2\log n)$ 用线段树维护每个块，每个线段树节点维护区间内长为 $1\sim len$ 的最大区间 or 和。 合并时，考虑两个儿子的贡献，以及跨越中点的 $O(w^2)$ 个区间的贡献。 若块大小为 $B$ ，这个复杂度是 $O(w^2\log B+B+B/2+B/4)=O(w^2\log B+B)$。 我们令 $B=\sqrt{nw}$ 即可做到 $O(n\sqrt{nw}+nw^2\log n)$。 卡常 ： 在区间长度较小时跑暴力，这样可以同时减小时空常数。 （未使用其他剪枝） 目前最优解，最慢点 `320ms`。 代码挺好写的。 ```cpp #include<algorithm> #include<cstring> #include<cstdio> #define Pr pair<int,int> #define fir first #define sec second #define mp make_pair #define MaxN 50500 using namespace std; struct Data{Pr p[32];int tn,s;}; inline void add(Data &A,const Data &B){ for (int i=1;i<=B.tn;i++) if ((B.p[i].fir|A.s)!=A.p[A.tn].fir) A.p[++A.tn]=mp(B.p[i].fir|A.s,B.p[i].sec); A.s|=B.s; } const int BS=800,BS2=32; struct Node{int *x,len;Data l,r;}a[(MaxN/BS2)<<2]; inline void up(int u) { int l=u<<1,r=u<<1|1; a[u].l=a[l].l;add(a[u].l,a[r].l); a[u].r=a[r].r;add(a[u].r,a[l].r); memcpy(a[u].x+1,a[l].x+1,sizeof(int)*a[l].len); memset(a[u].x+a[l].len+1,0,sizeof(int)*(a[u].len-a[l].len)); for (int i=1;i<=a[r].len;i++)a[u].x[i]=max(a[u].x[i],a[r].x[i]); for (int i=1;i<=a[l].r.tn;i++) for (int j=1;j<=a[r].l.tn;j++){ int len=a[r].l.p[j].sec-a[l].r.p[i].sec+1 ,s=a[r].l.p[j].fir|a[l].r.p[i].fir; a[u].x[len]=max(a[u].x[len],s); } for (int i=2;i<=a[u].len;i++) a[u].x[i]=max(a[u].x[i],a[u].x[i-1]); } int n,x[MaxN],_buf[MaxN<<4],*tbuf=_buf; void build2(int l,int r,Node &A) { memset(A.x+1,0,sizeof(int)*A.len); for (int i=l;i<=r;i++) for (int j=i,s=0;j<=r;j++) A.x[j-i+1]=max(A.x[j-i+1],s|=x[j]); for (int i=2;i<=A.len;i++) A.x[i]=max(A.x[i],A.x[i-1]); A.l.tn=A.r.tn=0; for (int i=l,s=0;i<=r;i++) if (i==l||(s|x[i])!=s){ s|=x[i]; A.l.p[++A.l.tn]=mp(s,i); } for (int i=r,s=0;i>=l;i--) if (i==r||(s|x[i])!=s){ s|=x[i]; A.r.p[++A.r.tn]=mp(s,i); } A.l.s=A.r.s=A.r.p[A.r.tn].fir; } void build(int l=1,int r=n,int u=1) { a[u].len=r-l+1; if (a[u].len<=BS){a[u].x=tbuf;tbuf+=a[u].len;} if (a[u].len<=BS2){build2(l,r,a[u]);return ;} int mid=(l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); if (a[u].len<=BS)up(u); } int to; void upd(int l=1,int r=n,int u=1) { if (a[u].len<=BS2){build2(l,r,a[u]);return ;} int mid=(l+r)>>1; if (to<=mid)upd(l,mid,u<<1); else upd(mid+1,r,u<<1|1); if (a[u].len<=BS)up(u); } int st[505],tot,wfc,ret; void qry(int l=1,int r=n,int u=1) { if (a[u].len<=BS){ if (ret>a[u].len&&a[u].x[a[u].len]>=wfc)ret=a[u].len; if (ret<=a[u].len)while(ret>1&&a[u].x[ret-1]>=wfc)ret--; st[++tot]=u; return ; }int mid=(l+r)>>1; qry(l,mid,u<<1);qry(mid+1,r,u<<1|1); } int calc(Data &L,Data &R,int lim) { int ret=n+1; for (int i=1,p=R.tn+1;i<=L.tn;i++){ while(p>1&&(R.p[p-1].fir|L.p[i].fir)>=lim)p--; if (p<=R.tn)ret=min(ret,R.p[p].sec-L.p[i].sec+1); }return ret; } int m; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++)scanf("%d",&x[i]); build(); for (int i=1,op;i<=m;i++){ scanf("%d",&op); if (op==1){ scanf("%d",&to); scanf("%d",&x[to]);upd(); } else { scanf("%d",&wfc); tot=0;ret=n+1;qry(); Data tr[2];bool flag=0; tr[0]=a[st[1]].r; for (int i=2;i<=tot;i++){ ret=min(ret,calc(tr[flag],a[st[i]].l,wfc)); add(tr[!flag]=a[st[i]].r,tr[flag]); flag^=1; }printf("%d\n",ret==n+1 ? -1 : ret); } }return 0; } ```