[HNOI2017]影魔

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：

给定 \(n\) 个数的排列，\(m\) 次询问，每次询问询问一个区间内所有子区间的贡献。

每个区间如果两个端点分别是最大值和次大值，我们就算 \(P1\) 的贡献。

如果两个端点一个是最大值，一个不是次大值，我们就算 \(P2\) 的贡献。

\(\text{Solution:}\)

将询问离线，处理出以 \(i\) 结尾的询问的答案。

考虑怎样的点 \(j(j<i)\) 满足它能与 \(i\) 组成区间 \(i\) ，\(j\) 分别是最大值与次大值或非次大值。

钦定 \(a[i]\) 比 \(a[j]\) 大，那么当 \(a[j]\) 为左边单调减的波峰的时候与 \(a[i]\) 有贡献 \(p1\) ，当 \(a[j]\) 为左边两个单调减的波峰之间的时候与 \(a[i]\) 有贡献 \(p2\) 。

维护单调减的波峰可以用单调栈。

由于钦定了 \(a[i] > a[j]\) 所以要倒过来再搞一遍。

像这种区间上不好直接维护的东西，可以考虑离线，讨论时要讨论清楚哪种点有贡献。

\(\text{Source:}\)

#include<vector>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>using namespace std;#define LL long long
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define GO debug("GO\n")inline int rint() {
register int x = 0, f = 1; register char c;
while (!isdigit(c = getchar())) if (c == '-') f = -1;
while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar()));
return x * f;
}template<typename T> inline void chkmin(T &a, T b) { a > b ? a = b : 0; }
template<typename T> inline void chkmax(T &a, T b) { a < b ? a = b : 0; }const int N = 2e5 + 10;int n,m,p1,p2;
int a[N];
vector<pair<int,int> >Q,QR[N];
LL ans[N];namespace SGT {
#define ls (x<<1)
#define rs (x<<1|1)
LL sum[N * 4], tag[N * 4];
void init() {
memset(sum, 0, sizeof sum);
memset(tag, 0, sizeof tag);
}
void pu(int x) {
sum[x] = sum[ls] + sum[rs];
}
void pd(int x, int l, int r) {
if (tag[x]) {
int mid = (l + r) >> 1;
sum[ls] += tag[x] * (mid - l + 1);
tag[ls] += tag[x];
sum[rs] += tag[x] * (r - mid);
tag[rs] += tag[x];
tag[x] = 0;
}
}
void Add(int L, int R, int val, int x = 1, int l = 1, int r = n) {
if (L > R) return;
if (L <= l and r <= R) {
sum[x] += val * (r - l + 1);
tag[x] += val;
return;
}
pd(x, l, r); int mid = (l + r) >> 1;
if (L <= mid) Add(L, R, val, ls, l, mid);
if (R > mid) Add(L, R, val, rs, mid + 1, r);
pu(x);
}
LL query(int L, int R, int x = 1, int l = 1, int r = n) {
if (L > R) return 0;
if (L <= l and r <= R) {
return sum[x];
}
pd(x, l, r); int mid = l + r >> 1;
LL ans = 0;
if (L <= mid) ans += query(L, R, ls, l, mid);
if (mid < R) ans += query(L, R, rs, mid + 1, r);
return ans;
}
}using SGT::Add; using SGT::query;void work() {
static int stk[N], top;
SGT::init();
top = 0;
for (int i = 1; i <= n; ++ i) {
int last = i;
while (top and a[stk[top]] <= a[i]) {
if (stk[top] + 1 < last)
Add(stk[top] + 1, last - 1, p2);
Add(stk[top], stk[top], p1);
last = stk[top--];
}
if (!top) Add(1, last - 1, p2);
else Add(stk[top] + 1, last - 1, p2);
stk[++top] = i;
for (int j = 0; j < QR[i].size(); ++ j)
ans[QR[i][j].second] += query(QR[i][j].first, i);
}
}int main(){
#ifndef ONLINE_JUDGE
freopen("xhc.in", "r", stdin);
freopen("xhc.out", "w", stdout);
#endif
n = rint(), m = rint(), p1 = rint(), p2 = rint();
for (int i = 1; i <= n; ++ i) a[i] = rint();
for (int i = 1; i <= m; ++ i){
int l = rint(), r = rint();
Q.push_back(make_pair(l, r));
}
for (int i = 0; i < m; ++ i)
QR[Q[i].second].push_back(make_pair(Q[i].first, i + 1));
work();
for (int i = 1; i <= n; ++ i)
QR[i].clear();
for (int i = 0; i < m; ++ i)
QR[n - Q[i].first + 1].push_back(make_pair(n - Q[i].second + 1, i + 1));
reverse(a + 1, a + 1 + n);
work();
for (int i = 1; i <= m; ++ i) printf("%lld\n", ans[i]);
}