Atcoder 题解

Atcoder Beginner Contest 260 problem E 题解

题目链接：点我

题目大意

给定$N$对数和一个整数$M$，第$i$对数包含两个数$A_i,B_i$。定义一个长度为$M$的序列$C$是好的，当且仅当满足:$C$是数列$(1,2,…,M)$的一段连续子序列，且$N$对数中每一对数都至少有一个数出现在$C$中。

定义函数$f(K)$，表示长度为$K$的满足以上定义的数列的个数。

要求输出$f(1),f(2),…,f(M)$。

第一行输入$N,M$，以后$N$行，每行两个数$A_i,B_i$。

样例输入1

3 5
1 3
1 4
2 5

样例输出

0 1 3 2 1

样例解释1

下面是所有的好的数列：

• $(1,2)$
• $(1,2,3)$
• $(2,3,4)$
• $(3,4,5)$
• $(1,2,3,4)$
• $(2,3,4,5)$
• $(1,2,3,4,5)$

样例输入2

1 2
1 2

样例输出2

2 1

样例输入3

5 9
1 5
1 7
5 6
5 8
2 6

样例输出3

0 0 1 2 4 4 3 2 1

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq 2 \times 10^5$
• $1 \leq A_i < B_i \leq M$
• 所有输入均为整型数。

解析

我们可以对每一个数($A_i$或$B_i$)，添加一个属性：$v[i]$表示数$i$出现在那些编号的数对中。例如，在样例1中，数$1$出现在了第$1$和第$2$二对数中，则$v[1]=${$1,2$}。因为会有多个数，所以我们用$vector$来存储。

容易想到，如果一段数列中，所有的数的$v[i]$中，如果包含了$1$到$N$，那么说明这段序列一定是好的。另外，不难想到，如果一段序列是好的，那么这段序列向外扩展出的序列也一定是好的。

因此，这道题的思路就像滑动窗口一般。先定下窗口左端，然后枚举窗口右端。若某时某刻，找到了一段好的序列，那么这之后的序列一定都是好的序列。

而对于答案统计，我们可以用差分来实现。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m;
int a[N],b[N];
int cnt[N],ans[N]; //cnt[j]表示在一段序列中，数i的v[i]中的元素j出现的个数
vector<int>v[N]; //v[i]
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    for(int i=1;i<=n;i++){
        v[a[i]].push_back(i);
        v[b[i]].push_back(i);
    }
    int cntn=n; //cntn表示在寻找好的序列时，剩余未出现的数对的个数
    for(int i=1,j=1;i<=m;i++){ //i为左端点
        while(j<=m&&cntn){ //将右端点j向右移
            for(auto &c:v[j]){//枚举v[j]并标记
                if(cnt[c]==0) cntn--; //若数对c没有出现过，则标记
                cnt[c]++;
            }
            j++;
        } 
        if(cntn) break; //cntn=0,说明找到了好的序列，则更新nas数组
        //如果cntn!=0,那么说明右端点找到了最后都没有找到好的序列，那么左端点再向右移也不可能再找到了，就退出循环
        ans[j-i]++;ans[m+1-i+1]--; //更新答案
        for(auto &c:v[i]){
            cnt[c]--;
            if(cnt[c]==0)cntn++;
        }//将左端点右移，并将之前统计过的数还原
    }
    for(int i=1;i<=m;i++){
        ans[i]+=ans[i-1];
        cout<<ans[i]<<" ";
    }
    return 0;
}

完结撒花~