Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
27992 | masppy | 【BJ】T2 | C++ | 解答错误 | 0 | 1000 MS | 3268 KB | 3186 | 2024-03-31 19:10:13 |
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e5+10; const ll inf= 1e17+10; const ll mod=998244353; int n,m,len,cnt,ans=1000000; int a[maxn],q[maxn]; ll block[300][300],pre[300][300],bck[300][300],in[300][300]; bool check(int x,int num){ int tot,flag=0; for(int i=1;i<=cnt-x+1;i++){ tot=0; for(int j=i+1;j<i+x;j++){ tot|=bck[j][1]; } int tmp=0; tmp=tot|bck[i][1]|bck[i+x][1]; // cout<<tmp<<endl; if(tmp<num) continue; int rcnt=1,lcnt=len; while(rcnt<len&&pre[i+x][rcnt]>=0){ while((tot|bck[i][lcnt]|pre[i+x][rcnt])<num&&lcnt>1) lcnt--; // cout<<(tot|bck[i][lcnt]|pre[i+x][rcnt])<<endl; if((tot|bck[i][lcnt]|pre[i+x][rcnt])>=num) flag=1,ans=min(ans,len*(x-2)+len-lcnt+1+rcnt); rcnt++; } rcnt=1,lcnt=len; while(lcnt){ while((tot|bck[i][lcnt]|pre[i+x][rcnt])<num&&rcnt<len&&pre[i+x][rcnt+1]>=0) rcnt++; // cout<<num<<" "<<(tot|bck[i][lcnt]|pre[i+x][rcnt])<<" "<<len*(x-1)-lcnt+1+rcnt<<endl; if((tot|bck[i][lcnt]|pre[i+x][rcnt])>=num) flag=1,ans=min(ans,len*(x-1)-lcnt+1+rcnt); lcnt--; } } return flag; } void init(){ for(int i=1;i<=cnt;i++){ for(int j=1;j<=len&&block[i][j]>=0;j++){ pre[i][j]=pre[i][j-1]|block[i][j]; } for(int j=len;j>=1;j--){ if(block[i][j]<0) continue; bck[i][j]=bck[i][j+1]|block[i][j]; } for(int j=1;j<=len;j++){ ll tmp=0; for(int k=j;k<=len;k++){ if(block[i][k]<0) break; tmp|=block[i][k]; in[i][k-j+1]=max(in[i][k-j+1],tmp); } } } } int main(){ // freopen("test.in","r",stdin); //freopen("beaco.out","w",stdout); memset(pre,0,sizeof(pre)); memset(bck,0,sizeof(bck)); scanf("%d%d",&n,&m); len=sqrt(n); cnt=(n+len-1)/len; bool fg=0; int num=0; for(int i=1;i<=cnt;i++){ for(int j=1;j<=len;j++){ num++; scanf("%d",&block[i][j]); if(num==n){ for(int k=j+1;k<=len;k++) block[i][k]=-1; break; } } } init(); while(m--){ int opt; scanf("%d",&opt); if(opt==1){ int x,y; scanf("%d%d",&x,&y); block[(x+len-1)/len][x-((x+len-1)/len-1)*len]=y; for(int i=x-((x+len-1)/len-1)*len;i<=len&&block[(x+len-1)/len][i]>=0;i++){ pre[(x+len-1)/len][i]=pre[(x+len-1)/len][i-1]|block[(x+len-1)/len][i]; } for(int i=x-((x+len-1)/len-1)*len;i>=1;i--){ bck[(x+len-1)/len][i]=bck[(x+len-1)/len][i+1]|block[(x+len-1)/len][i]; } for(int i=1;i<=len;i++){ ll tmp=0; for(int j=i;j<=len;j++){ if(block[(x+len-1)/len][j]<0) break; tmp|=block[(x+len-1)/len][j]; in[(x+len-1)/len][j-i+1]=max(in[(x+len-1)/len][j-i+1],tmp); } } } else{ int x; scanf("%d",&x); // cout<<x<<endl; int num=1000000; for(int i=1;i<=cnt;i++){ for(int j=1;j<=len;j++){ if(in[i][j]>=x) num=max(num,j); } } if(num<1000000){ printf("%d\n",num); continue; } int l=2,r=cnt; //ans=-1; while(l<=r){ int mid=(l+r)>>1; if(check(mid,x)) r=mid-1; else l=mid+1; } if(ans==1000000) printf("-1\n"); else printf("%d\n",ans); } } fclose(stdin); fclose(stdout); return 0; }