Steven_Mengの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$

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// 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;
}

 评论