题解 【P5065 [Ynoi2014] 不归之人与望眼欲穿的人们】
command_block
2021-06-29 20:53:53
本题的复杂度(相较于题面中给出的)更优的做法!
**题意** : 维护长为 $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;
}
```