关于这道题最后一个点*2

Mobius127 @ 2023-02-08 14:13:58

by Mobius127 @ 2023-02-08 14:14:09

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
#include <queue>
#include <bitset>
#include <cmath>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef pair <int, int> Pii;
const int INF=0x3f3f3f;
const int cp=1e9+7;
inline int plust(int x, int y){x+=y;if(x>=cp) x-=cp;if(x<0) x+=cp;return x;}
inline int minut(int x, int y){x-=y;if(x>=cp) x-=cp;if(x<0) x+=cp;return x;}
inline int read(){
    char ch=getchar();int x=0, f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline int ksm(int a, int b=cp-2){
    int ret=1;
    for(; b; b>>=1, a=1ll*a*a%cp)
        if(b&1) ret=1ll*ret*a%cp;
    return ret;
}
const int N=5e4+5;
const int M=500;
int n, m, B, a[N], bid[N], ors[M], L[M], R[M];
vector <Pii> pre[M], suf[M], pret, suft;
vi mx[M];
void remake(int x, int p){
    int l=L[bid[x]], r=R[bid[x]];
    for(int i=x, sum=0, lst=-1; i>=l; --i, lst=sum)
        if((sum|=a[i])^lst) mx[p][x-i+1]=max(mx[p][x-i+1], sum);
    for(int i=x, sum=0, lst=-1; i<=r; ++i, lst=sum)
        if((sum|=a[i])^lst) mx[p][i-x+1]=max(mx[p][i-x+1], sum);
    // printf("remake %d:\n", x);
    // for(auto v:ans[x]) printf("[%d %d] ", v.st, v.nd);puts("");
    return ;
}
void rebuild(int idx, int flg){
    //整体重构，flg>0 表示 flg 被修改
    int l=L[idx], r=R[idx];
    // printf("rebuild block %d [%d %d]:%d\n", idx, l, r, flg);
    vector <Pii> ().swap(pre[idx]);
    vector <Pii> ().swap(suf[idx]);
    mx[idx].resize(r-l+2);
    for(int i=0; i<=r-l+1; ++i) mx[idx][i]=0;
    for(int i=l, pr=0, lst=-1; i<=r; ors[idx]=pr, ++i, lst=pr)
        if((pr|=a[i])^lst) pre[idx].pb(mp(pr, i-l+1));
    for(int i=r, sf=0, lst=-1; i>=l; --i, lst=sf)
        if((sf|=a[i])^lst) suf[idx].pb(mp(sf, r-i+1));
    for(int i=l; i<=r; ++i) remake(i, idx);
    for(int i=1; i<=r-l+1; ++i) mx[idx][i]=max(mx[idx][i-1], mx[idx][i]);
}
int Ef(int idx, int val){
    int r=R[idx]-L[idx]+1;if(mx[idx][r]<val) return n+1;
    int l=1, ans=r;
    while(l<=r){
        int mid=l+r>>1;
        if(mx[idx][mid]>=val) ans=mid, r=mid-1;
        else l=mid+1; 
    }
    return ans;
}
signed main(){
    n=read(), m=read();
    for(int i=1; i<=n; ++i) a[0]|=(a[i]=read());
    for(int i=0; i<=30; ++i) if(a[0]&(1<<i)) B=i;
    B=sqrt(30*n);//printf("block len = %d\n", B);
    for(int i=1, c=1; i<=n; i+=B){
        for(int j=0; j<B&&i+j<=n; ++j) bid[i+j]=c;
        L[c]=i, R[c]=min(i+B-1, n);
        rebuild(c, 0);++c;
    }
    for(int i=1; i<=m; ++i){
        int op=read();
        if(op&1){
            int x=read(), y=read();a[x]=y;
            rebuild(bid[x], x);
        }
        else{
            int k=read(), sor=0, len=0;int res=n+1;
            for(int j=bid[1]; j<=bid[n]; ++j){
                res=min(res, Ef(j, k));
                // printf("for block %d: find [%d %d]\n", j, v.st, v.nd);
                if(j==bid[1]) 
                    pret=pre[j], suft=suf[j], sor=ors[j], len=R[j]-L[j]+1;
                else{
                    int sz1=suft.size(), sz2=pre[j].size();
                    for(int l=sz1-1, r=0; l>=0; --l){
                        while(r<sz2&&(suft[l].st|pre[j][r].st)<k) ++r;
                        if(r>=sz2) break;res=min(res, suft[l].nd+pre[j][r].nd);
                    }
                    /*合并*/
                    int lst=-1;
                    vector <Pii> tmp=pre[j];
                    for(auto &v:tmp) v.st|=sor, v.nd+=len;
                    lst=pret.back().st;
                    for(auto &v:tmp) if(v.st!=lst) pret.pb(v), lst=v.st;
                    tmp=suf[j];swap(suft, tmp);
                    for(auto &v:tmp) v.st|=ors[j], v.nd+=R[j]-L[j]+1;
                    lst=suft.back().st;
                    for(auto &v:tmp) if(v.st!=lst) suft.pb(v), lst=v.st;
                    len+=R[j]-L[j]+1, sor|=ors[j]; 
                }
            }
            if(res<=n) printf("%d\n", res);
            else puts("-1");
        }
    }
    return 0;
}

by Mobius127 @ 2023-02-08 15:03:20

草，突然发现我的 rebuild 好像是 O(n) 的。

下大饭