Loj 2019 影魔

Posted on | Views:

单调栈 + 二维数点.

对于一组端点 $(l,r)$ ,考虑将它们可能的贡献放到区间 $[l+1,r-1]$ 的最大值的那个位置去计算.

即,在每个位置 $i$ ,考虑它作为区间 $[l+1,r-1]$ 最大值时产生的 $p_1,p_2$ 的贡献.

利用单调栈求出 $i$ 左边第一个比它大的位置 $L$ ,右边第一个比它大的位置 $R$ .

由于 $i​$ 要是区间内的最大值,所以选择的左端点 $\ge L​$, 右端点 $\le R​$ .

当左右端点分别选择了 $L,R​$ 时,会造成 $p_1​$ 的贡献.

当左端点选了 $L$ ,右端点在 $[i+1,R-1]$ 中时,或左端点在 $[L+1,i-1]$ 中,右端点选了 $R$ ,都会有 $p_2$ 的贡献.

而我们的询问是限制了左右端点的取值范围,相当于在平面上询问一个矩形内贡献之和.

每个 $i$ 的贡献是一个单点 $(L,R)$ ,以及两条线段 $(L,i+1\sim R-1),(L+1\sim i-1,R)$ .

将操作全部离线下来,用线段树在平面上二维数点即可,可以分别计算横的线段和竖的线段的贡献.

最后还要加上两个端点是相邻的情况造成的若干 $p_1$ 贡献.

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

开始判 $R\neq n+1$ 的时候写成 $R\neq n-1​$ 了,居然还过了 80 分,调了好久.

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
struct SegTree
{
	struct node
	{
		int len;
		ll tag,sum;
	}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void pushup(int o)
	{
		root.sum=lson.sum+rson.sum;
	}
	void BuildTree(int o,int l,int r)
	{
		root.sum=root.tag=0;
		root.len=r-l+1;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
	}
	void modify(int o,ll c)
	{
		root.tag+=c;
		root.sum+=c*root.len;
	}
	void pushdown(int o)
	{
		if(root.tag)
		{
			modify(o<<1,root.tag);
			modify(o<<1|1,root.tag);
			root.tag=0;
		}
	}
	void upd(int o,int l,int r,int L,int R,ll c)
	{
		if(L>r || R<l)
			return;
		if(L<=l && r<=R)
			return modify(o,c);
		int mid=(l+r)>>1;
		pushdown(o);
		if(L<=mid)
			upd(o<<1,l,mid,L,R,c);
		if(R>mid)
			upd(o<<1|1,mid+1,r,L,R,c);
		pushup(o);
	}
	ll query(int o,int l,int r,int L,int R)
	{
		if(L>r || R<l)
			return 0;
		if(L<=l && r<=R)
			return root.sum;
		int mid=(l+r)>>1;
		pushdown(o);
		ll res=0;
		if(L<=mid)
			res+=query(o<<1,l,mid,L,R);
		if(R>mid)
			res+=query(o<<1|1,mid+1,r,L,R);
		return res;
	}
}T;
int n,m,p1,p2,a[MAXN],cnt=0;
ll ans[MAXN<<1];
struct Query
{
	int pos,c,l,r,id;
	Query(int pos=0,int c=0,int l=0,int r=0,int id=0):pos(pos),c(c),l(l),r(r),id(id) {}
	bool operator < (const Query &rhs) const
	{
		return pos==rhs.pos?id<rhs.id:pos<rhs.pos;
	}
}q[MAXN<<2];
int stk[MAXN],tp,L[MAXN<<1],R[MAXN<<1];
void init()
{
	a[0]=a[n+1]=n+1;
	stk[tp=1]=0;
	for(int i=1;i<=n;++i)
	{
		while(a[i]>a[stk[tp]])
			--tp;
		L[i]=stk[tp];
		stk[++tp]=i;
	}
	stk[tp=1]=n+1;
	for(int i=n;i>=1;--i)
	{
		while(a[i]>a[stk[tp]])
			--tp;
		R[i]=stk[tp];
		stk[++tp]=i;
	}
}
void solve_x()
{
	cnt=0;
	for(int i=1;i<=n;++i)
	{
		if(L[i])
		{
			if(R[i]!=n+1)
				q[++cnt]=Query(L[i],p1,R[i],R[i],0); // (L,R)
			if(i+1<=R[i]-1)
				q[++cnt]=Query(L[i],p2,i+1,R[i]-1,0); // (L,i+1 ~ R-1)
		}
	}
	for(int i=1;i<=m;++i)
	{
		q[++cnt]=Query(n,-1,1,R[i+n],i);
		if(L[i+n]-1)
			q[++cnt]=Query(L[i+n]-1,-1,1,R[i+n],i+m);
	}
	sort(q+1,q+1+cnt);
	T.BuildTree(1,1,n);
	for(int i=1;i<=cnt;++i)
	{
		if(q[i].id==0) // update
			T.upd(1,1,n,q[i].l,q[i].r,q[i].c);
		else // query
			ans[q[i].id]+=T.query(1,1,n,q[i].l,q[i].r);
	}
}
void solve_y()
{
	cnt=0;
	for(int i=1;i<=n;++i)
	{
		if(R[i]!=n+1 && L[i]+1<=i-1)
			q[++cnt]=Query(R[i],p2,L[i]+1,i-1,0); // (L+1 ~ i-1 ,R)
	}
	for(int i=1;i<=m;++i)
		q[++cnt]=Query(R[i+n],-1,L[i+n],n,i);
	sort(q+1,q+1+cnt);
	T.BuildTree(1,1,n);
	for(int i=1;i<=cnt;++i)
	{
		if(q[i].id==0) // update
			T.upd(1,1,n,q[i].l,q[i].r,q[i].c);
		else // query
			ans[q[i].id]+=T.query(1,1,n,q[i].l,q[i].r);
	}
}
int main()
{
	n=read(),m=read(),p1=read(),p2=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	init();
	for(int i=1;i<=m;++i)
		L[i+n]=read(),R[i+n]=read();
	solve_x();
	solve_y();
	for(int i=1;i<=m;++i)
		printf("%lld\n",ans[i]+1LL*p1*(R[i+n]-L[i+n])-ans[i+m]);
	return 0;
}