AC3TLE7，求助

code:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <deque>

using namespace std;

#define ull unsigned long long

const int N = 2e7 + 5;
const int PieceLength = 4780;
const int PieceCnt = N / PieceLength + 10;

int PiecePrefix[PieceCnt][PieceLength];
int PieceSuffix[PieceCnt][PieceLength];
int PieceMax[PieceCnt][PieceCnt];
int a[N];

ull sum;
int n, m, 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 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;
}

void query(int LPiece, int RPiece, int left, int right)
{
    int i;
    if (!(LPiece ^ RPiece))
    {
        ull max_ = 0;
        for (i = left; i <= right; i++)
        {
            if(a[i]>=max_)
            {
                max_=a[i];
            }
        }
        sum += max_;
        return;
    }
    else
    {
        if (LPiece + 1 == RPiece)
        {
            sum += max(PieceSuffix[LPiece][(left - 1) % n + 1], PiecePrefix[RPiece][(right - 1) % n + 1]);
        }
        else
        {
            sum += max(max(PieceSuffix[LPiece][(left - 1) % n + 1], PiecePrefix[RPiece][(right - 1) % n + 1]), PieceMax[LPiece + 1][RPiece - 1]);
        }
    }
    return;
}

void init()
{
    int i, j;
    int PieceNumber = (i - 1) / n + 1;
    int PieceIndex = (i - 1) % n + 1;
    int PieceLen = sqrt(n);
    int Piececnt = (PieceLen - 1) / n + 1;
    for (i = 1; i <= n; i++)
    {
        PiecePrefix[PieceNumber][PieceIndex] = max(PiecePrefix[PieceNumber][PieceIndex - 1], a[i]);
    }
    for (i = n; i >= 1; i--)
    {
        PieceSuffix[PieceNumber][PieceIndex] = max(PieceSuffix[PieceNumber][PieceIndex + 1], a[i]);
    }
    for (i = 1; i <= Piececnt; i++)
    {
        PieceMax[i][i] = PieceSuffix[i][1];
    }
    for (i = 1; i <= Piececnt; i++)
    {
        for (j = i + 1; j <= Piececnt; j++)
        {
            PieceMax[i][j] = max(PieceMax[i][j - 1], PieceMax[j][j]);
        }
    }
}

void work(int left, int right)
{
    if (left == right)
    {
        sum += a[left];
        return;
    }
    if (left > right)
    {
        swap(left, right);
    }
    query((left - 1) / n + 1, (right - 1) / n + 1, left, right);
}

signed main()
{
    int i, j;
    ios::sync_with_stdio(0);
    cin >> n >> m >> s;
    srand(s);
    for (i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    init();
    while (m--)
    {
        int l = read();
        int r = read();
        l = l % n + 1, r = r % n + 1;
        work(l, r);
    }
    cout << sum;
    return 0;
}

第75行（就是那个sum+=max_）那个地方注释掉后就没有TLE的点，全WA，不注释的话AC3TLE7。

Q1：不知道这条语句是间接影响了还是直接影响了 Q2：这个数据结构是理论可过的，但是交了好多次都TLE，求优化（卡常也行）