- 题解
- @ 2026-11-16 16:50:34
赌徒解法
“如果愿意承担可能变慢的风险来追求理论上的速度翻倍,那么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 条评论
目前还没有评论...