求助卡常

RT

TLE #2 #10

实在卡不动了/kk

#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define N 10000
namespace GenHelper{
    unsigned z1,z2,z3,z4,b;
    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);
    }
}
void srand(unsigned x){
    using namespace GenHelper;
    z1=x,z2=(~x)^0x233333333U,z3=x^0x1234598766U,z4=(~x)+51;
}
int read(){
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
int maxl[20000005],maxr[20000005];
int a[20000005],b[20000005],f[15][N],lg[N],p[15]={1},blo,n,m,s;
void init(){
    for(register int i=1;i<=n;i++)
        b[i]=(i-1)/blo+1;
    int x;
    for(register int i=1;blo*(i-1)+1<=n;i++){
        int tmp=(i-1)*blo;
        x=min(blo,n-tmp);
        maxl[tmp+1]=a[tmp+1],maxr[tmp+x]=a[tmp+x];
        for(register int j=2;j<=x;j++)
            maxl[tmp+j]=max(maxl[tmp+j-1],a[tmp+j]);
        for(register int j=x-1;j>0;j--)
            maxr[tmp+j]=max(maxr[tmp+j+1],a[tmp+j]);
        f[0][i]=maxl[tmp+x];
    }
    for(register int i=1;i<15;i++)
        p[i]=p[i-1]<<1;
    lg[0]=-1;
    for(register int i=1;i<N;i++)
        lg[i]=lg[i>>1]+1;
    for(register int j=1;j<15;j++)
        for(register int i=1;i+p[j]<=n/blo+3;i++)
            f[j][i]=max(f[j-1][i],f[j-1][i+p[j-1]]);
}
signed main(){
//  freopen("P3793.in","r",stdin);
//  freopen("out.out","w",stdout);
    scanf("%d%d%d",&n,&m,&s);
    srand(s);
    blo=sqrt(n)/2+1;
    for(register int i=1;i<=n;i++)
        a[i]=read();
    init();
    int l,r,kkak;
    long long ans=0;
    while(m--){
//      if(m%1000000==0)cout<<m<<endl;
        l=read()%n+1,r=read()%n+1;
        if(l>r)l^=r^=l^=r;
        if(b[l]+1==b[r])ans+=max(maxr[l],maxl[r]);
        else if(b[l]==b[r]){
            kkak=0;
            for(register int i=l;i<=r;i++)
                kkak=kkak<a[i]?a[i]:kkak;
            ans+=kkak;
        }
        else kkak=lg[b[r]-b[l]-1],ans+=max(max(f[kkak][b[l]+1],f[kkak][b[r]-p[kkak]]),max(maxr[l],maxl[r]));
    }
    printf("%lld",ans);
    return 0;
}