出現了一篇跑得炒雞慢的題解！

noteskey

無 fuck 說，好像就是整個數列分塊然后合并區間...什么的吧

對于每塊內部就是算一下前綴信息、后綴信息（就是以 第一個點/最后一個點 為一個邊界，不超過 log 個不同的 or 值所要到達的最 左/右 點）和中值信息（就是某種區間長度內能 or 出來的最大值）

然后詢問的時候從第一個塊開始，向后先查詢當前塊與下一個塊合并的答案，然后更新當前塊

watch out

nothing ，打代碼的時候注意細節貌似是所有 coding 的 gift ？ 【霧

code

//by Judge #pragma GCC optimize(3) #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define Rg register #define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i) #define P pair<int,int> #define ll long long #define se second #define fi first using namespace std; const int bl=403; const int M=6e4+3; typedef int arr[M]; #ifndef Judge #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) #endif char buf[1<<21],*p1=buf,*p2=buf; bool operator <(P& a,P& b){return a.fi^b.fi?a.fi<b.fi:a.se>b.se;} inline bool cmax(int& a,int b){return a<b?a=b,1:0;} inline bool cmin(int& a,int b){return a>b?a=b,1:0;} inline int read(){ int x=0,f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } char sr[1<<21],z[20];int CCF=-1,Z; inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;} inline void print(int x,char chr='\n'){if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x;while(z[++Z]=x%10+48,x/=10);while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr; } int n,m,K,ans,pv,a[M],pos[M]; P q[M],vec[bl+3],c[bl+3]; struct BLK{ int mx[bl+3],val[bl+3],L,R,cntp,cnts,all; P pre[33],suf[33]; //最多 log 個不同的 or 值 // mx[i] 長為 i 的區間 or 和的 max 值，val 表示塊內每個點的值 inline void re(){ memset(mx,0,sizeof mx); int p; // 就算 mx 數組 p=cntp=0; fp(i,1,bl) if((p|=val[i])!=pre[cntp].fi) pre[++cntp]=P(p,i+L-1);p=cnts=0; fd(i,bl,1) if((p|=val[i])!=suf[cnts].fi) suf[++cnts]=P(p,i+L-1);int head=1,tail=0;fd(i,bl,1){ int lst=tail,v=val[i];for(Rg int j=v;j;j^=j&-j) q[++tail]=P(__builtin_ctz(j),i);fp(j,head,lst) if(!(v>>q[j].fi&1)) q[++tail]=q[j]; head=lst+1;Rg int now=0,pos; fp(j,head,tail)pos=q[j].se,cmax(mx[pos-i+1],now|=val[pos]);}fp(i,2,bl) cmax(mx[i],mx[i-1]); all=pre[cntp].fi;}inline void build(int l,int r){ L=l,R=r;fp(i,l,r) val[i-l+1]=a[i]; re();}inline void update(int pos,int v){val[pos-L+1]=v,re();} //重構塊 inline int len(int v){return lower_bound(mx+1,mx+1+bl,v)-mx;}//得到構成長度為 v 的 or 和區間最短長度 inline void merge(){ int l=1,r=1,it=0; //將當前的區間和 vec 后綴合并 while(l<=pv&&r<=cnts) c[++it]=vec[l]<suf[r]?vec[l++]:suf[r++];while(l<=pv) c[++it]=vec[l++]; while(r<=cnts) c[++it]=suf[r++];vec[1]=c[1]; fp(i,2,it) vec[i]=c[i],vec[i].fi==vec[i-1].fi&&(vec[i].se=vec[i-1].se);pv=unique(vec+1,vec+1+it)-1-vec;}inline void check(int v){ int len=2e9; //用后綴 vec 和當前塊的前綴更新答案 fp(i,1,cntp) while(pv&&(vec[pv].fi|pre[i].fi)>=v)cmin(len,pre[i].se-vec[pv--].se+1); cmin(ans,len);} }b[131]; int main(){ n=read(),m=read(); fp(i,1,n) a[i]=read();fp(i,1,n) pos[i]=(i-1)/bl+1; K=pos[n],n=K*bl;fp(i,1,K) b[i].build((i-1)*bl+1,i*bl);while(m--){if(read()&1){ int x=read(),y=read();b[pos[x]].update(x,y),a[x]=y;} else{ ans=2e9; int x=read();fp(i,1,K) if(b[i].all>=x)cmin(ans,b[i].len(x));pv=0,b[1].merge();fp(i,2,K){b[i].check(x);fp(j,1,pv) vec[j].first|=b[i].all;b[i].merge();} print(ans<2e9?ans:-1);}} return Ot(),0; }

轉載于:https://www.cnblogs.com/Judge/p/10716248.html

總結

以上是生活随笔為你收集整理的题解 P5065 【[Ynoi2014]不归之人与望眼欲穿的人们】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。