LibreOJ 2019.「AHOI / HNOI2017」影魔

尝试学习 Min_25 筛,看了半天最终弃疗……
来写点 DS 题散心。

题面中二程度爆表

以下 ai=kia_i = k_i
翻译一下,题目的意思是:
对于每个有序数对 (x,y),x<y(x,y),x < y,如果 ax,ay>maxi=x+1y1aia_x,a_y > \max\limits_{i = x + 1}^{y - 1} a_i,对答案产生 p1p_1 的贡献;如果 ax>maxi=x+1y1ai>aya_x > \max\limits_{i = x + 1}^{y - 1} a_i > a_yay>maxi=x+1y1ai>axa_y > \max\limits_{i = x + 1}^{y - 1} a_i > a_x,对答案产生 p2p_2 的贡献。
询问给定 l,rl,r,求两个数都在 [l,r][l,r] 内的数对的答案。

两种贡献都跟 max\max 有关,所以我们可以考虑对于这个 max\max 统计答案的贡献。

先不考虑多组询问,假设只求整个序列的答案。
leftileft_i 表示 [1,i)[1,i) 中最后一个 >ai> a_i 的数的位置,rightiright_i 表示 (i,n](i,n] 中第一个 >ai> a_i 的数的位置。
这个东西随便用单调栈/双向链表/set 预处理就好了。
对于每个 ii,显然 ai=maxi=lefti+1righti1a_i = \max\limits_{i = left_i + 1}^{right_i - 1}
所以 (lefti,righti)(left_i,right_i) 产生 p1p_1 的贡献。
(lefti,j),(k,righti),i<j<righti,lefti<k<i(left_i,j),(k,right_i),i < j < right_i,left_i < k < i 产生 p2p_2 的贡献。

现在来考虑多组询问。
这个时候发现我们没辙了。
考虑离线。

对于第一种贡献,我们把询问按 rr 排序,从 1n1 \to n 扫描,如果遇到一个位置 ii,并有另外一个/多个位置 jj 满足 i=rightji = right_j,就让数据结构上第 leftjleft_j 个数加上 p1p_1
然后对于所有 r=ir = i 的询问,查询数据结构上 [l,r][l,r] 的和,即为第一种贡献。
注意这样子没法统计到形如 (x,x+1)(x,x + 1) 的数对的贡献,另外加上即可。

对于第二种贡献,我们先考虑 (lefti,j),i<j<righti(left_i,j),i < j < right_i 的情况,另一种倒过来即可。 把询问按 ll 排序,从 n1n \to 1 扫描,遇到一个位置 ii,并有 jj 满足 i=leftji = left_j,就让数据结构上 [j+1,rightj)[j + 1,right_j) 加上 p2p_2
对于 l=il = i 的询问,直接查询 [l,r][l,r] 区间和。

数据结构用线段树就好了。
因为个人习惯,我顺便写了动态开点和标记永久化。

代码:

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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 2e5;
const int M = 2e5;
int n,m,p1,p2;
int st[N + 5],top;
int a[N + 5],left[N + 5],right[N + 5];
vector<int> le[N + 5],ri[N + 5];
struct s_query
{
int l,r,id;
inline bool operator<(const s_query &o) const
{
return l < o.l;
}
inline bool operator>(const s_query &o) const
{
return r < o.r;
}
} qry[M + 5];
long long ans[M + 5];
struct node
{
long long sum,tag;
int ls,rs;
} seg[(N << 6) + 10];
int rt[3];
void update(int l,int r,long long k,int &p,int tl,int tr)
{
if(l > r)
return ;
static int tot = 0;
if(!p)
p = ++tot;
if(l <= tl && tr <= r)
{
seg[p].sum += k * (tr - tl + 1),seg[p].tag += k;
return ;
}
seg[p].sum += k * (min(r,tr) - max(l,tl) + 1);
int mid = tl + tr >> 1;
if(l <= mid)
update(l,r,k,seg[p].ls,tl,mid);
if(r > mid)
update(l,r,k,seg[p].rs,mid + 1,tr);
}
long long query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].sum;
int mid = tl + tr >> 1;
long long ret = seg[p].tag * (min(r,tr) - max(l,tl) + 1);
if(l <= mid)
ret += query(l,r,seg[p].ls,tl,mid);
if(r > mid)
ret += query(l,r,seg[p].rs,mid + 1,tr);
return ret;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&p1,&p2);
a[0] = a[n + 1] = 0x3f3f3f3f,top = 1;
for(register int i = 1;i <= n;++i)
{
scanf("%d",a + i);
for(;top && a[st[top]] < a[i];--top);
le[left[i] = st[top]].push_back(i),st[++top] = i;
}
st[top = 1] = n + 1;
for(register int i = n;i;--i)
{
for(;top && a[st[top]] < a[i];--top);
ri[right[i] = st[top]].push_back(i),st[++top] = i;
}
for(register int i = 1;i <= m;++i)
scanf("%d%d",&qry[i].l,&qry[i].r),qry[i].id = i;
sort(qry + 1,qry + m + 1,greater<s_query>());
for(register int i = 1,j = 0;i <= m;++i)
{
while(j < qry[i].r)
{
++j;
for(register int k = 0;k < ri[j].size();++k)
update(left[ri[j][k]],left[ri[j][k]],p1,rt[0],0,n + 1);
}
ans[qry[i].id] += query(qry[i].l,qry[i].r,rt[0],0,n + 1) + (long long)(qry[i].r - qry[i].l) * p1;
}
sort(qry + 1,qry + m + 1);
for(register int i = m,j = n + 1;i;--i)
{
while(j > qry[i].l)
{
--j;
for(register int k = 0;k < le[j].size();++k)
update(le[j][k] + 1,right[le[j][k]] - 1,p2,rt[1],0,n + 1);
}
ans[qry[i].id] += query(qry[i].l,qry[i].r,rt[1],0,n + 1);
}
sort(qry + 1,qry + m + 1,greater<s_query>());
for(register int i = 1,j = 0;i <= m;++i)
{
while(j < qry[i].r)
{
++j;
for(register int k = 0;k < ri[j].size();++k)
update(left[ri[j][k]] + 1,ri[j][k] - 1,p2,rt[2],0,n + 1);
}
ans[qry[i].id] += query(qry[i].l,qry[i].r,rt[2],0,n + 1);
}
for(register int i = 1;i <= m;++i)
printf("%lld\n",ans[i]);
}