Wuyanru's blog
0%

[LGR-133] 待黑白分明

发表于 分类于 ，

又是被数据结构吊着打的一天呢！

题目链接。

题意

数轴上有 个点，第 个点高度为 ， 是一个排列。

现在有 条折线，第 条折线从左到右依次连接了所有高度 的点。

现在称一个集合是好的，当且仅当所有点按照高度排序后，任意相邻的两个点被某条折线直接连接。

组询问，每一次给出 ，询问有多少好的集合，使得集合内的所有点高度均在 之间。

。

题解

首先来考虑什么样的集合是好的。

可以发现，两个点 被某条折线直接连接当且仅当有 。

考虑建出笛卡尔树，那么相当于，高度低的那个点向左或向右跳一步一定能跳到高度高的那个点。

那么直接枚举集合内高度最低的点，然后暴力一下，就可以做到 。

考虑使用树上撒点分块进行优化，先在树上随机撒 个关键点。

然后对询问跑扫描线，将所有询问按照 从大到小排序，每一次加入一个点。

考虑这个点造成的答案分为了两部分，一类是关键点以下的部分，一类是关键点以上的部分。

对第一部分来说，造成的答案的右端点期望只有 种，考虑使用 的分块，加答案的时候直接加，询问的时候查一下前缀和。

对于第二部分，由于关键点只有 个，所以此时相当于有 个位置，会造成额外的贡献。

枚举每一个位置，暴力求出每多 的贡献，对 的高度总共会造成多少答案，这一部分可以暴力 dp 然后前缀和。

对于每一个询问，还是扫描线一样加点，然后直接乘起来。

时间复杂度 。

每一块离线下来分开做，空间复杂度 。

代码

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
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
using pil=pair<int,ll>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int mod=998244353;
mt19937 _rand(1145141);
inline int rand(int l,int r)
{
    return _rand()%(r-l+1)+l;
}
struct node
{
    int l,r,id;
}b[200001];
int sta[200001],top;
vc<pil>g[200001];
bool vis[200001];
ll qans[200001];
ll sum1[200001];
ll sum2[501];
int to[200001][2];
int son[200001][2];
ll pre[200001];
int fa[200001];
int wh[200001];
int ra[200001];
int a[200001];
int n,m,sq;
inline void Add(ll &a,ll b)
{
    a+=b;
    if(a>=mod) a-=mod;
}
inline void add(int x,int y)
{
    Add(sum1[x],y);
    Add(sum2[wh[x]],y);
}
inline ll get(int x)
{
    ll ans=0;
    for(int i=1;i!=wh[x];i++) Add(ans,sum2[i]);
    for(int i=x;wh[i]==wh[x];i--) Add(ans,sum1[i]);
    return ans;
}
inline void push(int w,int v)
{
    int d=-1;ll t=1,sum=1;
    while(w)
    {
        add(a[w],t);
        if(vis[w]&&d!=-1)
        {
            g[to[w][!d]].push_back(pil(v,t));
            g[to[w][d]].push_back(pil(v,sum));
            break;
        }
        int dir=son[fa[w]][1]==w;
        if(dir==d) Add(sum,t);
        else swap(sum,t),Add(sum,t);
        d=dir,w=fa[w];
    }
}
void dfs(int p,int l,int r)
{
    if(son[p][0]) to[son[p][0]][1]=fa[son[p][0]]=p,to[son[p][0]][0]=to[p][0],dfs(son[p][0],l,p-1);
    if(son[p][1]) to[son[p][1]][0]=fa[son[p][1]]=p,to[son[p][1]][1]=to[p][1],dfs(son[p][1],p+1,r);
}
inline void run(int s)
{
    memset(pre,0,sizeof(pre));pre[a[s]]=1;
    for(int i=1;i<=n;i++)
    {
        int p=ra[i];
        if(to[p][0]) Add(pre[a[to[p][0]]],pre[i]);
        if(to[p][1]) Add(pre[a[to[p][1]]],pre[i]);
    }
    for(int i=1;i<=n;i++) Add(pre[i],pre[i-1]);


    ll sum=0;unsigned now=0;
    for(int i=1;i<=m;i++)
    {
        while(now<g[s].size()&&g[s][now].first>=b[i].l) Add(sum,g[s][now++].second);
        Add(qans[b[i].id],pre[b[i].r]*sum%mod);
    }
}
int main()
{
    n=read(),m=read();
    for(;(sq+1)*(sq+1)<=n;sq++);
    int rest=sq;
    for(int i=n;i;i--) if(rand(1,i)<=rest) rest--,vis[i]=1;
    for(int i=1;i<=n;i++)
    {
        ra[a[i]=read()]=i,wh[i]=(i+sq-1)/sq;
        while(top&&a[i]>a[sta[top]]) son[i][0]=sta[top--];
        son[sta[top]][1]=i,sta[++top]=i;
    }
    dfs(son[0][1],1,n);
    for(int i=1;i<=m;i++) b[i].l=read(),b[i].r=read(),b[i].id=i;
    sort(b+1,b+m+1,[](node a,node b){ return a.l>b.l;});

    int now=n;
    for(int i=1;i<=m;i++)
    {
        while(now>=b[i].l) push(ra[now],now),now--;
        qans[b[i].id]=get(b[i].r);
    }

    for(int i=1;i<=n;i++) if(g[i].size()) run(i);

    for(int i=1;i<=m;i++) printf("%lld\n",qans[i]);
    return 0;
}