差分

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2e4;
struct Node{
    int st,ed;
    bool repeat;
    bool operator <(const Node another)const{
        if(repeat)return false;
        if(st<another.st)return true;
        if(st==another.st&&ed<another.ed)return true;
        return false; 
    }
}nodes[MAXN];//原始数据
int nodeSum=0;

int m; 

//去重 
void makeDataGreatAgain(){
    sort(nodes+1,nodes+nodeSum+1);
    for(int i=2;i<=nodeSum;i++){
        if(nodes[i].st==nodes[i-1].st&&nodes[i].ed==nodes[i-1].ed){
            nodes[i].repeat=true;
        }
    }
}

int b[MAXN];//差分数组 
int main(){
    memset(b,0,sizeof(b));
    int n,p,h;
    scanf("%d%d%d%d",&n,&p,&h,&m);

    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if(abs(b-a)<=1)continue;
        nodes[++nodeSum]=Node{min(a,b),max(a,b),false}; 
    }
    //outputNode();
    makeDataGreatAgain();
    for(int i=1;i<=nodeSum;i++){
        Node node=nodes[i];
        if(node.repeat)continue;
        b[node.st]-=1;
        b[node.ed-1]+=1;
    }
    int delta=0;
    for(int i=1;i<=n;i++){
        cout<<h+delta<<endl;
        delta+=b[i];
    }
    return 0;
}