LibreOJ 2019 「AHOI / HNOI2017」影魔

发表于 | 分类于 | 8

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

题面中二程度爆表。

以下 ai=ki。
翻译一下，题目的意思是：
对于每个有序数对 (x,y),x<y，如果 ax,ay>y−1maxi=x+1ai，对答案产生 p1 的贡献；如果 ax>y−1maxi=x+1ai>ay 或 ay>y−1maxi=x+1ai>ax，对答案产生 p2 的贡献。
询问给定 l,r，求两个数都在 [l,r] 内的数对的答案。

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

先不考虑多组询问，假设只求整个序列的答案。
设 lefti 表示 [1,i) 中最后一个 >ai 的数的位置，righti 表示 (i,n] 中第一个 >ai 的数的位置。
这个东西随便用单调栈/双向链表/set 预处理就好了。
对于每个 i，显然 ai=righti−1maxi=lefti+1。
所以 (lefti,righti) 产生 p1 的贡献。
(lefti,j),(k,righti),i<j<righti,lefti<k<i 产生 p2 的贡献。

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

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

对于第二种贡献，我们先考虑 (lefti,j),i<j<righti 的情况，另一种倒过来即可。 把询问按 l 排序，从 n→1 扫描，遇到一个位置 i，并有 j 满足 i=leftj，就让数据结构上 [j+1,rightj) 加上 p2。
对于 l=i 的询问，直接查询 [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]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment