标签：扫描线，树状数组，单调栈

题目

题目传送门

题目背景

影魔，奈文摩尔，据说有着一个诗人的灵魂。事实上，他吞噬的诗人灵魂早已成千上万。

千百年来，他收集了各式各样的灵魂，包括诗人、牧师、帝王、乞丐、奴隶、罪人，当然，还有英雄。

题目描述

每一个灵魂，都有着自己的战斗力，而影魔，靠这些战斗力提升自己的攻击。

奈文摩尔有 n 个灵魂，他们在影魔宽广的体内可以排成一排，从左至右标号 1 到 n。第 i个灵魂的战斗力为 k[i]，灵魂们以点对的形式为影魔提供攻击力，对于灵魂对 i， j(i

输入输出格式

输入格式

输入文件名为 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%： 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;
}

洛谷3722 [AH2017/HNOI2017]影魔

题目