关于块长影响正确性

P5065 [Ynoi2014] 不归之人与望眼欲穿的人们

Swedish_Pigeon @ 2024-05-21 22:06:08

我的代码能够 AC 的充要条件是 198 <= 块长 <= 298,非常神奇,求教

(若块长不在范围内则会引发正确性问题)

#include<bits/stdc++.h>
#define pb push_back
#define endl '\n'
#define reg register

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int homo=114514,inf=0x3f3f3f3f;

//fast IO
#define _r return *this
#define _o &operator
namespace IO { const int _S = 1 << 20; char b[_S], *p1 = b, *p2 = b, pb[_S], *pp = pb;
    void fl() { fwrite(pb, 1, pp - pb, stdout), pp = pb; }
    struct fr { char gc() { if (p1 == p2) p2 = (p1 = b) + fread(b, 1, _S, stdin); return p1 == p2 ? ' ' : *p1++; }
        fr _o>>(char &c) { do c = gc(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t'); _r; }
        template <class T> fr _o>>(T &x) { char c = gc(); T f = 1; for (x = 0; !isdigit(c);) (c == '-' ? f = -1 : 1),
            c = gc(); while (isdigit(c)) x = (x * 10) + (c ^ 48), c = gc(); x *= f; _r; } fr() {} } in;
    struct fw { void pt(char c) { *pp++ = c; if (pp - pb == _S) fl(); } fw _o<<(char c) { pt(c); _r; }
        template <class T> fw _o<<(T x) { if (!x) { pt(48); _r; } if(x < 0) pt('-'), x = -x;
            static int s[64], t; t = 0; while (x) s[++t] = x % 10, x /= 10; while (t) pt(s[t--] + 48); _r; }
        fw _o<<(const char *s) { int c = 0; while (s[c]) pt(s[c++]); _r; }  fw() {} } out;
struct fe { ~fe() { fl(); } } fls; } using IO::in; using IO::out;
//end fast IO

const int N=5e4+233;
const int K=233,B=N/K+5;
//K 为块长
int n,m,a[N];
struct vect
{
    int a[32],sz;
    inline int& operator[](int i) { return a[i]; }
    inline void pb(int val) { a[sz++]=val; }
};
inline void ins(vect &v1,vect &v2,int val,int pos)
{
    v1.sz=0;
    for (int i=0;i<31;i++)
        if (val&1<<i) v1.pb(i|pos<<5);
    for (int i=0;i<v2.sz;i++)
        if (!(val&1<<(v2[i]&31))) v1.pb(v2[i]);
}
inline void mrg(vect &v1,vect &v2,int val,vect &v3)
{
    v3.sz=0;
    for (int i=0;i<v1.sz;i++)
        if (val&1<<(v1[i]&31)) v3.pb(v1[i]);
    for (int i=0;i<v2.sz;i++)
        if (!(val&1<<(v2[i]&31))) v3.pb(v2[i]);
}
struct block
{
    vect pre[K+5],suf[K+5];
    //pre 降序,suf 升序
    int a[K+5],mx[K+5];
    int sz,begin,sum;
    inline int& operator[](int i) { return a[i]; }
    inline void getmx()
    {
        for (int i=1;i<=sz;i++) mx[i]=-inf;
        for (int i=1,s=0;i<=sz;i++,s=0)
            for (int j=0;j<pre[i].sz;j++)
            {
                int &np=mx[i-(pre[i][j]>>5)+begin+1];
                np=max(np,s|=1<<(pre[i][j]&31));
            }
        for (int i=1;i<=sz;i++) mx[i]=max(mx[i],mx[i-1]);
    }
    inline void build()
    {
        for (int i=1;i<=sz;i++) sum|=a[i];
        for (int i=1;i<=sz;i++) ins(pre[i],pre[i-1],a[i],begin+i);
        for (int i=sz;i>=1;i--) ins(suf[i],suf[i+1],a[i],begin+i);
        getmx();
    }
    inline void udt(int pos,int val)
    {
        int ch=a[pos]^val;
        a[pos]=val;
        sum=0;
        for (int i=1;i<=sz;i++) sum|=a[i];
        ins(pre[pos],pre[pos-1],a[pos],begin+pos);
        for (int i=pos+1,s=0;i<=sz;i++)
        {
            ins(pre[i],pre[i-1],a[i],begin+i);
            s|=a[i];
            if (ch==(s&ch)) break;
        }
        getmx();
        ins(suf[pos],suf[pos+1],a[pos],begin+pos);
        for (int i=pos-1,s=0;i>=1;i--)
        {
            ins(suf[i],suf[i+1],a[i],begin+i);
            s|=a[i];
            if (ch==(s&ch)) break;
        }
    }
    inline int qry(int x,int lim)
    { return mx[sz]<x?inf:lower_bound(mx+1,mx+min(sz+1,lim),x)-mx; }
}b[B];
vect suf[B];
int lxl,bel[N],idx[N];
inline void udt(int pos,int val)
{
    b[bel[pos]].udt(idx[pos],val);
    for (int i=bel[pos];i>=1;i--) mrg(b[i].suf[1],suf[i+1],b[i].sum,suf[i]);
}
inline int qry(int x)
{
    int ans=inf;
    for (int i=1;i<=lxl;i++)
        ans=min(ans,b[i].qry(x,ans));
    for (int i=lxl;i>=2;i--)
    {
        int v=b[i-1].sum,pv;
        vect &sf=b[i-1].suf[1];
        for (int j=0,k=0,s=0;j<suf[i].sz;j++)
        {
            if ((suf[i][j]>>5)-b[i].begin>=ans) break;
            s|=1<<(suf[i][j]&31);
            if ((s|v)<x) continue;
            while (k+1<sf.sz)
            {
                pv=v&~(1<<(sf[k]&31));
                if ((s|pv)>=x) k++,v=pv;
                else break;
            }
            ans=min(ans,(suf[i][j]>>5)-(sf[k]>>5)+1);
            if (k+1==sf.sz) break;
        }
    }
    return ans==inf?-1:ans;
}

int main()
{
    in>>n>>m;
    lxl=(n-1)/K+1;
    for (int i=1;i<=lxl;i++)
    {
        int L=(i-1)*K+1,R=min(n,i*K);
        for (int j=L;j<=R;j++) in>>b[bel[j]=i][idx[j]=j-L+1];
        b[i].sz=R-L+1,b[i].begin=L-1;
        b[i].build();
    }
    for (int i=lxl;i>=1;i--) mrg(b[i].suf[1],suf[i+1],b[i].sum,suf[i]);
    int op,i,x;
    while (m--)
    {
        in>>op;
        if (op==1) in>>i>>x,udt(i,x);
        else in>>x,out<<qry(x)<<endl;
    }

    return 0;
}

|