P1204 [USACO1.2]挤牛奶Milking Cows（差分）

题目传送门

Milking Cows

题目大意

给你n个区间为覆盖，区间总长为最小左端点到最大右端点，求最长的覆盖区间，和最长的为覆盖区间

思路

本想练习线段树的，发现线段树有点麻烦，采取了差分做法
使用差分的方法操作区间 O ( 1 ) O(1) O(1)即可，查询 O ( n ) O(n) O(n)
区间增值即为 a [ l ] + + ,   a [ r + 1 ] + + a[l]++,\ a[r+1]++ a[l]++, a[r+1]++，注意300~900其实是601秒，题目给的600秒，所以是在899结束的，所以应该是 a [ l ] + + ,   a [ r ] + + a[l]++,\ a[r]++ a[l]++, a[r]++

AC Code

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
const int N=1e6 +9;
int n, a[N];
int x, y;
void solve(){
    cin>>n;
    int mx=-INF, mn=INF;
    for(int i=1; i<=n; i++){
        cin>>x>>y;
        a[x]++;
        a[y]--;
        if(x<mn)    mn=x;
        if(y>mx)    mx=y;
    }
    int ans1=0, ans0=0;
    int temp1=0, temp0=0, sum=0;
    for(int i=mn; i<=mx; i++){
        sum+=a[i];
        if(sum==0){
            temp0++;
            ans1=max(ans1, temp1);
            temp1=0;
        }
        else{
            temp1++;
            ans0=max(ans0, temp0);
            temp0=0;
        }
    }
    cout<<ans1<<" "<<ans0<<endl;
    return ;
}

signed main(){
    ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}