我不要再救爷爷了呜呜呜

块长 $T=\sqrt{n}$，本地开 O2跑出来只有 4.1s。难道我们机房机子跑的比洛谷快？

#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ll;
const int maxn=2e7+5;
const int maxT=4505;
int n,Q,s,m,a[maxn],lg[maxn];
int T,bel[maxn],l[maxT],r[maxT];
int mx[maxT][maxT],pre[maxT][maxT],suf[maxT][maxT];
inline void build(){
	T=sqrt(n);
	for(int i=1;i<=n;++i){
		bel[i]=(i-1)/T+1;
	}
	m=n/T;for(int i=1;i<=m;++i){
		l[i]=(i-1)*T+1;r[i]=i*T;
	}
	if(r[m]!=n){
		++m;l[m]=r[m-1]+1;r[m]=n;
	}
	for(int i=1;i<=m;++i){
		for(int j=l[i];j<=r[i];++j){
			pre[i][j-l[i]+1]=max(pre[i][j-l[i]],a[j]);
		}
		for(int j=r[i];j>=l[i];--j){
			suf[i][j-l[i]+1]=max(suf[i][j-l[i]+1+1],a[j]);
		}
	}
	for(int i=1;i<=m;++i) mx[i][0]=suf[i][1];
	for(int i=2;i<=m;++i) lg[i]=lg[i>>1]+1;
	for(int j=1;j<=lg[m];++j){
		for(int i=1;i+(1<<j)-1<=m;++i){
			mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
		}
	}
//	for(int i=1;i<=m;++i){
//		for(int j=i;j<=m;++j){
//			mx[i][j]=max(mx[i][j-1],suf[j][1]);
//		}
//	}
}
inline int Query(int lx,int rx){
	int L=bel[lx]+1,R=bel[rx]-1;
	if(bel[lx]==bel[rx]){
		int mx=0;
		for(int i=lx;i<=rx;++i){
			mx=max(mx,a[i]);
		}
		return mx;
	}
	else if(bel[lx]+1==bel[rx]) return max(suf[L-1][lx-l[L-1]+1],pre[R+1][rx-l[R+1]+1]);
	int k=lg[R-L+1];
	return max((L<=R)*max(mx[L][k],mx[R-(1<<k)+1][k]),max(suf[L-1][lx-l[L-1]+1],pre[R+1][rx-l[R+1]+1]));
//	return 0;
}
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;
}
unsigned long long ans;
signed main(){
	scanf("%d%d%d",&n,&Q,&s);
	srand(s);
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	build();
	for(int l,r;Q;--Q){
		l=read()%n+1;r=read()%n+1;
		if(l>r) swap(l,r);
		ans+=1ull*Query(l,r);
//		cout<<ans<<endl;
	}
	printf("%llu\n",ans);
	return 0;
}