TLE 80pts求助，状压rmq

#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
//#include<ext/pb_ds/priority_queue.hpp>
#define umap unordered_map
#define mset multiset
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(),(x).end()
#define tmax(a,b) (a)=max((a),(b))
#define tmin(a,b) (a)=min((a),(b))
#define dbg(x) cout<<"line "<<__LINE__<<" : "<<#x<<"="<<x<<"\n"
#define cout(x) cout<<fixed<<setprecision(x)

using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;typedef pair<int,int> PII;
typedef vector<int> vi;typedef vector<PII> vp;
typedef array<int,3> a3;typedef vector<a3> va3;

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;
}

const int N=2e7+5,M=N/24,Logn=20+5,Inf=1e9+7;  //M=N/log(N),Logn=log(M)
int n,m,a[N];
unsigned long long ans;
int T,tot,bel[N],ma[M][Logn],bm[N],pre[N],suf[N];

int pos(int i){
	return i-(bel[i]-1)*T+1;
}
void init(){
	T=log2(n);
	int stk[35],top;
	for(int i=1;i<=n;i++){
		if((i-1)%T==0){
			tot++;
		}
		bel[i]=tot;
		tmax(ma[tot][0],a[i]);
	}
	for(int i=1;i<=n;i++){
		if(bel[i]!=bel[i-1]){
			top=0;
		}else{
			bm[i]=bm[i-1];
		}
		while(top&&a[stk[top]]<=a[i]){
			bm[i]&=~(1<<pos(stk[top--]));
		}
		stk[++top]=i;
		bm[i]|=(1<<pos(i));
	}
	for(int i=1;i<=n;i++){
		if(bel[i]!=bel[i-1]){
			pre[i]=a[i];
		}else{
			pre[i]=max(pre[i-1],a[i]);
		}
	}
	for(int i=n;i>=1;i--){
		if(bel[i]!=bel[i+1]){
			suf[i]=a[i];
		}else{
			suf[i]=max(suf[i+1],a[i]);
		}
	}
	for(int j=1;j<=__lg(tot);j++){
		for(int i=1;i+(1<<j)-1<=tot;i++){
			ma[i][j]=max(ma[i][j-1],ma[i+(1<<j-1)][j-1]);
		}
	}
}
inline int query(int l,int r){
	if(bel[l]==bel[r]){
		return a[l+__builtin_ctz(bm[r]>>pos(l))];
	}
	if(bel[l]+1<=bel[r]-1){
		int s=__lg(bel[r]-bel[l]-1);
		return max({suf[l],pre[r],ma[bel[l]+1][s],ma[bel[r]-(1<<s)][s]});
	}else{
		return max(suf[l],pre[r]);
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int s;
	cin>>n>>m>>s;
	_srand(s);
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	init();
	for(int l,r;m--;){
		l=read()%n+1,r=read()%n+1;
		if(l>r) swap(l,r);
		ans+=query(l,r);
	}
	cout<<ans;
	return 0;
}
/*

*/