4826: [Hnoi2017]影魔
https://lydsy.com/JudgeOnline/problem.php?id=4826
分析：
莫队+单调栈+st表。
考虑如何O(1)加入一个点，删除一个点，类似bzoj4540。然后就可以莫队了。复杂度$O(n\sqrt n)$
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; char buf[], *p1 = buf, *p2 = buf;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline int read() {
int x=,f=;char ch=nc();for(;!isdigit(ch);ch=nc())if(ch=='-')f=-;
for(;isdigit(ch);ch=nc())x=x*+ch-'';return x*f;
} const int N = ;
struct Edge{
int l, r, bel, id;
bool operator < (const Edge &A) const {
return bel == A.bel ? r < A.r : bel < A.bel;
}
}Q[N];
int cnt[N], a[N], f[N][], Log[N];
int sum1R[N], sum1L[N], sum2R[N], sum2L[N], q[N], mxL[N], mxR[N];
int P1, P2, L, R, n, m;
LL ans[N], Ans = ; int getmax(int l,int r) {
int k = Log[r - l + ];
int p1 = f[l][k], p2 = f[r - ( << k) + ][k];
return a[p1] > a[p2] ? p1 : p2;
} void updR(int x,int f) {
if (L >= R) { Ans = ; return ; }
int p = getmax(L, R - ), p2 = max(mxL[x], p);
Ans += (sum1L[R - ] - sum1L[p2] + ) * P1 * f;
Ans += (sum1L[p2] - sum1L[p]) * P2 * f;
Ans += (sum2L[R - ] - sum2L[p2]) * P2 * f;
if (L > mxL[x]) Ans += (p2 - L) * P2 * f;
} void updL(int x,int f) {
if (L >= R) { Ans = ; return ; }
int p = getmax(L + , R), p2 = min(mxR[x], p);
Ans += (sum1R[L + ] - sum1R[p2] + ) * P1 * f;
Ans += (sum1R[p2] - sum1R[p]) * P2 * f;
Ans += (sum2R[L + ] - sum2R[p2]) * P2 * f;
if (R < mxR[x]) Ans += (R - p2) * P2 * f;
} int main() {
n = read(), m = read();P1 = read(), P2 = read();
int B = sqrt(n);
for (int i = ; i <= n; ++i) a[i] = read(), f[i][] = i;
for (int j = ; ( << j) <= n; ++j) {
for (int i = ; i + ( << j) - <= n; ++i) {
int p1 = f[i][j - ], p2 = f[i + ( << (j - ))][j - ];
f[i][j] = a[p1] > a[p2] ? p1 : p2;
}
}
Log[] = -;
for (int i = ; i <= n; ++i) Log[i] = Log[i >> ] + ;
a[] = a[n + ] = 1e9;
int l = , r = ; q[] = ;
for (int i = ; i <= n; ++i) {
while (l <= r && a[i] > a[q[r]]) r --;
q[++r] = i;
int j = q[r - ]; mxL[i] = j;
sum2L[i] = sum2L[j] + (i - j - ); sum1L[i] = sum1L[j] + ;
}
l = , r = ; q[] = n + ;
for (int i = n; i >= ; --i) {
while (l <= r && a[i] > a[q[r]]) r --;
q[++r] = i;
int j = q[r - ]; mxR[i] = j;
sum2R[i] = sum2R[j] + (j - i - ); sum1R[i] = sum1R[j] + ;
}
for (int i = ; i <= m; ++i) {
Q[i].l = read(), Q[i].r = read(), Q[i].bel = (Q[i].l - ) / B + , Q[i].id = i;
}
sort(Q + , Q + m + );
L = , R = ;
for (int i = ; i <= m; ++i) {
while (L > Q[i].l) L --, updL(L, );
while (R < Q[i].r) R ++, updR(R, );
while (L < Q[i].l) updL(L, -), L ++;
while (R > Q[i].r) updR(R, -), R --;
ans[Q[i].id] = Ans;
}
for (int i = ; i <= m; ++i) printf("%lld\n", ans[i]);
return ;
}
sol2：
每个点i找到左边右边第一个比它大的点，设为x,y，那么x,y会产生P1的贡献，x和[i+1,y-1]，y和[x+1,i-1]会产生P2的贡献，把它们看做是平面上的点，然后转化为二维数点问题。
询问区间L,R，就是询问横坐标在[L,R]的，纵坐标也在[L,R]的点有多少个。有一个问题：(y,x+1)这个点是否和(x+1,y)的贡献一样？就是这两个数哪个在前面的问题，因为询问总是一个关于直线y=x对称的一个矩形，而(y,x+1)和(x+1,y)也关于y=x对称，所以这两个点怎么放都行。
然后离线+扫描线+线段树就行了（可以标记永久化）。复杂度$O(nlogn)$
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
#define Root 1, n, 1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ;
struct Node{
int p, l, r, id, w;
bool operator < (const Node &A) const { return p < A.p; }
}q[N * ], A[N * ];
int L[N], R[N], sk[N], a[N];
LL sum[N << ], tag[N << ], ans[N]; void update(int l,int r,int rt,int L,int R,int v) {
sum[rt] += 1ll * (R - L + ) * v;
if (L == l && r == R) {
tag[rt] += v; return ;
}
int mid = (l + r) >> ;
if (R <= mid) update(lson, L, R, v);
else if (L > mid) update(rson, L, R, v);
else update(lson, L, mid, v), update(rson, mid + , R, v);
}
LL query(int l,int r,int rt,int L,int R,LL t) {
if (L == l && r == R) return sum[rt] + 1ll * (R - L + ) * t;
int mid = (l + r) >> ;
if (R <= mid) return query(lson, L, R, t + tag[rt]);
else if (L > mid) return query(rson, L, R, t + tag[rt]);
else return query(lson, L, mid, t + tag[rt]) + query(rson, mid + , R, t + tag[rt]);
}
int main() {
int n = read(), m = read(), P1 = read(), P2 = read();
for (int i = ; i <= n; ++i) a[i] = read();
for (int top = , i = ; i <= n; ++i) {
while (top && a[i] > a[sk[top]]) top --;
sk[++top] = i;
L[i] = sk[top - ];
}
sk[] = n + ;
for (int top = , i = n; i >= ; --i) {
while (top && a[i] > a[sk[top]]) top --;
sk[++top] = i;
R[i] = sk[top - ];
}
int tot = ;
for (int i = ; i <= n; ++i) {
if (L[i] && R[i] <= n) A[++tot] = (Node){R[i], L[i], L[i], , P1};
if (L[i] && R[i] > i + ) A[++tot] = (Node){L[i], i + , R[i] - , , P2};
if (R[i] <= n && i > L[i] + ) A[++tot] = (Node){R[i], L[i] + , i - , , P2};
}
for (int i = ; i <= m; ++i) {
int l = read(), r = read();
q[i] = (Node){l - , l, r, i, -};
q[i + m] = (Node){r, l, r, i, };
ans[i] += 1ll * (r - l) * P1;
}
sort(q + , q + m + m + );
sort(A + , A + tot + );
int now = ;
while (A[now].p <= ) now ++;
for (int i = ; i <= m + m; ++i) {
while (now <= tot && A[now].p <= q[i].p) {
update(Root, A[now].l, A[now].r, A[now].w); now ++;
}
ans[q[i].id] += 1ll * query(Root, q[i].l, q[i].r, ) * q[i].w;
}
for (int i = ; i <= m; ++i) printf("%lld\n", ans[i]);
return ;
}