标签：扫描线，树状数组，单调栈
题目
题目背景
影魔，奈文摩尔，据说有着一个诗人的灵魂。 事实上，他吞噬的诗人灵魂早已成千上万。
千百年来，他收集了各式各样的灵魂，包括诗人、 牧师、 帝王、 乞丐、 奴隶、 罪人，当然，还有英雄。
题目描述
每一个灵魂，都有着自己的战斗力，而影魔，靠这些战斗力提升自己的攻击。
| 奈文摩尔有 n 个灵魂，他们在影魔宽广的体内可以排成一排，从左至右标号 1 到 n。第 i个灵魂的战斗力为 k[i]，灵魂们以点对的形式为影魔提供攻击力，对于灵魂对 i， j(i<j)来说，若不存在 ks大于 k[i]或者 k[j]，则会为影魔提供 p1 的攻击力（可理解为： 当 j=i+1 时，因为不存在满足 i<s<j 的 s，从而 k[s]不存在，这时提供 p1 的攻击力；当 j>i+1 时，若max{k[s] | i<s<j}<=min{k[i],k[j]} ， 则 提 供 p1 的 攻 击 力 ）； 另 一 种 情 况 ， 令 c 为k[i+1],k[i+2],k[i+3]……k[j-1]的最大值，若 c 满足： k[i]<c<k[j],或者 k[j]<c<k[i]，则会为影魔提供 p2 的攻击力，当这样的 c 不存在时，自然不会提供这 p2 的攻击力；其他情况的点对，均不会为影魔提供攻击力。 |
影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了，他想知道，对于任意一段区间[a,b]， 1<=a<b<=n，位于这些区间中的灵魂对会为影魔提供多少攻击力，即考虑 所有满足a<=i<j<=b 的灵魂对 i,j 提供的攻击力之和。
顺带一提，灵魂的战斗力组成一个 1 到 n 的排列： k[1],k[2],…,k[n]。
输入输出格式
输入格式
输入文件名为 sf.in。
第一行 n,m,p1,p2
第二行 n 个数： k[1],k[2],…,k[n]
接下来 m 行， 每行两个数 a,b， 表示询问区间[a,b]中的灵魂对会为影魔提供多少攻击力。
输出格式
输出文件名为 sf.out
共输出 m 行，每行一个答案，依次对应 m 个询问。
输入输出样例
输入样例#1
10 5 2 3
7 9 5 1 3 10 6 8 2 4
1 7
1 9
1 3
5 9
1 5
输出样例#1
30
39
4
13
16
说明
30%： 1<= n,m <= 500。
另 30%: p1=2* p2。
100%:1 <= n,m <= 200000； 1 <= p1,p2 <= 1000。
题意
给定长度为n的序列ai和q个询问
每个询问有两个端点l,r
如果两个端点分别是这个区间的最大值和次大值，有p1的贡献，否则如果其中一个端点是这个区间的最大值，有p2的贡献
问所有被区间完全包含的区间的贡献和
分析
一开始看这题，网上全是线段树做法的题解，还有主席树的，果然每年只要AHOI参加的那个省省选题都很考验码力
新版AHOI数据结构大赛
回归正题，我用的是树状数组+扫描线+单调栈的做法
我们考虑对答案产生贡献的情况
对于点x，找出左右各比它大的第一个点所在位置le,ri
-
只有左端点为le，右端点为ri才会产生p1的贡献
-
左端点在(le,x)，右端点为ri产生p2的贡献
-
左端点在le，右端点在(x,ri)产生p2的贡献
-
左右端点差值为1的情况产生p1的贡献（可以O(1)计算，之后就不再多讨论了）
那么我们可以抽象到二维平面上，分别把矩形和询问排序，做一遍扫描线，使用树状数组快速求和维护
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=2e5+6;
int n,m,p1,p2,S[maxn]={0},top=1,ls,a[maxn],le[maxn],ri[maxn],n1=1,n2=1;
ll ans[maxn],c1[maxn],c2[maxn];
struct node{int l,r,x,b,z;}s1[maxn<<1],s2[maxn<<2];
inline bool operator < (node a,node b){return a.x<b.x;}//将矩形和点按x升序排列
void modify(int x,int y){if(x)for(int i=x;i<=n;i+=i&(-i))c1[i]+=y,c2[i]+=1ll*x*y;}//树状数组修改
inline ll query(int x){
ll re=0;
for(int i=x;i;i-=i&(-i))re+=(x+1)*c1[i]-c2[i];
return re;
}//树状数组求和
int main()
{
n=read(),m=read(),p1=read(),p2=read();
a[0]=a[n+1]=n+1;
rep(i,1,n)a[i]=read();
rep(i,1,n+1){
while(a[S[top]]<a[i])ri[S[top--]]=i;
le[i]=S[top];S[++top]=i;
}//单调栈求左右各比a[i]大的第一个点所在位置
rep(i,1,m){
int l=read(),r=read();ans[i]+=(r-l)*p1;
s1[i]=(node){l,r,l-1,i,-1};
s1[i+m]=(node){l,r,r,i,1};
}//将询问离线存储
sort(s1+1,s1+m+m+1);
rep(i,1,n){
if(le[i]&&ri[i]<=n)s2[++ls]=(node){le[i],le[i],ri[i],0,p1};
if(le[i]&&ri[i]>i+1)s2[++ls]=(node){i+1,ri[i]-1,le[i],0,p2};
if(le[i]+1<i&&ri[i]<=n)s2[++ls]=(node){le[i]+1,i-1,ri[i],0,p2};
}//建立矩形
sort(s2+1,s2+ls+1);
while(!s1[n1].x)n1++;
rep(i,1,n){
if(n1>m+m)break;
while(n2<=ls&&s2[n2].x==i){
modify(s2[n2].r+1,-s2[n2].z);
modify(s2[n2].l,s2[n2].z),n2++;
}
while(n1<=m+m&&s1[n1].x==i){
ans[s1[n1].b]+=s1[n1].z*(query(s1[n1].r)-query(s1[n1].l-1));
n1++;
}
}//扫描线求询问的矩形面积和
rep(i,1,m)printf("%lld\n",ans[i]);
return 0;
}
