HNOI 2017 影魔（扫描线+线段树+树状数组）

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

Description

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

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

奈文摩尔有n个灵魂，他们在影魔宽广的体内可以排成一排，从左至右标号1到n。第i个灵魂的战斗力为k[i]，灵魂们以点对的形式为影魔提供攻击力，对于灵魂对i，j (i < j) 来说，若不存在k[s] (i < s < j) 大于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]。

Input

第一行n,m,p1,p2

第二行n个数：k[1],k[2],…,k[n]

接下来m行，每行两个数a,b，表示询问区间[a,b]中的灵魂对会为影魔提供多少攻击力。

Output

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

Sample Input

10 5 2 3

7 9 5 1 3 10 6 8 2 4

1 7

1 9

1 3

5 9

1 5

Sample Output

30

39

4

13

16

Data Constraint

30%：1<= n,m <= 500。 另30%: p1=2*p2。

100%:1 <= n,m <= 200000；1 <= p1,p2 <= 1000。

首先考虑$p_1$的贡献，那么需要计算有多少对$(i,j)$满足$k[i],k[j]$分别是$[i,j]$的最大值和次大值。

我们讨论每个点对中的次大值，那么当$k[i]$为区间次大值时，找到$k[i]$左边第一个比它大的数$k[l]$，右边第一个比他大的数$k[r]$，那么以$k[i]$为次大值的点对就是$(l,i)$和$(i,r)$

那么询问$p_1$的贡献就等价于问以$(a,a)$为左下角$(b,b)$为右上角的矩形中有多少个点。

将每个询问拆成两个询问，即以$(1,a)$为左下角，$(a-1,b)$为右上角的矩形和以$(1,a)$为左下角$(b,b)$为右上角的两个矩形相减即可，然后用扫描线从左往右扫一遍，用树状数组维护纵坐标的区间和即可。

然后考虑$p_2$的贡献，需要计算有多少对$(i,j)$满足一个端点是最大值，另一个不是次大值。这个不好计算，但我们可以发现$p_1$与$p_2$的贡献和很好算，即计算有多少对$(i,j)$满足其中一个是区间最大值。

那么考虑每个点$k[i]$，那么同样找出每个点左边第一个比他大的数$k[l]$，右边$k[r]$，则满足条件的点对是$([l+1,i-1],i)$与$(i,[i+1,r-1])$，这些点对，容易发现我们可以将这些点对抽象成线段，即横坐标为$i$，纵坐标在$[l+1,i-1]$与$[i+1,r-1]$之间的线段，这样的话同样可以扫描线，只不过单点修改变成了区间修改。

那么$p_2$的点对数就是上述算出来的点对数减去$p_1$的点对数即可。

总时间复杂度$O(n\log n)$

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#define N 400005
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 void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
int n,m,v1,v2,A[N],L[N],R[N],cnt1[N],cnt2[N];
stack<int>S;
struct nodd{int pos,x1,x2,ty,id;}T[N],Q[N];
struct node{int l,r,id;}K[N];
bool operator<(nodd a,nodd b)
{return a.pos<b.pos;}
namespace BIT
{
	int C[N];
	void MD(int x,int d)
	{for(int i=x;i&&i<=n;i+=(i&-i))C[i]+=d;}
	int GS(int x)
	{
		int i,sum=0;
		for(i=x;i;i-=(i&-i))sum+=C[i];
		return sum;
	}
}
namespace Seg
{
	int tot,ls[N],rs[N],v[N],lazy[N];
	int BT(int x,int y)
	{
		int p=++tot;
		if(x==y)return p;
		int mid=x+y>>1;
		ls[p]=BT(x,mid);
		rs[p]=BT(mid+1,y);
		return p;
	}
	void PD(int p,int l,int r)
	{
		int mid=l+r>>1;
		if(ls[p])v[ls[p]]+=lazy[p]*(mid-l+1),lazy[ls[p]]+=lazy[p];
		if(rs[p])v[rs[p]]+=lazy[p]*(r-mid),lazy[rs[p]]+=lazy[p];
		lazy[p]=0;
	}
	void ADD(int p,int l,int r,int x,int y)
	{
		if(lazy[p])PD(p,l,r);
		if(x<=l&&y>=r){lazy[p]++;v[p]+=r-l+1;return;}
		int mid=l+r>>1;
		if(x<=mid&&y>=l)ADD(ls[p],l,mid,x,y);
		if(x<=r&&y>mid)ADD(rs[p],mid+1,r,x,y);
		v[p]=v[ls[p]]+v[rs[p]];
	}
	int GS(int p,int l,int r,int x,int y)
	{
		if(lazy[p])PD(p,l,r);
		if(x<=l&&y>=r)return v[p];
		int mid=l+r>>1,sum=0;
		if(x<=mid&&y>=l)sum+=GS(ls[p],l,mid,x,y);
		if(x<=r&&y>mid)sum+=GS(rs[p],mid+1,r,x,y);
		return sum;
	}
}
int main()
{
	int i,j,k,x,y,pt=0;
	_R(n);_R(m);_R(v1);_R(v2);
	for(i=1;i<=n;i++)_R(A[i]);
	A[0]=A[n+1]=1e9;S.push(0);
	for(i=1;i<=n;i++)
	{
		while(A[S.top()]<A[i])S.pop();
		L[i]=S.top();S.push(i);
	}
	while(S.size())S.pop();
	S.push(n+1);
	for(i=n;i>=1;i--)
	{
		while(A[S.top()]<A[i])S.pop();
		R[i]=S.top();S.push(i);
	}
	for(i=1;i<=m;i++)
	{
		_R(x);_R(y);
		K[i]=(node){x,y,i};
	}
	for(i=1;i<=n;i++)
	{
		T[i]=(nodd){i,L[i],0,0,0};
		T[n+i]=(nodd){i,R[i],0,0,0};
	}
	for(i=1;i<=m;i++)
	{
		Q[i]=(nodd){K[i].l-1,K[i].l,K[i].r,-1,i};
		Q[i+m]=(nodd){K[i].r,K[i].l,K[i].r,1,i};
	}
	sort(T+1,T+n+n+1);sort(Q+1,Q+m+m+1);
	for(i=j=1;i<=m+m;i++)
	{
		while(j<=n+n&&T[j].pos<=Q[i].pos)
		BIT::MD(T[j].x1,1),j++;
		cnt1[Q[i].id]+=Q[i].ty*(BIT::GS(Q[i].x2)-BIT::GS(Q[i].x1-1));
	}
	for(i=1;i<=n;i++)
	{
		if(L[i]+1<i)T[++pt]=(nodd){i,L[i]+1,i-1,0,0};
		if(R[i]-1>i)T[++pt]=(nodd){i,i+1,R[i]-1,0,0};
	}
	sort(T+1,T+pt+1);Seg::BT(1,n);
	for(i=j=1;i<=m+m;i++)
	{
		while(j<=pt&&T[j].pos<=Q[i].pos)Seg::ADD(1,1,n,T[j].x1,T[j].x2),j++;
		cnt2[Q[i].id]+=Q[i].ty*Seg::GS(1,1,n,Q[i].x1,Q[i].x2);
	}
	for(i=1;i<=m;i++)printf("%lld\n",1ll*v1*cnt1[i]+1ll*v2*(cnt2[i]-cnt1[i]));
}