真心巧妙，不看题解准做不出(之前题解都看不懂QwQ)
这道题貌似有许多的做法，都不费，主席树的话不知道怎么搞，于是建了 $3$ 棵线段树，实测是不会炸的。
30分做法：
小学生都能轻易想出来的解法，对于一个询问的区间，暴力枚举其子区间，然后按照题面的要求算贡献，区间最大值可以用 $ST$ 表预处理，复杂度爆炸，但是仍然可以拿到 $30$ 暴力分。
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
|
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
const int N=1e5+2;
const int LogN=23;
const int inf=1e9+9;
int v[N],n,m,p1,p2;
struct {
int logs[N],f[N][LogN+2];
inline void make(){
logs[0]=-1;
for(int i=1;i<=n;++i)
f[i][0]=v[i],logs[i]=logs[i>>1]+1;
for(int j=1;j<=LogN;++j)
for(int i=1;i+(1<<j)-1<=n;++i)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int query(int x,int y){
int ans=logs[y-x+1];
return max(f[x][ans],f[y-(1<<ans)+1][ans]);
}
}T;
template <typename _Tp> inline void IN(_Tp&x){
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
if(flag)x=-x;
}
int main(){
IN(n),IN(m),IN(p1),IN(p2);
for(int i=1;i<=n;++i)IN(v[i]);
T.make();
for(int i=1;i<=m;++i){
int l,r,ans=0;
IN(l),IN(r);
for(int a=l;a<=r;++a)
for(int b=a+2;b<=r;++b){
int sum=T.query(a+1,b-1);
if(v[a]>=sum&&v[b]>=sum)ans+=p1;
if((v[a]<sum&&sum<v[b])||(v[b]<sum&&sum<v[a]))ans+=p2;
}
printf("%dn",ans+(r-l)*p1);
}
return 0;
}
|
100分做法
对于一个点 $i$ ，我们设 $lmax[i]$ 为 $i$ 向左走遇到的第一个大于自己的数(没有的话为 $0$) ，同样的，设 $rmax[i]$ 为 $i$ 向右走遇到的第一个大于自己的数(没有的话为 $n+1$) 。这两个数组比较容易求出，搞个单调栈求就好。
1
2
3
4
5
6
7
8
9
10
|
top=0,stack[0]=0;
for(int i=1;i<=n;++i){
while(top&&k[stack[top]]<k[i])--top;
lmax[i]=stack[top],stack[++top]=i;
}
top=0,stack[0]=n+1;
for(int i=n;i>=1;--i){
while(top&&k[stack[top]]<k[i])--top;
rmax[i]=stack[top],stack[++top]=i;
}
|
然后可以发现，如果枚举点 $i$ 的话，有了上面的两个数组后有关 $i$ 的贡献就好求些了，首先我们可以知道 $i$ 是区间 $[lmax[i]+1,rmax[i]-1]$ 的最大值，那么对于每种贡献：
- 如果 $lmax[i]$ 和 $rmax[i]$ 都在当前询问区间内，那么就可以做出 $p_1$ 的贡献。
- 如果 $lmax[i]$ 在当前询问区间中，那么显然 $lmax[i]$ 为区间 $[lmax[i],rmax[i]-1]$ 的最大值，这个时候右端点如果在 $[i+1,rmax[i]-1]$ 区间中，那么可以保证右端点不是 $[lmax[i],rmax[i]-1]$ 的次大值，这个时候可以产生多个 $p_2$ 的贡献。
- 如果 $rmax[i]$ 在当前询问区间中，那么显然当左端点为 $[lmax[i]+1,i-1]$ 的时候该子区间均能产生 $p_2$ 的贡献，原因跟上面一样的。
但是这样的话复杂度依旧是 $O(n^2)$ 的，所以还要优化。
考虑用线段树维护，我们离线处理询问，把每个询问按左端点排个序，然后反着扫一遍，如果遇到了一个点 $x$ ，它是 某个点/某些点 的 $lmax$ ，假设 $x$ 是 $i$ 的 $lmax$ ，那么我们依次在第一颗线段树中实现区间加：将 $[i+1,rmax[i]-1]$ 区间正题加上 $p_2$ ，因为当前的左端点为 $x$ ，这个时候我们将要计算的是所有的左端点为 $x$ 的区间对答案的贡献，因为对于 $i$ 来说右端点的范围就是 $[i+1,rmax[i]-1]$，这些区间均可以做出贡献，于是都在线段树中加上。当然在做贡献的之前不要忘记判断 $i+1<rmax[i]$ ，如果不满足的话就没有右端点了……
那么接下来讨论怎么计算 $p_1$ 的贡献，对于询问区间来说，现在我们确定了左端点为 $x$ ，这个时候当右端点落在 $[rmax[i],n+1]$ 的时候询问区间都可以算上 $[lmax[i],rmax[i]]$ 区间的贡献，也就是 $p_1$ 的贡献，于是我们可以在另一个线段树中将 $[rmax[i],n+1]$ 全都加上 $p_1$ 即可。
按照上面的方法，再正着扫一遍计算 $rmax$ 的情况就好，当然反着扫的时候就不要算 $p_1$ 的贡献了，不然就会重复了，想想就可以明白。最后就是一定要开 $longlong$ 。
Code:
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
大专栏 |