赌徒解法

“如果愿意承担可能变慢的风险来追求理论上的速度翻倍,那么AVX-512迁移是当前代码在指令级优化上最后一个有意义的突破口。代码结构的其余部分(16叉树、Montgomery、SoA、64字节对齐)已经非常接近该算法在AVX2下的极限。部分Intel处理器在执行512位宽指令时,会主动降低核心频率。而洛谷评测机是Ice Lake架构。在Ice Lake上,持续执行512位乘法指令可能触发频率下降。如果线段树的操作很密集,降频带来的损失有可能抵消甚至超过指令数减半的收益。因此,这份代码的收益高度依赖于评测机的实际频率策略。”

#pragma GCC target("avx2,avx512f,avx512dq,avx512bw,avx512vl,popcnt,lzcnt,bmi,bmi2")
#define __AVX512F__ 1
#define __AVX512DQ__ 1
#define __AVX512BW__ 1
#define __AVX512VL__ 1
#include <immintrin.h>
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
typedef unsigned u32;
typedef unsigned long long ull;
const int MaxN=100005,MaxB=1<<18;
char ib[MaxB],ob[MaxB];
int ip,ie,op;
inline int gc()
{
    if(__builtin_expect(ip==ie,0))
    {
        ie=fread(ib,1,MaxB,stdin);
        ip=0;
        if(!ie)return -1;
    }
    return ib[ip++];
}
inline int read()
{
    unsigned c=gc()-'0';
    while(c>9)c=gc()-'0';
    int x=c;
    while((c=gc()-'0')<=9)x=x*10+c;
    return x;
}
inline void write(ull x)
{
    static const char dig[]=
        "0001020304050607080910111213141516171819"
        "2021222324252627282930313233343536373839"
        "4041424344454647484950515253545556575859"
        "6061626364656667686970717273747576777879"
        "8081828384858687888990919293949596979899";
    char s[21],*p=s+20;
    *p='\n';
    while(x>=100)
    {
        ull q=x/100;
        p-=2;
        memcpy(p,dig+2*(x-q*100),2);
        x=q;
    }
    if(x<10)*--p='0'+x;
    else
    {
        p-=2;
        memcpy(p,dig+2*x,2);
    }
    int len=s+21-p;
    if(__builtin_expect(op+len>MaxB,0))
    {
        fwrite(ob,1,op,stdout);
        op=0;
    }
    memcpy(ob+op,p,len);
    op+=len;
}
static constexpr u32 inv32(u32 m)
{
    u32 x=m;
    for(int i=0;i<5;i++)x*=2-m*x;
    return x;
}
#define MOD (MC?(u32)MC:Mr)
#define VEC (MC?true:vecr)
#define ONE (MC?(u32)(MC>1?1u:0u):Oner)
#define VM (MC?_mm512_set1_epi32((int)MC):vMr)
#define VMINV (MC?_mm512_set1_epi32((int)inv32(MC|1)):vMinvr)
template<u32 MC>struct Tree
{
    struct Tag
    {
        u32 b,c;
    };
    int n,H;
    u32 Mr,Oner;
    bool vecr;
    size_t cnt[8];
    u32 *S[8],*Bt[8],*Ct[8];
    __m512i vMr,vMinvr;
    static u32 *alloc64(size_t words)
    {
        size_t bytes=((words*4+63)/64)*64;
        if(!bytes)bytes=64;
        u32 *p=(u32*)aligned_alloc(64,bytes);
        memset(p,0,bytes);
        return p;
    }
    static inline __m512i mont_mul(__m512i x,__m512i y,__m512i vM,__m512i vMinv)
    {
        __m512i xo=_mm512_srli_epi64(x,32),yo=_mm512_srli_epi64(y,32);
        __m512i te=_mm512_mul_epu32(x,y);
        __m512i to=_mm512_mul_epu32(xo,yo);
        __m512i me=_mm512_mul_epu32(te,vMinv);
        __m512i mo=_mm512_mul_epu32(to,vMinv);
        __m512i ue=_mm512_mul_epu32(me,vM);
        __m512i uo=_mm512_mul_epu32(mo,vM);
        __m512i T=_mm512_mask_blend_epi32(0xAAAA,_mm512_srli_epi64(te,32),to);
        __m512i U=_mm512_mask_blend_epi32(0xAAAA,_mm512_srli_epi64(ue,32),uo);
        __m512i r=_mm512_sub_epi32(T,U);
        return _mm512_min_epu32(r,_mm512_add_epi32(r,vM));
    }
    static inline __m512i add_mod(__m512i x,__m512i y,__m512i vM)
    {
        __m512i r=_mm512_add_epi32(x,y);
        return _mm512_min_epu32(r,_mm512_sub_epi32(r,vM));
    }
    static inline u32 hsum16(__m512i v)
    {
        __m256i lo=_mm512_castsi512_si256(v);
        __m256i hi=_mm512_extracti64x4_epi64(v,1);
        __m256i s=_mm256_add_epi32(lo,hi);
        __m128i x=_mm_add_epi32(_mm256_castsi256_si128(s),_mm256_extracti128_si256(s,1));
        x=_mm_add_epi32(x,_mm_shuffle_epi32(x,0x4E));
        x=_mm_add_epi32(x,_mm_shuffle_epi32(x,0xB1));
        return (u32)_mm_cvtsi128_si32(x);
    }
    static inline __mmask16 cmask16(int a,int e)
    {
        u32 lo=(a>=16)?0xFFFFu:((1u<<a)-1);
        u32 hi=(e>=16)?0xFFFFu:((1u<<e)-1);
        return (__mmask16)(hi^lo);
    }
    inline u32 rawsum(const u32 *s,int a,int e)const
    {
        if(VEC)
        {
            __mmask16 mask=cmask16(a,e);
            __m512i v=_mm512_maskz_mov_epi32(mask,_mm512_load_si512((const __m512i*)s));
            return hsum16(v);
        }
        ull t=0;
        for(int j=a;j<e;j++)t+=s[j];
        return (u32)(t%MOD);
    }
    inline u32 nodeTotal(int L,size_t node)const
    {
        return rawsum(S[L]+node*16,0,16)%MOD;
    }
    void init(int n_,u32 M_,const u32 *a)
    {
        n=n_;
        Mr=M_;
        Oner=1%M_;
        vecr=(M_&1)&&M_>1&&M_<(1u<<27);
        vMr=_mm512_set1_epi32((int)M_);
        vMinvr=_mm512_set1_epi32((int)inv32(M_|1));
        H=1;
        while((1L<<(4*H))<n)H++;
        for(int L=1;L<=H;L++)
        {
            cnt[L]=((size_t)n+(1u<<(4*L))-1)>>(4*L);
            size_t words=cnt[L]*16;
            S[L]=alloc64(words);
            Bt[L]=alloc64(words);
            Ct[L]=alloc64(words);
            u32 one=ONE;
            for(size_t i=0;i<words;i++)Bt[L][i]=one;
        }
        for(int i=0;i<n;i++)S[1][i]=a[i]%MOD;
        for(int L=2;L<=H;L++)
            for(size_t node=0;node<cnt[L];node++)
                for(int j=0;j<16;j++)
                {
                    size_t ch=node*16+j;
                    if(ch<cnt[L-1])S[L][ch]=nodeTotal(L-1,ch);
                }
    }
    struct Geo
    {
        int a,e,pL,lL,rL,pR,lR,rR;
    };
    static inline Geo geo(int l,int r,int sh)
    {
        Geo g;
        int W=1<<sh,m=W-1;
        g.a=(l+m)>>sh;
        g.e=r>>sh;
        if(g.a>g.e)g.e=g.a;
        g.pL=g.pR=-1;
        g.lL=g.rL=g.lR=g.rR=0;
        if(l&m)
        {
            g.pL=l>>sh;
            g.lL=l&m;
            g.rL=(((r-1)>>sh)==g.pL)?r-(g.pL<<sh):W;
        }
        if((r&m)&&(g.pL<0||(r>>sh)!=g.pL))
        {
            g.pR=r>>sh;
            g.rR=r&m;
        }
        return g;
    }
    inline void kernel(int L,size_t node,Tag t1,Tag t21,int a,int e,u32 len)
    {
        u32 *s=S[L]+node*16;
        const bool leaf=(L==1);
        const bool tnon=t1.b!=ONE||t1.c!=0;
        if(!VEC)
        {
            u32 *bb=Bt[L]+node*16,*cc=Ct[L]+node*16;
            for(int j=0;j<16;j++)
            {
                Tag t=(j>=a&&j<e)?t21:t1;
                s[j]=((ull)t.b*s[j]+(ull)t.c*len)%MOD;
                if(!leaf)
                {
                    cc[j]=((ull)t.b*cc[j]+t.c)%MOD;
                    bb[j]=(ull)t.b*bb[j]%MOD;
                }
            }
            return;
        }
        const __m512i vM=VM,vMinv=VMINV;
        const u32 M=MOD;
        __m512i vb1,vl1,vc1;
        if(tnon)
        {
            vb1=_mm512_set1_epi32((u32)(((ull)t1.b<<32)%M));
            vl1=_mm512_set1_epi32((u32)((ull)t1.c*len%M));
            vc1=_mm512_set1_epi32(t1.c);
        }
        else
        {
            vb1=_mm512_set1_epi32((u32)(((ull)ONE<<32)%M));
            vl1=vc1=_mm512_setzero_si512();
        }
        __m512i vb21=vb1,vl21=vl1,vc21=vc1;
        if(a<e)
        {
            vb21=_mm512_set1_epi32((u32)(((ull)t21.b<<32)%M));
            vl21=_mm512_set1_epi32((u32)((ull)t21.c*len%M));
            vc21=_mm512_set1_epi32(t21.c);
        }
        __mmask16 mask=cmask16(a,e);
        __m512i bl=_mm512_mask_blend_epi32(mask,vb1,vb21);
        __m512i cl=_mm512_mask_blend_epi32(mask,vl1,vl21);
        __m512i cv=_mm512_mask_blend_epi32(mask,vc1,vc21);
        __m512i sv=_mm512_load_si512((const __m512i*)s);
        _mm512_store_si512((__m512i*)s,add_mod(mont_mul(sv,bl,vM,vMinv),cl,vM));
        if(!leaf)
        {
            u32 *bb=Bt[L]+node*16;
            u32 *cc=Ct[L]+node*16;
            __m512i b0=_mm512_load_si512((const __m512i*)bb);
            __m512i c0=_mm512_load_si512((const __m512i*)cc);
            _mm512_store_si512((__m512i*)bb,mont_mul(b0,bl,vM,vMinv));
            _mm512_store_si512((__m512i*)cc,add_mod(mont_mul(c0,bl,vM,vMinv),cv,vM));
        }
    }
    u32 upd(int L,size_t node,int l,int r,Tag t1,const Tag &t2)
    {
        const u32 M=MOD;
        Geo g=geo(l,r,4*(L-1));
        const bool tnon=t1.b!=ONE||t1.c!=0;
        if(g.a<g.e||tnon)
        {
            Tag t21=t1;
            if(g.a<g.e)t21=Tag{(u32)((ull)t2.b*t1.b%M),(u32)(((ull)t2.b*t1.c+t2.c)%M)};
            kernel(L,node,t1,t21,g.a,g.e,1u<<(4*(L-1)));
        }
        if(g.pL>=0)
        {
            size_t idx=node*16+g.pL;
            Tag tp{Bt[L][idx],Ct[L][idx]};
            Bt[L][idx]=ONE;
            Ct[L][idx]=0;
            S[L][idx]=upd(L-1,idx,g.lL,g.rL,tp,t2);
        }
        if(g.pR>=0)
        {
            size_t idx=node*16+g.pR;
            Tag tp{Bt[L][idx],Ct[L][idx]};
            Bt[L][idx]=ONE;
            Ct[L][idx]=0;
            S[L][idx]=upd(L-1,idx,g.lR,g.rR,tp,t2);
        }
        return nodeTotal(L,node);
    }
    void update(int l,int r,bool mul,u32 k)
    {
        if(l>=r)return;
        k%=MOD;
        Tag t2=mul?Tag{k,0}:Tag{ONE,k};
        upd(H,0,l,r,Tag{ONE,0},t2);
    }
    ull qry(int L,size_t node,int l,int r,Tag T)
    {
        const u32 M=MOD;
        Geo g=geo(l,r,4*(L-1));
        ull res=0;
        if(g.a<g.e)res=T.b*(ull)rawsum(S[L]+node*16,g.a,g.e)+(ull)T.c*((ull)(g.e-g.a)<<(4*(L-1)));
        if(g.pL>=0)
        {
            size_t idx=node*16+g.pL;
            u32 pb=Bt[L][idx],pc=Ct[L][idx];
            Tag Tn=(pb==ONE&&pc==0)?T:Tag{(u32)((ull)T.b*pb%M),(u32)(((ull)T.b*pc+T.c)%M)};
            res+=qry(L-1,idx,g.lL,g.rL,Tn);
        }
        if(g.pR>=0)
        {
            size_t idx=node*16+g.pR;
            u32 pb=Bt[L][idx],pc=Ct[L][idx];
            Tag Tn=(pb==ONE&&pc==0)?T:Tag{(u32)((ull)T.b*pb%M),(u32)(((ull)T.b*pc+T.c)%M)};
            res+=qry(L-1,idx,g.lR,g.rR,Tn);
        }
        return VEC?res:res%M;
    }
    u32 query(int l,int r)
    {
        if(l>=r)return 0;
        return (u32)(qry(H,0,l,r,Tag{ONE,0})%MOD);
    }
};
static u32 av[MaxN];
template<u32 MC>static void solve(int n,int q,u32 M)
{
    static Tree<MC> tree;
    for(int i=0;i<n;i++)av[i]=read();
    tree.init(n,M,av);
    while(q--)
    {
        u32 op=read(),x=read(),y=read();
        if(op==3)write(tree.query(x-1,y));
        else tree.update(x-1,y,op==1,read());
    }
}
int main()
{
    int n=read(),q=read();
    u32 M=read();
    if(M==571373)solve<571373>(n,q,M);
    else solve<0>(n,q,M);
    fwrite(ob,1,op,stdout);
    return 0;
}

0 条评论

目前还没有评论...