一个常数凹到极限的解法
wjszez最优解

#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>
using namespace std;
typedef int i32;
typedef unsigned u32;
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()
{
    int c=gc();
    while(c!='-'&&(c<'0'||c>'9'))c=gc();
    int f=1;
    if(c=='-'){f=-1;c=gc();}
    int x=0;
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=gc();}
    return x*f;
}
inline void write(int x)
{
    static const char dig[]=
        "0001020304050607080910111213141516171819"
        "2021222324252627282930313233343536373839"
        "4041424344454647484950515253545556575859"
        "6061626364656667686970717273747576777879"
        "8081828384858687888990919293949596979899";
    char s[13],*p=s+12;
    *p='\n';
    unsigned ux;
    if(x<0)
    {
        if(__builtin_expect(op+1>MaxB,0))
        {
            fwrite(ob,1,op,stdout);
            op=0;
        }
        ob[op++]='-';
        ux=(unsigned)(-(long long)x);
    }
    else ux=(unsigned)x;
    while(ux>=100)
    {
        unsigned q=ux/100;
        p-=2;
        memcpy(p,dig+2*(ux-q*100),2);
        ux=q;
    }
    if(ux<10)*--p='0'+ux;
    else
    {
        p-=2;
        memcpy(p,dig+2*ux,2);
    }
    int len=s+13-p;
    if(__builtin_expect(op+len>MaxB,0))
    {
        fwrite(ob,1,op,stdout);
        op=0;
    }
    memcpy(ob+op,p,len);
    op+=len;
}
struct Tree
{
    int n,H;
    size_t cnt[8];
    u32 *S[8],*Bt[8];
    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 int hmax16(__m512i v)
    {
        __m256i lo=_mm512_castsi512_si256(v);
        __m256i hi=_mm512_extracti64x4_epi64(v,1);
        __m256i s=_mm256_max_epi32(lo,hi);
        __m128i x=_mm_max_epi32(_mm256_castsi256_si128(s),_mm256_extracti128_si256(s,1));
        x=_mm_max_epi32(x,_mm_shuffle_epi32(x,0x4E));
        x=_mm_max_epi32(x,_mm_shuffle_epi32(x,0xB1));
        return _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 int rawmax(const u32 *s,int a,int e)const
    {
        if(a>=e)return INT_MIN;
        __mmask16 mask=cmask16(a,e);
        __m512i full=_mm512_load_si512((const __m512i*)s);
        __m512i fill=_mm512_set1_epi32(INT_MIN);
        return hmax16(_mm512_mask_mov_epi32(fill,mask,full));
    }
    void init(int n_,const int *a)
    {
        n=n_;
        H=1;
        while((1LL<<(4*H))<n)H++;
        __m512i vmin=_mm512_set1_epi32(INT_MIN);
        for(int L=1;L<=H;L++)
        {
            cnt[L]=((size_t)n+(1LL<<(4*L))-1)>>(4*L);
            size_t words=cnt[L]*16;
            S[L]=alloc64(words);
            Bt[L]=alloc64(words);
            for(size_t i=0;i<words;i+=16)_mm512_store_si512((__m512i*)(S[L]+i),vmin);
        }
        for(int i=0;i<n;i++)S[1][i]=(u32)a[i];
        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]=(u32)rawmax(S[L-1]+ch*16,0,16);
                }
    }
    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,int t1,int t21,int a,int e)
    {
        u32 *s=S[L]+node*16;
        __mmask16 mask=cmask16(a,e);
        __m512i add=_mm512_mask_blend_epi32(mask,_mm512_set1_epi32(t1),_mm512_set1_epi32(t21));
        __m512i sv=_mm512_load_si512((const __m512i*)s);
        _mm512_store_si512((__m512i*)s,_mm512_add_epi32(sv,add));
        if(L>1)
        {
            u32 *b=Bt[L]+node*16;
            __m512i bv=_mm512_load_si512((const __m512i*)b);
            _mm512_store_si512((__m512i*)b,_mm512_add_epi32(bv,add));
        }
    }
    int upd(int L,size_t node,int l,int r,int t1,int t2)
    {
        Geo g=geo(l,r,4*(L-1));
        if(g.a<g.e||t1)kernel(L,node,t1,t1+t2,g.a,g.e);
        if(g.pL>=0)
        {
            size_t idx=node*16+g.pL;
            int tag=(int)Bt[L][idx];
            Bt[L][idx]=0;
            S[L][idx]=(u32)upd(L-1,idx,g.lL,g.rL,tag,t2);
        }
        if(g.pR>=0)
        {
            size_t idx=node*16+g.pR;
            int tag=(int)Bt[L][idx];
            Bt[L][idx]=0;
            S[L][idx]=(u32)upd(L-1,idx,g.lR,g.rR,tag,t2);
        }
        return rawmax(S[L]+node*16,0,16);
    }
    void update(int l,int r,int c)
    {
        if(l>=r)return;
        upd(H,0,l,r,0,c);
    }
    int qry(int L,size_t node,int l,int r,int carry)
    {
        Geo g=geo(l,r,4*(L-1));
        int ans=INT_MIN;
        if(g.a<g.e)
        {
            int m=rawmax(S[L]+node*16,g.a,g.e);
            if(m!=INT_MIN)
            {
                int v=m+carry;
                if(v>ans)ans=v;
            }
        }
        if(g.pL>=0)
        {
            size_t idx=node*16+g.pL;
            int tag=(int)Bt[L][idx];
            int res=qry(L-1,idx,g.lL,g.rL,carry+tag);
            if(res>ans)ans=res;
        }
        if(g.pR>=0)
        {
            size_t idx=node*16+g.pR;
            int tag=(int)Bt[L][idx];
            int res=qry(L-1,idx,g.lR,g.rR,carry+tag);
            if(res>ans)ans=res;
        }
        return ans;
    }
    int query(int l,int r)
    {
        if(l>=r)return INT_MIN;
        return qry(H,0,l,r,0);
    }
};
static int av[MaxN];
static Tree tree;
int main()
{
    int n=read();
    for(int i=0;i<n;i++)av[i]=read();
    tree.init(n,av);
    int q=read();
    while(q--)
    {
        int k=read();
        if(k==1)
        {
            int l=read()-1,r=read(),c=read();
            tree.update(l,r,c);
        }
        else
        {
            int l=read()-1,r=read();
            write(tree.query(l,r));
        }
    }
    fwrite(ob,1,op,stdout);
    return 0;
}

0 条评论

目前还没有评论...

信息

ID
1144
难度
4
分类
数据结构 | 线段树 点击显示
标签
递交数
28
已通过
14
通过率
50%
上传者