萌新have just learned OI求助

RT，80pts，快绝望了，怎么卡常啊？

#include <iostream>
#include <cstdio>
#include <cmath>
#define yycoi 0
#define re register
#define mymax(a, b) (a>b?a:b)
#define violence(aa, bb, ans) for (int kkk=aa; kkk<=bb; ++kkk) ans=mymax(ans, a[kkk])
const int N=20010000;
const int M=20000000;
const int SQRTN=4473;
int n, m;
unsigned s;
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 sr(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 a[N+2], pre[N+2], post[N+2], block[SQRTN+2][SQRTN+2];
int szblock;
unsigned long long summ;
int main()
{
    #if yycoi==1
    freopen("tmp.in", "r", stdin);
    freopen("tmp.out", "w", stdout);
    #endif // yycoi
    scanf("%d%d%u", &n, &m, &s);
    sr(s);
    szblock=std::sqrt(n)+1;
    #if yycoi==2
    printf("%d\n", szblock);
    #endif // yycoi
    for (re int i=0; i<n; ++i)
        a[i]=read();
    #if yycoi==2
    for (int i=0; i<n; ++i)
        printf("%d\n", a[i]);
    #endif // yycoi
    int tmp;
    for (re int i=0; i<szblock-1; ++i)
    {
        tmp=szblock*i;
        pre[tmp]=a[tmp];
        for (re int j=1; j<szblock; ++j)
            pre[tmp+j]=mymax(pre[tmp+j-1], a[tmp+j]);
    }
    for (re int i=0; i<n; ++i)
    {
        if (i%szblock==0)
            pre[i]=a[i];
        else
            pre[i]=mymax(pre[i-1], a[i]);
    }
    #if yycoi==2
    for (int i=0; i<szblock*szblock; ++i)
        printf("%d\n", pre[i]);
    #endif // yycoi
    #if yycoi==2
    printf("pre ok\n");
    #endif // yycoi
    for (re int i=(n-1)/szblock*szblock-1; i>=0; --i)
    {
        if ((i+1)%szblock==0)
            post[i]=a[i];
        else
            post[i]=mymax(post[i+1], a[i]);
    }
    #if yycoi==2
    for (int i=0; i<szblock*szblock; ++i)
        printf("%d\n", pre[i]);
    #endif // yycoi
    #if yycoi==2
    printf("post ok\n");
    #endif // yycoi
    for (re int i=0; i<szblock-1; ++i)
    {
        block[i][i]=post[i*szblock];
    }
    for (re int i=1; i<=szblock-1; ++i)
    {
        for (re int j=0; j<szblock-i; ++j)
            block[j][j+i]=mymax(block[j][j], block[j+1][j+i]);
    }
    #if yycoi==2
    printf("block ok\n");
    #endif // yycoi
    int l, r, bcl, bcr, ans;
    while (m--)
    {
        l=read()%n, r=read()%n;
        if (l>r)
        {
            tmp=l;
            l=r;
            r=tmp;
        }
        #if yycoi==2
        printf("%d %d\n", l, r);
        #endif // yycoi
        bcl=l/szblock, bcr=r/szblock;
        if (bcl==bcr)
        {
            ans=-2147483647-1;
            violence(l, r, ans);
            summ+=ans;
        }
        else if (bcl+1==bcr)
            summ+=mymax(post[l], pre[r]);
        else
            summ+=mymax(mymax(post[l], pre[r]), block[bcl+1][bcr-1]);
    }
    printf("%llu\n", summ);
    return 0;
}
#undef yycoi