lxl卡分块rmq了吗

最后一篇题解TLE80分了

只能用笛卡尔树了吗？

顺便，珂以帮我卡卡吗？

#include<bits/stdc++.h>
using namespace std;

#define ULL unsigned long long
#define MAXN 20000005
#pragma GCC optimize (3)
#define max(a,b) (a > b ? a:b)

int n,m,nn,mm,x;
int a[MAXN];
int b[MAXN],c[MAXN],d[MAXN];
int g[MAXN];
int e[4480][20];
int p[4480];
ULL 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);
    }
}
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*32768+b;
}

inline int qiu(int l,int r)
{
    int n = r-l+1;
    if(n == 0) return 0;
    return max(e[l][g[n]],e[r-(1<<g[n])+1][g[n]]);
}

int main()
{
  scanf("%d%d",&n,&m);
    cin >> s;
    int x = clock();
    nn = sqrt(n);
    register int tt = 0;
    b[0] = 1;
    for(register int i = 1; i <= n; i ++)
    {
        tt ++;
        b[i] = b[i-1];
        if(tt == nn+1) 
        {
            tt = 1;
            b[i] ++;
        }
    }
    mm = b[n];
    g[0] = -1;
    for(int i = 1; i <= mm; i ++)
    {
        g[i] = g[i>>1] + 1;
    }

    srand_(s);
    for(register int i = 1; i <= n; i ++) {
        a[i] = read();  
    }   
    //cout<<"\n";
    for(register int i = 1; i <= n; i ++)
    {
        if(b[i] == b[i-1])
            c[i] = max(a[i],c[i-1]);
        else
            c[i] = a[i];
    }
    for(register int i = n; i >= 1; i --)
    {
        if(b[i] == b[i+1])
        {
            d[i] = max(a[i],d[i+1]);
        } else {
            d[i] = a[i];
            p[b[i]] = c[i];
            e[b[i]][0] =c[i];
            //cout<<b[i]<<" "<<p[b[i]]<<"\n";
        }
    }   
    for(int j = 1; j <= 14; j ++)
        for(register int i = 1; i <= mm; i ++)
        if(i + (1<<j) - 1 <= mm)
        {
            e[i][j] = max(e[i][j-1] , e[i+(1<<(j-1)) ][j-1]);
        }

    ULL ans = 0;
    for(register int i = 1; i <= m; i ++)
    {
    //cout<<"QAQ\n";
        int l,r;
        l = read()%n+1;
        r = read()%n+1;
        if(l > r)
            l ^= r,r ^= l,l ^= r;
        int an = 0; 
        const int bl = b[l],br = b[r];
        if(bl == br)
        {
            for(register int j = l; j <= r; ++ j)
                an = max(an,a[j]);  
        } else {
          an = max(qiu(bl+1,br-1),max(d[l],c[r]));
        }
        ans += an;
    }
    cout<<ans;
    return 0;
} 
/*
5000000 5260817 19260817
*/