Link：

 

Solution：

一道思路比较巧的线段树的题目

 

首先可以发现，答案和顺序是没有关系的，都是$\sum_{i=1}^n {H_i∗(H_i−1)/2}$。

那么可以比较容易得得到以下的贪心策略：

对于第$i$个船帆，对前$H_i$层中的前$K_i$小的数加1 

 

感性证明：最优方案肯定是每层上数量尽量接近，那么每次放在当前数量最少的层上一定不会使答案变差

 

此题的难点还是在实现上，

为了对于每个$i$都能区间+1，序列一定要具有单调性

又由于$H_i$是从小到大排序的，每次区间加时注意维护序列从大到小递减即可

 

但每次对$[H_i-K_i+1,H_i]$+1是不一定能保证单调的，

于是我们找到$seg[H_i-K_i+1]$第一个出现的位置$posr$和结束的位置$posl$，

由于$seg[posl]$更小，我们先尽量选取$[posl,H_i]$，再从$posr$开始选取从而保证单调性

 

Code：

#include 
     
      using namespace std;typedef long long ll;typedef pair
      
        P;#define mid ((l+r)>>1)#define lc k<<1,l,mid#define rc k<<1|1,mid+1,r#define F first#define S secondconst int MAXN=1e5+10;const int INF=1<<27;int n,maxk=0;ll res=0;P dat[MAXN];int seg[MAXN<<2],tag[MAXN<<2];void push_up(int k){seg[k]=min(seg[k<<1],seg[k<<1|1]);}void push_down(int k){    if(!tag[k]) return;    seg[k<<1]+=tag[k];seg[k<<1|1]+=tag[k];    tag[k<<1]+=tag[k];tag[k<<1|1]+=tag[k];    tag[k]=0;}void build(int k,int l,int r){    if(l==r)    {        if(l==maxk) seg[k]=-INF;  //要增加最后一位！        else seg[k]=0;        return;    }    build(lc);build(rc);    push_up(k);}int find_val(int x,int k,int l,int r){    if(l==r) return seg[k];    push_down(k);    if(x<=mid) return find_val(x,lc);    else return find_val(x,rc);}int find_pos(int x,int k,int l,int r){    if(l==r) return l;    push_down(k);    if(seg[k<<1]<=x) return find_pos(x,lc);    else return find_pos(x,rc);}void Update(int a,int b,int k,int l,int r){    if(a<=l && r<=b)    {        seg[k]++;tag[k]++;        return;    }    push_down(k);    if(a<=mid) Update(a,b,lc);    if(b>mid) Update(a,b,rc);    push_up(k);}void cnt(int k,int l,int r){    if(l==maxk) return;    if(l==r)    {        res+=1ll*seg[k]*(seg[k]-1)/2;        return;    }    push_down(k);    cnt(lc);cnt(rc);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d%d",&dat[i].F,&dat[i].S),maxk=max(maxk,dat[i].F);    sort(dat+1,dat+n+1);maxk++;    build(1,1,maxk);        for(int i=1;i<=n;i++)    {        int num=find_val(dat[i].F-dat[i].S+1,1,1,maxk); //当前位置        int posl=find_pos(num-1,1,1,maxk); //第一个小于num的的数的位置        int posr=find_pos(num,1,1,maxk);  //第一个等于num的数的位置                if(posl<=dat[i].F) Update(posl,dat[i].F,1,1,maxk);        Update(posr,posr+min(dat[i].S,posl-(dat[i].F-dat[i].S+1))-1,1,1,maxk);    }        cnt(1,1,maxk);    printf("%lld",res);    return 0;}
      
     

 

Review：

1、如果序列单调，则可用线段树查询的方式找出第一个小于/大于/等于$x$的数

 

2、对边界问题还是要敏感些啊，

此题中如果不添加最后一位，并将$seg[maxk]=-INF$，则可能出现$posl=(dat[i].F-dat[i].S+1)$，导致溢出

 

3、算是又了解了一种在线段树上维护单调性的方法吧，

要先找到这个数第一个出现的位置$pos$，再从$pos$开始操作即可