link

log块长分块+块间ST表+快内前后缀最小值，同块则暴力查询

#include <bits/stdc++.h>
using namespace std;
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;
}
inline int read() {
	using namespace GenHelper;
	int a=rand_()&32767;
	int b=rand_()&32767;
	return (a<<15)|b;
}
const int maxn=2e7+5;
const int LOG=log2(maxn)+1;
const int bl=maxn/LOG+5;//有几个块
int a[maxn];//原数组
int val[bl],st[bl],ed[bl],id[maxn];
//val是块内最小，st，ed是块的左右端点，id[i]是i属于哪一块
int pre[bl][LOG],lst[bl][LOG];
//前后缀最小值
inline int MAX(int a,int b) {
	return a>b?a:b;
}
int s[bl][LOG];//块间ST表
int LG[maxn];//LG[i]表示log2(i)
inline int query(int l,int r) {
	int sb=id[l];
	int eb=id[r];
	int res=a[l];
	if(sb==eb) {
		for(int i=l; i<=r; ++i) res=MAX(res,a[i]);
		return res;
		//块内暴力查
	}
	res=MAX(pre[eb][r-st[eb]],lst[sb][l-st[sb]]);
	l=sb+1;
	r=eb-1;
	if(l>r) return res;//两块相邻，不查询ST表
	int k=LG[r-l+1];
	return MAX(res,MAX(s[l][k],s[r-(1<<k)+1][k]));
}
int l,r;
int size,len;//size是块长，len是块数
int n,m,sra;
unsigned long long ans;
signed main() {
	for(int i=2; i<maxn; ++i) LG[i]=LG[i>>1]+1;

	cin>>n>>m>>sra;
	size=log2(n);
	len=n/size;
	srand(sra);

	for(int i=1; i<=n; ++i) a[i]=read();

	//预处理
	for(int i=1; i<=len; ++i) st[i]=ed[i-1]+1,ed[i]=st[i]+size-1;
	if(ed[len]<n) st[len+1]=ed[len]+1,ed[++len]=n;
	for(int i=1; i<=len; ++i) {
		for(int j=st[i]; j<=ed[i]; ++j)
			pre[i][j-st[i]]=MAX(pre[i][j-st[i]-1],a[j]),
			id[j]=i,
			val[i]=MAX(val[i],a[j]);
		for(int j=ed[i]; j>=st[i]; --j)
			lst[i][j-st[i]]=MAX(lst[i][j-st[i]+1],a[j]);
		s[i][0]=val[i];
	}
	//ST表
	for(int j=1; j<LOG; ++j)
		for(int i=1; i+(1<<j)<=len; ++i) {
			s[i][j]=MAX(s[i][j-1],s[i+(1<<(j-1))][j-1]);
		}
	while(m--) {
		l=read()%n+1,r=read()%n+1;
		if(l<=r) ans+=query(l,r);
		else ans+=query(r,l);
	}
	cout<<ans;
	return 0;
}