BZOJ1805[Ioi2007]Sail船帆——线段树+贪心

题目描述

让我们来建造一艘新的海盗船。船上有 N个旗杆，每根旗杆被分成单位长度的小节。旗杆的长度等于它被分成的小节的数目。每根旗杆上会挂一些帆，每张帆正好占据旗杆上的一个小节。在一根旗杆上的帆可以任意排布在不同的小节中，但是每个小节上至多能挂一张帆。 在风中，帆的不同排布方式会产生不同的推动力。靠近船头的帆比它后面的相同高度上的帆获得的推动力少，换句话说，靠近船头的帆的推动力由于受它后面相同高度的帆的影响而打了折扣。对于任意一张帆，它的推动力折扣等于在它后面并且和它在同一高度的帆的数目。 所有帆的任意一种位置组合的推动力折扣总和等于在该位置下所有帆的推动力折扣的总和。 前 后 这条船上有6个旗杆，从前（图上的左边）到后的高度分别是3，5，4，2，4和3。图中所示的帆的位置组合的总推动力折扣是10。上图给出了每张帆自己的推动力折扣。 任务 给定N个旗杆的高度和每个旗杆上挂的帆的数目，写一个程序求出所有位置组合中的可能达到的最小的总推动力折扣。

输入

第一行包含一个整数N（2 ≤ N ≤ 100 000），表示旗杆的数目。 接下来的N行每行包含两个整数H和K（1 ≤ H ≤ 100 000, 1 ≤ K ≤ H），分别表示对应旗杆的高度及其上的帆的数目。旗杆按照从船头到船尾的顺序给出。

输出

输出包含一个整数，表示可以达到的最小的总推动力折扣。 注意：计算和输出结果时使用64位整数类型（在C/C++中用long long, 在Pascal中用int64）。 评分 在25分的测试数据中，帆的不同位置组合的总数目不超过1 000 000。

样例输入

6
3 2
5 3
4 1
2 1
4 3
3 2

样例输出

10
这个样例数据和上页中图示的样例相同。

很有思维量的一道线段树的题。(本题有几个贪心证明统一在最后证明)

首先能发现旗杆的顺序对答案不影响(证明1)，假设从下到上第i行有si个船帆，那么答案就是Σsi*(si-1)/2。

题目就可看成每次在前hi行中选ki行，使每行的si加1。

那么我们每次贪心地在前hi行中选si最小的ki行每行+1一定会使答案最优(证明2)。

如果暴力地找前ki小的每行+1显然不行，那么能不能将需要加的行变成一个区间，然后线段树上直接区间修改？

答案是可以的，我们发现对于每一步操作后的最优解中，一定有一种是满足从下到上每行船帆数单调递减的(证明3)。

这样最小的ki行就是一段区间了，但考虑修改完之后是否还保持单调递减？

假设当次修改的是[l,r]，如果s[l-1]>s[l]，那么修改后依旧保持单调递减。

如果s[l-1]=s[l]呢？这样修改之后s[l]就比s[l-1]大了，因此要找到最左边和s[l]相等的点L和最右边和s[l]相等的点R。

如果r<=R，即s[l]=s[r]，那么就将修改区间平移到[L,L+ki-1]，否则就将修改区间拆成两段：一段是[R+1,r]，剩下的平移到从L开始处。

因为这样修改是尽量靠前修改的，而且旗杆顺序不影响答案，所以要将所有旗杆按长度从小到大排序。

证明1：

我们以两个旗杆a,b为例，如果b,a时的最优解比a,b时的最优解更优，那么我们将a,b调换顺序并保持b,a时船帆状态，这时的答案还是b,a时的最优解，那么之前a,b的最优解就不是最优的了。因此无论船帆是什么顺序，都不会影响答案。

证明2：

对于每一次修改，假设不选最小的那些而是将最小的留给后面，那么为了使答案最优，最小的那几个一定是要选的，先选大的再选小的也就相当于先选小的再选大的。

证明3：

假设最优解中存在i>j且si>sj，因为能放到第i行的船帆一定能放到第j行，那么一定可以将第i行比第j行多的那些都放到第j行使得si和sj大小调换且答案不变。

#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct miku
{
    int h;
    int s;
}a[100010];
int mn[800010];
int mx[800010];
int sum[800010];
int n,m;
ll ans;
bool cmp(miku a,miku b)
{
    return a.h<b.h;
}
void pushup(int rt)
{
    mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
    mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
}
void pushdown(int rt)
{
    if(sum[rt])
    {
        sum[rt<<1]+=sum[rt];
        sum[rt<<1|1]+=sum[rt];
        mn[rt<<1]+=sum[rt];
        mn[rt<<1|1]+=sum[rt];
        mx[rt<<1]+=sum[rt];
        mx[rt<<1|1]+=sum[rt];
        sum[rt]=0;
    }
}
void change(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
    {
        sum[rt]++;
        mx[rt]++;
        mn[rt]++;
        return ;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(L<=mid)
    {
        change(rt<<1,l,mid,L,R);
    }
    if(R>mid)
    {
        change(rt<<1|1,mid+1,r,L,R);
    }
    pushup(rt);
}
int query_mid(int rt,int l,int r,int k)
{
    if(l==r)
    {
        return mn[rt];
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(k<=mid)
    {
        return query_mid(rt<<1,l,mid,k);
    }
    else
    {
        return query_mid(rt<<1|1,mid+1,r,k);
    }
}
int query_left(int rt,int l,int r,int k)
{
    if(l==r)
    {
        return l;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(mn[rt<<1]<=k)
    {
        return query_left(rt<<1,l,mid,k);
    }
    else
    {
        return query_left(rt<<1|1,mid+1,r,k);
    }
}
int query_right(int rt,int l,int r,int k)
{
    if(l==r)
    {
        return l;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(mx[rt<<1|1]>=k)
    {
        return query_right(rt<<1|1,mid+1,r,k);
    }
    else
    {
        return query_right(rt<<1,l,mid,k);
    }
}
void count_ans(int rt,int l,int r)
{
    if(l==r)
    {
        ans+=1ll*mn[rt]*(mn[rt]-1)/2;
        return ;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    count_ans(rt<<1,l,mid);
    count_ans(rt<<1|1,mid+1,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].h,&a[i].s);
        m=max(m,a[i].h);
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        int res=query_mid(1,1,m,a[i].h-a[i].s+1);
        int L=query_left(1,1,m,res);
        int R=query_right(1,1,m,res);
        if(R<a[i].h)
        {
            int len=a[i].h-R;
            change(1,1,m,R+1,a[i].h);
            change(1,1,m,L,L+(a[i].s-len)-1);
        }
        else
        {
            change(1,1,m,L,L+a[i].s-1);
        }
    }
    count_ans(1,1,m);
    printf("%lld",ans);
}