UVA 12663 第九届省赛 高桥与低桥 线段树

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define Lson (rt<<1),l,mid
#define Rson (rt<<1|1),mid+1,r
#define N 100010
using namespace std;
int n,m,k;
int d[N*3],maxk[N*3],flag[N*3],A[N];
void up(int rt)
{
    d[rt]=d[rt<<1]+d[rt<<1|1];
    maxk[rt]=maxk[rt<<1]+maxk[rt<<1|1];
}
void pushdown(int rt,int l,int r)
{
    if (l>=r || flag[rt]==0) return;
    int ll=rt<<1;
    int rr=rt<<1|1;
    int mid=(l+r)>>1;
    d[ll]+=flag[rt];
    d[rr]+=flag[rt];
    flag[ll]+=flag[rt];
    flag[rr]+=flag[rt];
    flag[rt]=0;
    if (mid-l+1==1 && d[ll]>=k)
        maxk[ll]=1;
    if (r-mid==1 && d[rr]>=k)
        maxk[rr]=1;
   // up(rt);
}
void add(int rt,int l,int r,int L,int R)
{
    if (L<=l && r<=R)
    {
        pushdown(rt,l,r);
        d[rt]+=r-l+1;
        if (l>=r && d[rt]>=k)
            maxk[rt]=1;
        flag[rt]++;
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if (L<=mid)
        add(Lson,L,R);
    if (R>mid)
        add(Rson,L,R);
    up(rt);
}
void incase(int rt,int l,int r)
{
    if (l>=r)
    {
        if(d[rt]>=k)
            maxk[rt]=1;
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    incase(Lson);
    incase(Rson);
    up(rt);
}
void build(int rt,int l,int r)
{
    flag[rt]=0;
    if(l>=r)
    {
        d[rt]=0;
        maxk[rt]=0;
        flag[rt]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(Lson);
    build(Rson);
    up(rt);
}
int main()
{
    int kase=0,a,b,cur;
    while (scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        for (int i=1;i<=n;i++){
            scanf("%d",&A[i]);
        }
        sort(A+1,A+1+n);
        build(1,1,n);
        cur=1;
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            int l=upper_bound(A+1,A+1+n,cur)-A;
            int r=upper_bound(A+1,A+1+n,a)-A;
            r--;
            if (l<=r)
            add(1,1,n,l,r);
            cur=b;
        }
        incase(1,1,n);
        printf("Case %d: %d
",++kase,maxk[1]);
    }
    return 0;
}