Steven_Meng's Blog

传送门

毒瘤$lxl$数据结构题。

首先，考虑传统的$ST$表，发现$n=2000000$，空间开不下。

考虑分块$+ST$表，每个块里面存的是块内前缀最大值，后缀最大值。

最后$ST$表查询的是块的最大值。

注意查询的区间$[l,r]$在同一块内需要暴力搞一下，发现数据随机，所以出现这种情况不多。

为了卡常数，需要预处理$\log$，注意查询时要特判$l>r$

还有一点非常玄学，块大小要开$5000$，要不然会$TLE$

时间复杂度$O(n+\log5000 \times 5000+a \times 5000 + b)$，其中$a$表示查询区间$[l,r]$在同一块的情况总数，$b$表示查询区间$[l,r]$不在同一块的情况总数。

空间复杂度$O(n+\log5000 \times 5000)$，反正不会$MLE$

注意此代码常数蜃大，提交前需要洗一把脸。

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 20000005
#define BMAX 5005 //块的最大值
#define STMAX 13
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
namespace GenHelper{
    unsigned z1,z2,z3,z4,b;
    inline 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;
    return (rand_()&32767)*32768+(rand_()&32767);
}
static int Block_L[MAXN],Block_R[MAXN],a[MAXN];
static int id[MAXN],lg[BMAX];
int Size;
//ST表处理Block最大值
static int ST[STMAX][BMAX];
inline void Init_ST(int n){
    for (register int i=1;i<STMAX;++i){
        for (register int j=1;j+(1<<i)-1<BMAX;++j){
            ST[i][j]=max(ST[i-1][j],ST[i-1][j+(1<<(i-1))]);
        }
    }
}
inline int Query(int l,int r){
    if (l>r) return 0;
    int k=lg[r-l+1];
    return max(ST[k][l],ST[k][r-(1<<k)+1]);
}
inline void Init(int n){
    for (register int i=1;i<=n;++i){//前缀和
        Block_L[i]=(((id[i]-1)*Size+1)==i)?a[i]:max(Block_L[i-1],a[i]);
    }
    for (register int i=n;i>=1;--i){//后缀和
        Block_R[i]=(min(id[i]*Size,n)==i)?a[i]:max(Block_R[i+1],a[i]);
    }
    for (register int i=1;i<=n;++i){//整块的最大值
        ST[0][id[i]]=max(ST[0][id[i]],a[i]);
    }
    Init_ST(n);
}
#define ull unsigned long long
int main(){
    int n=read(),m=read(),s=read();
    srand(s);
    Size=5000;
    for (register int i=1;i<=n;++i){
        a[i]=_read();
        id[i]=(i-1)/Size+1;
    }
    lg[0]=-1;
    for (register int i=1;i<BMAX;++i) lg[i]=lg[i>>1]+1;
    Init(n);
    ull ans=0;
    while (m--){
        int l=_read()%n+1,r=_read()%n+1;
        if (l>r) swap(l,r);
        if (id[l]==id[r]){//Brute_Force
            int maxn=0;
            for (register int i=l;i<=r;++i){
                maxn=max(maxn,a[i]);
            }
            ans+=(ull)maxn;
        }
        else {
            ans+=(ull)(max(max(Block_L[r],Block_R[l]),Query(id[l]+1,id[r]-1)));
        }
    }
    cout<<ans<<endl;
}