题解：P3722 [AHOI2017/HNOI2017] 影魔
Lucyna_Kushinada
·
·
题解
P3722 [AHOI2017/HNOI2017] 影魔
题意
给定长度为 n 的排列 a，定义一个二元组 (i,j) （其中 i<j）会产生贡献，分为下面三种情况：
-
情况一：如果满足 \max_{k=i+1}^{j-1}a_k<\min(a_i,a_j)，则会产生 p_1 的贡献。
-
情况二：如果满足 a_i<\max_{k=i+1}^{j-1}a_k<a_j，则会产生 p_2 的贡献。
-
情况三：如果满足 a_j<\max_{k=i+1}^{j-1}a_k<a_i，则会产生 p_2 的贡献。
进行 m 次询问，每次询问一个区间 [l,r]，问该区间中所有 (i,j) 的贡献之和。
题解
没什么思维难度，只需要不断地推式子就行了。
-
情况一：如果满足 \max_{k=i+1}^{j-1}a_k<\min(a_i,a_j)，则会产生 p_1 的贡献。
-
情况二：如果满足 a_i<\max_{k=i+1}^{j-1}a_k<a_j，则会产生 p_2 的贡献。
-
情况三：如果满足 a_j<\max_{k=i+1}^{j-1}a_k<a_i，则会产生 p_2 的贡献。
套路地，不考虑 (i,j) 中有哪些 k 产生贡献，而是反过来看 k 能对哪些 (i,j) 产生贡献。
单调栈预处理出 a_i 左边第一个比 a_i 大的数的下标 L_i，如果没有则 L_i=0，以及右边第一个比 a_i 大的数的下标 R_i，如果没有则 R_i=n+1。
故当 a_k 作为 (i+1,j-1) 区间最大值当且仅当 \begin{cases}
i+1>L_k \\
j-1<R_k
\end{cases}，解得 \begin{cases}
i\ge L_k \\
j\le R_k
\end{cases}。
满足情况一时，必须有 \begin{cases}
a_i>a_k \\
a_j<a_k
\end{cases}，可看作 \begin{cases}
i\le L_k \\
j\ge R_k
\end{cases}，结合上式，此时只能 \begin{cases}
i=L_k \\
j=R_k
\end{cases}。
满足情况二时，必须有 \begin{cases}
i\neq L_k\\
j\ge R_k
\end{cases}，推得 \begin{cases}
i>L_k\\
j=R_k
\end{cases}。
满足情况三时，同理可推得 \begin{cases}
i=L_k\\
j<R_k
\end{cases}。
那么对于一个询问 [l,r]，它的答案就有四个组成：
\displaystyle ans_1=\sum_{i=l}^r [l\le L_i][R_i \le r]p_1
\displaystyle ans_2=\sum_{i=l}^r [R_i\le r](i-\max(L_i+1,l))p_2
\displaystyle ans_3=\sum_{i=l}^r [l\le L_i](\max(R_i-1,r)-i)p_2
\displaystyle ans_4=(r-l)p_1
这时候果断对 r 按 1\sim n 扫描线，可以求出 ans_1 和 ans_2，具体是把式子继续拆开，用树状数组维护即可。
$ans_4$ 是相邻元素产生的贡献，由于上面的推理默认存在 $k$，所以会遗漏这种 $i,j$ 相邻的情况。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()
#define N 202506
#define int long long
int n,m,p1,p2,a[N],L[N],R[N];
int st[N],tp,ans[N];
vector<pr>e[N],g[N];
vector<int>rr[N],ri[N],ll[N],li[N];
inline void init(){
rep(i,1,n){
while(tp&&a[i]>a[st[tp]]){
R[st[tp]]=i;
tp--;
}
st[++tp]=i;
}
while(tp){
R[st[tp]]=n+1;
tp--;
}
per(i,1,n){
while(tp&&a[i]>a[st[tp]]){
L[st[tp]]=i;
tp--;
}
st[++tp]=i;
}
while(tp){
L[st[tp]]=0;
tp--;
}
}
struct BIT{
#define lb(x) (x&-x)
int tr[N];
inline void init(){
rep(i,0,n){
tr[i]=0;
}
}
inline void upd(int k,int d){
while(k<=n){
tr[k]+=d;
k+=lb(k);
}
}
inline int ask(int k){
int ans=0;
while(k){
ans+=tr[k];
k-=lb(k);
}
return ans;
}
#undef lb
}t1,t2,t3,ti;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>p1>>p2;
rep(i,1,n){
cin>>a[i];
}
init();
rep(i,1,n){
rr[R[i]].pb(L[i]);
ri[R[i]].pb(i);
ll[L[i]].pb(R[i]);
li[L[i]].pb(i);
}
rep(i,1,m){
int l,r;
cin>>l>>r;
g[l].pb({r,i});
e[r].pb({l,i});
ans[i]=(r-l)*p1;
}
rep(i,1,n){
for(int l:rr[i]){
if(l){
t1.upd(l,1);
}
t2.upd(l+1,1);
t3.upd(l+1,l+1);
}
for(int x:ri[i]){
ti.upd(x,x);
t2.upd(x+1,-1);
}
for(pr u:e[i]){
ans[u.se]+=(t1.ask(n)-t1.ask(u.fi-1))*p1;
ans[u.se]+=(ti.ask(n)-ti.ask(u.fi-1))*p2;
ans[u.se]-=t2.ask(u.fi)*u.fi*p2;
ans[u.se]-=(t3.ask(n)-t3.ask(u.fi))*p2;
}
}
t1.init();
t2.init();
t3.init();
ti.init();
per(i,1,n){
for(int r:ll[i]){
t2.upd(r-1,1);
t3.upd(r-1,r-1);
}
for(int x:li[i]){
if(x-1){
t2.upd(x-1,-1);
}
ti.upd(x,x);
}
for(pr u:g[i]){
ans[u.se]-=ti.ask(u.fi)*p2;
ans[u.se]+=(t2.ask(n)-t2.ask(u.fi-1))*u.fi*p2;
ans[u.se]+=t3.ask(u.fi-1)*p2;
}
}
rep(i,1,m){
cout<<ans[i]<<"\n";
}
return 0;
}
```