求助卡常

bovine__kebi @ 2020-06-21 09:19:06

by bovine__kebi @ 2020-06-21 09:19:33

二楼贴代码，这是跑的最快的一份

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<bits/stdc++.h>
using namespace std;
const int maxn=20000005;
const int maxm=4485;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long long ll;
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);
    }
}
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<<15)+b;
}
ull a[maxn],st[maxm][20],lg[maxm];
int n,m,s;
ull size,ans;
ull pre[maxn],bk[maxn];
inline ull belong(int i){return (i-1)/size+1;}
inline void init()
{
    for(register int i=1;i<=n;i++)st[belong(i)][0]=max(st[belong(i)][0],a[i]);
    int p=belong(n);
    for(register ull i=1;(ull)(1<<i)<=p;i++)
    {
        for(ull j=1;j+(1<<i)-1<=p;j++)
        {
            st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
        }
    }
}
inline ull query(int l,int r)
{
    ull ans2=0;int ml=belong(l),mr=belong(r);
    if(ml==mr){for(register int i=l;i<=r;i++)ans2=max(ans2,a[i]);return ans2;}
    if(mr-ml==1)return max(bk[l],pre[r]);
    int x=lg[mr-ml-1];
    ans2=max(st[ml+1][x],st[mr-(1<<x)][x]);
    ans2=max(ans2,max(bk[l],pre[r]));
    return ans2;
}
int main()
{
    scanf("%d %d %d",&n,&m,&s);
    srand((unsigned)s);
    size=sqrt(n);
    for(register int i=1;i<=n;i++)a[i]=read();
    lg[0]=-1;
    for(register int i=1;i<=belong(n);i++)lg[i]=lg[i>>1]+1;
    for(register int i=1;i<=n;i++)pre[i]=(i%size==1)?a[i]:max(pre[i-1],a[i]);
    for(register int i=n;i>=1;i--)bk[i]=(i%size==0)?a[i]:max(bk[i+1],a[i]);
    init();
    for(register int i=1;i<=m;i++)
    {
        int l=read()%n+1,r=read()%n+1;if(l>r)swap(l,r);
        ans+=query(l,r);
    }
    printf("%llu\n",ans);
}

by bovine__kebi @ 2020-06-21 09:20:41

不预处理bl，TLE，预处理bl，MLE

by Aw顿顿 @ 2020-06-21 09:28:37

@bovine__kebi https://www.luogu.com.cn/record/34558227

你这不是过了 #2

by bovine__kebi @ 2020-06-21 09:30:09

我还是想知道到底该怎么卡/kk

by bovine__kebi @ 2020-06-21 09:30:41

两个点都是极限数据，但是照理来说应该不会T吧

by Aw顿顿 @ 2020-06-21 09:31:08

@bovine__kebi

读入换一下？

const int LEN=(1<<20);
inline int nec(){
    static char buf[LEN],*p=buf,*e=buf;
    if(p==e){
        if((e=buf+fread(buf,1,LEN,stdin))==buf)return EOF;
        p=buf;
    }return *p++;
}inline bool nei(int &x){
    static char neg=0,c=nec();
    neg=0,x=0;
    while((c<'0'||c>'9')&&c!='-'){
        if(c==EOF)return 0;
        c=nec();
    }if(c=='-'){neg=1;c=nec();}
    do{x=x*10+c-'0';}while((c=nec())>='0');
    if(neg)x=-x;
    return 1;
}

by bovine__kebi @ 2020-06-21 09:31:33

@Aw顿顿 不是，就3个数换了有可能出现负优化吧？我去试试

by bovine__kebi @ 2020-06-21 09:33:36

还是过不了/wn

by LanrTabe @ 2020-06-21 09:36:14

试试把st表两维反过来（？

by bovine__kebi @ 2020-06-21 09:40:11

@LanrTabe 这样有用吗((((