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

回复帖子

@limaopipi2022  2020-03-26 18:37 回复 举报

@Trinitrotoluene

#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;}
inline int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
inline void ask(int L,int R)
{
    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)
    {
        a[i]=read();bl[i]=i/p+1;
        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]);
    while(m--)ask(read()%n+1,read()%n+1);std::cout<<ans;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。