题意

有n个数，其中位置b的数一定大于等于位置a的数,且a和b之间的数都比a小。已知最大的数的位置及大小。求这n个数的可能的最大值。

做法：差分

思路

  • 因为每个数要尽可能大，所以a和b相等，且a+1~b-1的数比a小1
  • 区间内的数同时增大或减小某一个数可以用差分处理

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

map<pii,bool> mp;
int d[N],h[N];

void solve(){
    int n,id,maxh,r;cin>>n>>id>>maxh>>r;
    while(r--){
        int a,b;cin>>a>>b;
        if(a>b) swap(a,b);
        if(mp[{a,b}]) continue;
        mp[{a,b}]=1;
        //(a+1)~(b-1)
        d[a+1]--;
        d[b]++;
    }
    h[0]=maxh;
    rep(i,1,n){
        h[i]=h[i-1]+d[i];
        cout<<h[i]<<"\n";
    }
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}