玄学错误求调

TLE 30pts

#include <bits/stdc++.h>
#define int long long

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 s=rand_()&32767;
    int b=rand_()&32767;
    return s*32768+b;
}

const int N = 2e7 + 5;
int pos[N], a[N];
int S, pre[N], suf[N];
int n, m, s;

const int M = 1e6 + 5;
int sum[M], l[M], r[M];
int st[M][15];  

void build(){
    S = log2(n);
    for (int i = 1; i <= S; i ++){
        l[i] = (i - 1) * S + 1;
        r[i] = i * S;
    }
    if (r[S] < n) l[S + 1] = r[S] + 1, r[++ S] = n;
    for (int i = 1; i <= S; i ++)
    for (int i = S; i >= 1; i --)
        for (int j = l[i]; j <= r[i]; j ++)
            pre[j] = std::max(a[j], pre[j - 1]);
    for (int i = 1; i <= S; i ++)
        for (int j = r[i]; j >= l[i]; j --)
            suf[j] = std::max(a[j], suf[j + 1]);
    for (int i = 1; i <= S; i ++)
        st[i][0] = sum[i];
    for (int j = 1; j <= 20; j ++){
        for (int i = 1; i + (1 << (j - 1)) <= S; i ++)
            st[i][j] = std::max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
}

int query_range(int l, int r){
    int k = log2(r - l + 1);
    return std::max(st[l][k], st[r - (1 << k) + 1][k]);
}

int query(int L, int R){
    int p = pos[L], q = pos[R];
    int val = -2e9;
    if (p == q){
        for (int i = L; i <= R; i ++)
            val = std::max(val, a[i]);
        return val;
    }
    int t = query_range(p + 1, q - 1);
    val = std::max(val, t);
    val = std::max(val, std::max(pre[R], suf[L]));
    return val;
}

signed main()
{
    std::cin >> n >> m >> s;
    srand(s);
    int ans = 0;
    for (int i = 1; i <= n; i ++) a[i] = read();
    build();
    while (m --){
        int l = read() % n + 1;
        int r = read() % n + 1;
        if (l > r) std::swap(l, r);
        ans += query(l, r);
    }
    std::cout << ans;
    return 0;
}