# 话说有没有dalao可以教我一下卡常，TLE80分好难受

• 版块灌水区
• 楼主
• 发帖时间2020-03-26 18:35
@limaopipi2022  2020-03-26 18:37 回复 举报
#include<iostream>
const int M=2e7+5;unsigned long long ans;
int st[4505][15],mL[M],mR[M],a[M];
int n,m,s,t,p=4480,l[4505],x[4505],y[4505],bl[M];
namespace GenHelper
{
unsigned z1,z2,z3,z4,b;
inline unsigned rand_()
{
b=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^b;
b=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^b;
b=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^b;
return (z1^z2^z3^z4);
}
}
inline void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
{
using namespace GenHelper;
int a=rand_()&32767;
int b=rand_()&32767;
return a*32768+b;
}
{
if(L>R)std::swap(L,R);register int res=0;
if(bl[L]==bl[R])
{
for(register int i=L;i<=R;++i)res=std::max(res,a[i]);
ans+=res;return;
}if(bl[R]-bl[L]==1){ans+=std::max(mR[L],mL[R]);return;}
int k=l[bl[R]-bl[L]-1];
res=std::max(st[bl[L]+1][k],st[bl[R]-(1<<k)][k]);
res=std::max(res,std::max(mR[L],mL[R]));ans+=res;
}
main()
{
register int i,j;std::cin>>n>>m>>s;srand(s);
for(i=1;i<=n;++i)
{
st[bl[i]][0]=std::max(st[bl[i]][0],a[i]);
}t=bl[n];l[0]=-1;
for(i=1;i<=t;++i)
{
l[i]=l[i-1]+((1<<l[i-1]+1)==i);
x[i]=(i-1)*p;y[i]=x[i]+p-1;
}x[1]=1;y[t]=n;
for(i=1;i<=n;++i)mL[i]=std::max(a[i],i^x[bl[i]]?mL[i-1]:0);
for(i=n;i>=1;--i)mR[i]=std::max(a[i],i^y[bl[i]]?mR[i+1]:0);
for(j=1;(1<<j)<=t;++j)for(i=1;i+(1<<j)-1<=t;++i)
st[i][j]=std::max(st[i][j-1],st[i+(1<<j-1)][j-1]);
}