其实这个每一块的前缀后缀最大可以用一个一维数组存的
by critnos @ 2020-11-29 12:20:05
be[i] 表示从 l[belong[i]]~i 的最大值，la 同理
应该会快一些，你的预处理和我的速度是没什么区别的，下面 st 表的查询也不慢，是每一块的前缀后缀最大的问题吧
by critnos @ 2020-11-29 12:26:39
@[mcyl35](/user/203623) thx
by JRzyh @ 2020-11-29 12:34:00
```cpp
#\
p\
r\
a\
g\
m\
a\
\
G\
C\
C\
\
t\
a\
r\
g\
e\
t\
(\
"\
a\
v\
x\
,\
s\
s\
e\
2\
,\
s\
s\
e\
3\
,\
s\
s\
e\
4\
,\
m\
m\
x\
"\
)
#include<bits/stdc++.h>
using namespace std;
namespace IO {
const int SIZE = (1 << 20) + 1;
char ibuf[SIZE], *iS, *iT;
inline char gc() {
return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++) : *iS++);
}
inline void qread() {}
template<class T1, class ...T2>
inline void qread(T1 &IEE, T2 &... ls) {
register T1 __ = 0, ___ = 1;
register char ch;
while (!isdigit(ch = gc())) ___ = (ch == '-') ? -___ : ___;
do {
__ = (__ << 1) + (__ << 3) + (ch ^ 48);
} while (isdigit(ch = gc()));
__ *= ___;
IEE = __;
qread(ls...);
return;
}
}
using namespace IO;
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);
}
}
using namespace GenHelper;
void srand(unsigned x)
{z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
static int a, b;
a=rand_()&32767;
b=rand_()&32767;
return a << 15 | b;
}
int max(int a,int b){return (a<b)?b:a;}
int min(int a,int b){return (a<b)?a:b;}
unsigned long long out;
int size,num,n,m,s,a[20000008],block[4480],l[4480],r[4480],belong[20000008],be[20000008],la[20000008],st[4480][15];
inline int query(int l,int r)
{
if(r<l)return -114514;
int k=log2(r-l+1);
return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main()
{
qread(n,m,s);
srand(s);
for(register int i=1;i<=n;i++)
{
a[i]=read();
}
size=sqrt(n);
num=n/size+(n%size!=0);
l[1]=1;
r[1]=size;
for(register int i=2;i<=num;i++)
{
l[i]=r[i-1]+1;
r[i]=min(l[i]+size-1,n);
}
for(register int i=1;i<=num;i++)
{
for(register int j=l[i];j<=r[i];j++)
{
block[i]=max(block[i],a[j]);
belong[j]=i;
}
be[l[i]]=a[l[i]];
for(register int j=l[i]+1;j<=r[i];j++)
{
be[j]=max(be[j-1],a[j]);
}
la[r[i]]=a[r[i]];
for(register int j=r[i];j>=l[i];j--)
{
la[j]=max(la[j+1],a[j]);
}
}
for(register int i=1;i<=num;i++)
{
st[i][0]=block[i];
}
for(register int j=1;j<=log2(num);j++)
{
for(register int i=1;i+(1<<j)-1<=num;i++)
{
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
while(m--)
{
int x=read()%n+1,y=read()%n+1,l1=min(x,y),r1=max(x,y),ans=0;
if(belong[l1]==belong[r1])
{
for(int i=l1;i<=r1;i++)
{
ans=max(a[i],ans);
}
out+=ans;
continue;
}
ans=max(ans,la[l1]);
ans=max(ans,be[r1]);
ans=max(ans,query(belong[l1]+1,belong[r1]-1));
out+=ans;
}
printf("%llu",out);
return 0;
}
```
@[Zhaoyuhang2008](/user/242524) [卡过了](https://www.luogu.com.cn/record/42830173)
by Yuanchenpu @ 2020-11-29 12:45:18
@[Yuanchenpu](/user/60554) thx!
by JRzyh @ 2020-11-29 12:48:22