bzoj 1805: [Ioi2007]Sail 船帆

.

题意：有n根桅杆，第$i$根的高度为$h_i$，上面有$k_i$面帆，每面帆的推力折扣为它后面同一高度的帆的数量。求最少产生多少推理折扣。
题解：贪心+线段树
很明显，桅杆的顺序对结果是没有影响的，所以我们可以先按高度排个序。对于每个桅杆，最优策略肯定是把这$k$面帆放到最少的那些行里。我们可以使每行的帆的数量保持降序，然后差分一下，就可以区间加了。但有个问题，就是假如要加的区间的左端点的在一段数量相等的区间内（即差分数组为0），就要在这个区间前加上。好像很不清楚的样子。。。你们自己去看官方题解吧。。。传送门这个可以用线段树来找这种区间。
代码：

#include<bits/stdc++.h>
#define pa pair<int,int>
#define h first
#define k second
using namespace std;

int n,num=0,d[100010];
pa a[100010];
struct tree
{
    int l,r,lc,rc;
    bool c;
}tr[200010];

void pushup(int i)
{
    int lc=tr[i].lc,rc=tr[i].rc;
    tr[i].c=tr[lc].c&tr[rc].c;
}
int bt(int l,int r)
{
    int i=++num;
    tr[i].l=l;
    tr[i].r=r;
    tr[i].c=1;
    if(l<r)
    {
        int md=l+r>>1;
        tr[i].lc=bt(l,md);
        tr[i].rc=bt(md+1,r);
    }
    return i;
}
void chg(int i,int p,int x)
{
    if(tr[i].l==tr[i].r)
    {
        d[tr[i].l]+=x;
        if(!d[tr[i].l])
        tr[i].c=1;
        else
        tr[i].c=0;
        return;
    }
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(p<=md)
    chg(lc,p,x);
    else
    chg(rc,p,x);
    pushup(i);
}
int getl(int i,int p)
{
    if(tr[i].c)
    return -1;
    if(tr[i].l==tr[i].r)
    return tr[i].l;
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(p>tr[i].r)
    {
        if(tr[rc].c)
        return getl(lc,p);
        else
        return getl(rc,p);
    }
    else
    {
        int hh;
        if(p<=md||(hh=getl(rc,p))==-1)
        return getl(lc,p);
        else
        return hh;
    }
}
int getr(int i,int p)
{
    if(tr[i].c)
    return -1;
    if(tr[i].l==tr[i].r)
    return tr[i].l;
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(p<tr[i].l)
    {
        if(tr[lc].c)
        return getr(rc,p);
        else
        return getr(lc,p);
    }
    else
    {
        int hh;
        if(p>md||(hh=getr(lc,p))==-1)
        return getr(rc,p);
        else
        return hh;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d%d",&a[i].h,&a[i].k);
    sort(a,a+n);
    bt(1,a[n-1].h+1);
    for(int i=0;i<n;i++)
    {
        int l=getl(1,a[i].h-a[i].k+1),r=getr(1,a[i].h-a[i].k+1);
        if(l==-1)
        l=1;
        if(r==-1)
        r=a[i].h+1;
        chg(1,r,1);
        chg(1,a[i].h+1,-1);
        chg(1,l,1);
        chg(1,l+(a[i].k-(a[i].h+1-r)),-1);
//        printf("%d %d %d %d\n",a[i].h,a[i].k,l,r);
        /*for(int i=1;i<=a[n-1].h+1;i++)
        printf("%d ",d[i]);
        puts("");
        int s=0;
        for(int i=1;i<=a[n-1].h+1;i++)
        printf("%d ",s+=d[i]);
        puts("\n");*/
    }
    long long ans=0,s=0;
    for(int i=1;i<=a[n-1].h;i++)
    {
        s+=d[i];
        ans+=s*(s-1)/2;
    }
    printf("%lld",ans);
}