题目描述

blablabla

样例

blablabla

算法1

(差分) $O(n^2)$

#include<bits/stdc++.h>
using namespace std;
const int N=10000+2;
map<pair<int,int>,bool> mp;
int A[N],B[N],C[N];
int main(){
    int n,p,h,m;
    scanf("%d%d%d%d",&n,&p,&h,&m);
    for(int i=1;i<=n;i++){
        B[i]=h;
    }
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if(a>b)swap(a,b);
        if(mp[make_pair(a,b)]==true)continue;
        mp[make_pair(a,b)]=true;
        A[a+1]--;A[b]++;
    }
    for(int i=1;i<=n;i++){
        C[i]=C[i-1]+A[i];
    }
    for(int i=1;i<=n;i++){
        B[i]=B[i]+C[i];
        printf("%d\n",B[i]);
    }
    return 0;
}

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla