- 河蟹王国
- @ 2026-11-16 16:35:15
一个常数凹到极限的解法
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 条评论
目前还没有评论...