D - Alarm Clock 线段树尽量递归右边的代码模板

https://codeforces.com/contest/898/problem/D

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug printf("---\n");
const int N=200010,M=1000010;
struct node{
    int l;
    int r;
    int sum;
    bool lz;
}tr[M<<2];
int cnt[M];
void pushdown(int u)
{
    tr[u<<1].sum=tr[u<<1|1].sum=0;
    tr[u<<1].lz=1;
    tr[u<<1|1].lz=1;
    tr[u].lz=0;
}
void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void build(int u,int l,int r)
{
    tr[u]={l,r,0};
    if(l==r)
    {
        if(cnt[l])    
        tr[u].sum=1;
        return ;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
void mdf(int u,int l,int r,int &d)
{
//    cout<<u<<" "<<l<<" "<<r<<" "<<d<<endl;
    if(tr[u].l>=l && tr[u].r<=r)
    {
        //cout<<1<<endl;
        if(tr[u].sum<=d)
        {
        d-=tr[u].sum;
        tr[u].sum=0;
        tr[u].lz=1;
        return ;
        }
        else
        {
                mdf(u<<1|1,l,r,d);
                if(d)
                mdf(u<<1,l,r,d);
        }
    }
    if(tr[u].l==tr[u].r)    return ;
    if(tr[u].lz)
    pushdown(u);
    int mid = tr[u].l +tr[u].r>>1;
    if(r<=mid)
    {
        mdf(u<<1,l,r,d);
    }
    else if(l>mid)
    {
        mdf(u<<1|1,l,r,d);
    }
    else
    {
        mdf(u<<1|1,l,r,d);
        if(d) 
        mdf(u<<1,l,r,d);
    }
    pushup(u);
}
int qr(int u,int l,int r)
{
    //cout<<u<<" "<<l<<" "<<r<<endl;
    if(tr[u].l>=l && tr[u].r<=r)
    {
        return tr[u].sum;
    }
    if(tr[u].lz)
    pushdown(u);
    int mid = tr[u].l +tr[u].r>>1;
    int res=0;
    if(l<=mid)    res+=qr(u<<1,l,r);
    if(r>mid)    res+=qr(u<<1|1,l,r);
    return res;
}
int a[N];
int sum[M];
int main()
{
    ios::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    int n , m , k;
    cin >> n >>m >>k;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    if(k==1)
    {
        cout<<n<<endl;
        return 0;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    cnt[a[i]]++;
    build(1,1,M-1);
    int res=0;
    for(int i=1;i+m-1<M;i++)
    {
        int r=qr(1,i,i+m-1);
        if(r<k)    continue;
        else
        {
            res+=r-k+1;
            int tt=r-k+1;
            mdf(1,i,i+m-1,tt);
        }
    }
    cout<<res<<endl;
    return 0;
}