「HNOI2017」影魔

发表于
字数统计: 1,859字 | 阅读时长 ≈ 9min

「HNOI2017」影魔

题目描述

影魔，奈文摩尔，据说有着一个诗人的灵魂。事实上，他吞噬的诗人灵魂早已成千上万。千百年来，他收集了各式各样的灵魂，包括诗人、牧师、帝王、乞丐、奴隶、罪人，当然，还有英雄。

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

奈文摩尔有 $n$ 个灵魂，他们在影魔宽广的体内可以排成一排，从左至右标号 $1$ 到 $n$。第 $i$ 个灵魂的战斗力为 $k_i$，灵魂们以点对的形式为影魔提供攻击力，对于灵魂对 $i, j(i i + 1$ 时，若 $\max\{k_s | i < s < j\}\le \min(k_i, k_j)$，则提供 $p_1$ 的攻击力）；另一种情况，令 $c$ 为 $k_{i + 1}, k_{i + 2}, \cdots, k_{j -1}$ 的最大值，若 $c$ 满足：$k_i < c < k_j$，或者 $k_j < c < k_i$，则会为影魔提供 $p_2$ 的攻击力，当这样的 $c$ 不存在时，自然不会提供这 $p_2$ 的攻击力；其他情况的点对，均不会为影魔提供攻击力。

影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了，他想知道，对于任意一段区间 $[a,b]$，位于这些区间中的灵魂对会为影魔提供多少攻击力，即考虑所有满足 $a\le i<j\le b$ 的灵魂对 $i, j$ 提供的攻击力之和。

顺带一提，灵魂的战斗力组成一个 $1$ 到 $n$ 的排列：$k_1, k_1, \cdots, k_n$。

输入格式

第一行四个整数 $n,m,p_1,p_2$；
第二行 $n$ 个整数数：$k_1, k_2,\cdots, k_n$；
接下来 $m$ 行,每行两个数 $a,b$，表示询问区间 $[a,b]$ 中的灵魂对会为影魔提供多少攻击力。

输出格式

共输出 $m$ 行，每行一个答案，依次对应 $m$ 个询问。

数据范围与提示

对于 $30\%$ 的数据，$1\le n, m\le 500$；
另有 $30\%$ 的数据，$p_1 = 2p_2$
对于 $100\%$ 的数据，$1\le n,m\le 200000, 1\le p_1, p_2\le 1000$。

首先简化一下题目：提供$p_1$的攻击力的区间要满足端点一个是区间最大值，另一个是区间次大值；提供$p_2$的攻击力的区间要满足其中一个端点是最大值，而另一个不是次大值。

对于第一类，考虑每个点作为区间端点且为次大值的情况，那么显然区间的另一个端点是它左边或右边第一个比它大的数。使用单调栈可以$O(n)$预处理出第$i$个数左边的第一个比它的位置$l[i]$，以及右边第一个比它大的位置$r[i]$。那么其中每有一个在$[a,b]$，就有1的贡献。

进一步转化模型，把每个$i$转为2个点$(i,l[i])$,$(i,r[i])$，那么每次询问的第一类区间个数就是左下角在$[a,a]$，右上角在$[b,b]$的矩形内的点的个数。

直接考虑第二类好像也可求？但是我是计算”其中一个端点是区间最大，另一个端点不做其他要求”的区间个数，用它来减去第一类的个数从而间接求。考虑每个数作为区间端点且为最大值的情况，那么区间的另一个端点一定落在$[l[i],i-1]\bigcup[i+1,r[i]]$中。

转换模型，每个点转为若干条横坐标为$i$的竖直线段，每次询问的就是左下角在$[a,a]$，右上角在$[b,b]$的矩形中，线段上的整点的个数。

两种类型都是扫描线的经典问题。可以考虑将询问离线，将矩形拆成前缀和相减的形式，再用线段树维护一下就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<stack>
#define MAXN 200005
#define MAXT 800005
#define ll long long
using namespace std;

char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R(){
	char s=GC;int v=0,sign=0;
	while((s!='-')&&(s>57||s<48))s=GC;
	if(s=='-')sign=1,s=GC;
	for(;s>47&&s<58;s=GC)v=v*10+s-48;
	return sign?-v:v;
}

stack<int>S;
int N,M,K[MAXN],P1,P2;
int l[MAXN],r[MAXN];
ll ans1[MAXN],ans2[MAXN],Ans[MAXN];
struct node{int l,r;}seg[MAXN];
struct line{int l,d,u,id,k;}L[MAXN*10];int cnt;
bool operator<(line a,line b){return a.l==b.l?a.id<b.id:a.l<b.l;}

int ls[MAXT],rs[MAXT],a[MAXT],b[MAXT],lazy[MAXT],tot;
ll sum[MAXT];

void update(int p){sum[p]=sum[ls[p]]+sum[rs[p]];}

void putdown(int p){
	if(!ls[p]||!rs[p])return;
	sum[ls[p]]+=(ll)(b[ls[p]]-a[ls[p]]+1)*lazy[p];
	sum[rs[p]]+=(ll)(b[rs[p]]-a[rs[p]]+1)*lazy[p];
	lazy[ls[p]]+=lazy[p];
	lazy[rs[p]]+=lazy[p];
	lazy[p]=0;
}

int Build(int l,int r){
	int p=++tot,mid=l+r>>1;
	a[p]=l;b[p]=r;
	if(l==r)return p;
	ls[p]=Build(l,mid);
	rs[p]=Build(mid+1,r);
	return p;
}

void modify(int p,int x,int y){
	if(lazy[p])putdown(p);
	if(x<=a[p]&&b[p]<=y){
		lazy[p]++;sum[p]+=b[p]-a[p]+1;
		return;
	}
	int mid=a[p]+b[p]>>1;
	if(x<=mid)modify(ls[p],x,y);
	if(y>mid)modify(rs[p],x,y);
	update(p);
}

ll getsum(int p,int x,int y){
	if(lazy[p])putdown(p);
	if(x<=a[p]&&b[p]<=y)return sum[p];
	int mid=a[p]+b[p]>>1;ll ret=0;
	if(x<=mid)ret+=getsum(ls[p],x,y);
	if(y>mid)ret+=getsum(rs[p],x,y);
	return ret;
}

int main(){
	int i,x,y;
	N=_R();M=_R();P1=_R();P2=_R();
	for(i=1;i<=N;i++)K[i]=_R();
	for(i=1;i<=M;i++)seg[i].l=_R(),seg[i].r=_R();

	for(i=1;i<=N;i++){
		while(S.size()&&K[i]>K[S.top()])r[S.top()]=i,S.pop();
		S.push(i);
	}
	while(S.size())r[S.top()]=N+1,S.pop();
	for(i=N;i;i--){
		while(S.size()&&K[i]>K[S.top()])l[S.top()]=i,S.pop();
		S.push(i);
	}
	while(S.size())l[S.top()]=0,S.pop();

	Build(1,N);
	cnt=0;
	for(i=1;i<=M;i++){
		L[++cnt]=(line){seg[i].r,seg[i].l,seg[i].r,i,1};
		L[++cnt]=(line){seg[i].l-1,seg[i].l,seg[i].r,i,-1};//l,u,d,id,k
	}
	for(i=1;i<=N;i++){
		if(l[i]+1<=i-1)L[++cnt]=(line){i,l[i]+1,i-1,0,0};
		if(i+1<=r[i]-1)L[++cnt]=(line){i,i+1,r[i]-1,0,0};
	}
	sort(L+1,L+cnt+1);
	for(i=1;i<=cnt;i++){
		if(L[i].id)ans2[L[i].id]+=(ll)L[i].k*getsum(1,L[i].d,L[i].u);
		else modify(1,L[i].d,L[i].u);
	}

	memset(lazy,0,sizeof(lazy));
	memset(sum,0,sizeof(sum));
	cnt=0;
	for(i=1;i<=M;i++){
		L[++cnt]=(line){seg[i].r,seg[i].l,seg[i].r,i,1};
		L[++cnt]=(line){seg[i].l-1,seg[i].l,seg[i].r,i,-1};//l,u,d,id,k
	}
	for(i=1;i<=N;i++){
		if(l[i])L[++cnt]=(line){i,l[i],l[i],0,0};
		if(r[i]<=N)L[++cnt]=(line){i,r[i],r[i],0,0};
	}
	sort(L+1,L+cnt+1);
	for(i=1;i<=cnt;i++){
		if(L[i].id)ans1[L[i].id]+=(ll)L[i].k*getsum(1,L[i].d,L[i].u);
		else modify(1,L[i].d,L[i].u);
	}

	for(i=1;i<=M;i++)ans2[i]-=ans1[i];
	for(i=1;i<=M;i++)Ans[i]=(ll)P1*ans1[i]+(ll)P2*ans2[i];
	for(i=1;i<=M;i++)printf("%lld\n",Ans[i]);
}