Magus @ 2025-01-10 20:10:31
PS:样例过了
所以目测是外层 query 炸了，但是没找到错误。
```
// Problem:P5065 [Ynoi2014] 不归之人与望眼欲穿的人们
// Contest:Luogu
// URL:https://www.luogu.com.cn/problem/P5065
// Memory Limit:125 MB
// Time Limit:1000 ms
// Luogu Account:qhzx_FeS2_Butterfly
// Codeforces Account:Butterfly_qwq
// Atcoder Account:Super_agg
// CP Duel Rating:2007
// Start Coding:01-10 15:53
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N=50004,B=224;
int n,m,blk[N],pos[N];
struct qu
{
int sz,dat[35];
inline int& operator [](const int& x){return dat[x];}
}ans[230];
void insert(qu u,int w,qu& t,int pos)
{
t.sz=0;
for(int i=0;i<31;i++)if(w&(1<<i))t[++t.sz]=(pos<<5)|i;
for(int i=1;i<=u.sz;i++)if((~w)&(1<<(u[i]&31)))t[++t.sz]=u[i];
}
void merge(qu u,qu v,int w,qu& t)
{
t.sz=0;
for(int i=1;i<=u.sz;i++)if(w&(1<<(u[i]&31)))t[++t.sz]=u[i];
for(int i=1;i<=v.sz;i++)if((~w)&(1<<(v[i]&31)))t[++t.sz]=v[i];
}
struct block
{
int sz,val,lst,a[230],mx[230];qu pre[230],suf[230];
inline int& operator [](const int& x){return a[x];}
void getmax()
{
memset(mx,0xc0,sizeof(mx));
for(int i=1;i<=sz;i++)for(int j=1,r=0,u;j<=pre[i].sz;j++)
{
r|=(1<<(pre[i][j]&31));
u=i-(pre[i][j]>>5)+lst+1;
mx[u]=max(mx[u],r);
}
for(int i=1;i<=sz;i++)mx[i]=max(mx[i],mx[i-1]);
}
void build()
{
for(int i=1;i<=sz;i++)val|=a[i];
for(int i=1;i<=sz;i++)insert(pre[i-1],a[i],pre[i],lst+i);
for(int i=sz;i;i--)insert(suf[i+1],a[i],suf[i],lst+i);
getmax();
}
void update(int u,int w)
{
int inc=a[u]^w,r=0;a[u]=w;val=0;
for(int i=1;i<=sz;i++)val|=a[i];
insert(pre[u-1],a[u],pre[u],lst+u);
for(int i=u+1;i<=sz;i++)
{
insert(pre[i-1],a[i],pre[i],lst+i);
r|=a[i];if(r==(r|inc))break;
}
getmax();r=0;
insert(suf[u+1],a[u],suf[u],lst+u);
for(int i=u-1;i;i--)
{
insert(suf[i+1],a[i],suf[i],lst+i);
r|=a[i];if(r==(r|inc))break;
}
}
int query(int k,int R)
{
int l=1,r=min(sz+1,R),mid;
while(l<r)
{
mid=l+r>>1;
if(mx[mid]>=k)r=mid;
else l=mid+1;
}
if(l==sz+1)return 0x3f3f3f3f;
return l;
}
}bl[230];
void init()
{
for(int i=1;i<=n;i++){blk[i]=(i-1)/B+1;pos[i]=(i-1)%B+1;}
for(int i=1;i<blk[n];i++)bl[i].sz=B;bl[blk[n]].sz=pos[n];
for(int i=n;i;i--)bl[blk[i]].lst=i-1;
}
void update(int u,int w)
{
bl[blk[u]].update(pos[u],w);
for(int i=blk[u];i;i--)merge(bl[i].suf[1],ans[i+1],bl[i].val,ans[i]);
}
int query(int k)
{
int res=0x3f3f3f3f;qu q;
for(int i=1;i<=blk[n];i++)res=min(res,bl[i].query(k,res));
for(int i=blk[n],w,tmp;i>=2;i--)
{
w=bl[i-1].val;q=bl[i-1].pre[bl[i-1].sz];
for(int j=1,k=q.sz,r=0;j<=ans[i].sz;j++)
{
if((ans[i][j]>>5)-bl[i].lst>=res)break;
r|=(1<<(ans[i][j]&31));if((r|w)<k)continue;
while(k!=1)
{
tmp=w&(~(1<<(q[k]&31)));
if((r|tmp)<k)break;k--;w=tmp;
}
res=min(res,(ans[i][j]>>5)-(q[k]>>5)+1);
if(k==1)break;
}
}
if(res==0x3f3f3f3f)return -1;
return res;
}
int main()
{
cin>>n>>m;init();
for(int i=1;i<=n;i++)cin>>bl[blk[i]][pos[i]];
for(int i=1;i<=blk[n];i++)bl[i].build();
for(int i=blk[n];i;i--)merge(bl[i].suf[1],ans[i+1],bl[i].val,ans[i]);
for(int i=1,op,k,x;i<=m;i++)
{
cin>>op>>k;
if(op==1){cin>>x;update(k,x);}
else cout<<query(k)<<'\n';
}
}
```