[NOI Online 2022 提高组] 丹钓战

发表于 更新于

P8251 [NOI Online 2022 提高组] 丹钓战
这道题我的方法是主席树，请不了解主席树的同学移步这道题： P3834 【模板】可持久化线段树 2

分析

模拟入栈

首先我们可以发现，这个栈的元素 $b_i$ 一定是单调下降的，如果要模拟入栈的操作，我们可以通过二分查找第一个比 $b_i$ 大的元素来模拟，可以在 $n\log n$ 的复杂度内完成一次模拟。但是同时还要满足任意两个相邻元素的 $a$ 不同，我们只需要在找到第一个比 $b_i$ 大的元素后，弹出栈顶直到栈顶元素的 $a$ 与 $a_i$ 不相等。注意要首先把 $inf$ 入栈，防止越界。
$b$ 代表 $b$ 序列，$c$ 代表栈。

1
2
3
4
5
6
7
8
int l=0,r=t,z;
while(l<r)
 {
    z=(l+r+1)>>1;
    if(b[i]<b[c[z]]) l=z;
    else r=z-1;
}
while(a[c[l]]==a[i]) --l;

查询

如果我们先把所有元素按顺序入栈，由于任意的 $[l,r]$ 都应该是 $[1,n]$ 的一部分，并且栈中的元素编号一定递减，所以 $\forall [l,r]$，最终形成的栈一定是 $[1,r]$ 形成的栈的一部分，具体来说就是 $[1,r]$ 形成的栈去掉所有编号比 $l$ 小的元素。如果 $r$ 号元素想要在 $[l,r]$ 形成的栈中成为第一个，那么 $[1,r]$ 所形成的的栈中在 $r$ 之前的元素的编号必然都比 $l$ 小，只有这样前面所有元素才会被删去。所以用 $d$ 来储存每个数入栈后前一个元素的编号，那么 $[l,r]$ 中成功二元组的个数就是 $k \in [l,r],d_k < l$ 成立的 $k$ 的个数。

优化

但是上面这种方法的复杂度为 $O(n\times q)$ ，显然过不了。通过上面的分析，我们发现查询的实质是求 $d$ 中 $[l,r]$ 中小于 $l$ 的数的个数。有什么数据结构能实现？主席树！于是这道题就变成了主席树的板子题。然后，就没有然后了。

code

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
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
int n,m,p,t,a[500001],b[500001],c[500001],rt[500001];
struct tree
{
    int l,r,s;
}T[30000001];
void pushup(int x)
{
    T[x].s=T[T[x].l].s+T[T[x].r].s;
}
void build(int &x,int l,int r)
{
    x=++p;
    if(l==r) return;
    int z=l+r>>1;
    build(T[x].l,l,z);
    build(T[x].r,z+1,r);
}
void modify(int &x,int l,int r,int q)
{
    T[++p]=T[x];
    ++T[p].s;
    x=p;
    if(l==r) return;
    int z=l+r>>1;
    if(q<=z) modify(T[x].l,l,z,q);
    else modify(T[x].r,z+1,r,q);
}
int num(int x,int l,int r,int k)
{
    if(l==r) return 0;
    int z=l+r>>1;
    if(k==z) return T[T[x].l].s;
    if(k<z) return num(T[x].l,l,z,k);
    return T[T[x].l].s+num(T[x].r,z+1,r,k);
}
int main()
{
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i) b[i]=read();
    a[0]=0;
    b[0]=1e9;
    c[0]=0;
    build(rt[0],0,n);
    for(int i=1;i<=n;++i)
    {
        int l=0,r=t,z;
        while(l<r)
        {
            z=(l+r+1)>>1;
            if(b[i]<b[c[z]]) l=z;
            else r=z-1;
        }
        while(a[c[l]]==a[i]) --l;
        t=l+1;
        c[t]=i;
        rt[i]=rt[i-1];
        modify(rt[i],0,n,c[l]);
    }
    for(int i=1;i<=m;++i)
    {
        int l=read(),r=read();
        printf("%d\n",num(rt[r],0,n,l-1)-num(rt[l-1],0,n,l-1));
    }
    return 0;
}
相关文章