题解：P13959 [ICPC 2023 Nanjing R] 计数器

· · 题解

由于操作只有清零和加一，所以对于每个 i，第 a_i-b_i 次操作是清零，a_i-b_i+1 到 a_i 的操作都是加一。

如果一个加一的区间里面在后来说要清零，那么肯定输出 No。

用映射记录每个加一的左开右闭区间，然后排序（STL 的 map 是自动排序的）。两个区间左端点相同的，是合法的，因为都一起清零，但是这样，右端点要取最大值。

遍历所有区间，如果两个区间冲突，即一个区间左端点小于等于上一个区间左端点,那么输出 No。如果没有区间冲突，输出 Yes。

code

#include <bits/stdc++.h>
using namespace std;
map<int,int> a;
void c(){
    a.clear();
    int n,m;
    cin>>n>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        a[x-y]=max(a[x-y],x);
    }
    int r=-1;
    for(pair<int,int> i:a){
        if(i.first<=r){
            cout<<"No\n";
            return;
        }
        r=i.second;
    }
    cout<<"Yes\n";
}
int main(){
    int T;
    cin>>T;
    while(T--){
        c();
    }
}