题解 P4647 【[IOI2007] sails 船帆】

· · 题解

[IOI2007] sails 船帆

怎么大家写的都是线段树/平衡树，一个树状数组不就可以搞定了么...

提供一个 \mathcal{O(n\log n)} 的树状数组做法。

首先将 h_i 按照升序排序，按顺序考虑每个柱子，在高度 1 \sim h_i 中找到旗帜数量最少的 k 个高度放上 k 面旗，因为 h_i 越大可选择的位置就越多，所以将 h_i 越大的放在后面考虑才能保证答案最小。

设 s_i 表示高度 i 上有 s_i 面旗帜，维护 s_i 单调不升，这样每次找的旗帜数量最少的 k 个高度就对应了 s_i 上的某段区间，不难发现这段区间就是 [h_i-k_i+1,h_i] 。

但是这样会出现一个问题，如果直接更新 [h_i-k_i+1,h_i] 上的值，会破坏 s_i 序列的单调性（ \exists \varepsilon ,\varepsilon < h_i-k_i+1,s_{\varepsilon}=s_{h_i-k_i+1} ），由于一个高度只能放一面旗帜，所以破坏单调性的只会是 [h_i-k_i+1,h_i] 的一段前缀，考虑将这段前缀前移。

令 l,r 表示 s_{h_i-k_i+1} 出现范围的左端点和右端点，转化为修改 [l,l+r-(h-k+1)] 和 [r+1,h] 两段区间，既维护了单调性，又满足了贪心的条件。

考虑用树状数组维护 s_i ，区间修改转化为差分数组上的单点修改，单点求值转化为前缀求和，由于 s_i 单调不降，l,r 可以在树状数组上通过倍增求出。

具体地说，设树状数组为 c ，维护的序列是 a ，由于树状数组的性质，c[x] 保存的信息是 \sum_{i=x-\text{lowbit}(x)+1}^xa_i ，区间的长度是二的整数次幂，而在树状数组上求和的过程则类似于对某个数进行二进制拆分。

设 \text{pos} 表示最后一个满足 s_{\text{pos}}>s_{h_i-k_i+1} 的位置，令 \text{sum} 模拟在树状数组上求和。

以 l 的求值为例，初始时 \text{pos}=0,\text{sum}=0 ，从 \log h_i 到 0 倒序考虑每一个数 p ，若满足 \text{pos}+2^p \leq h_i 且 \text{sum}+c[\text{pos}+2^p]>s_{h_i-k_i+1} ，则更新 \text{pos} 和 \text{sum} 的值，让 \text{pos} 前进 2^p 步，最后 l 就是 \text{pos}+1 。

同理， r 也可以通过同样的办法求出，相比在树状数组上二分，倍增将复杂度降至单次 \mathcal{O(\log n)} 。

最后求出每个 s_i ，计算 \sum\dfrac{1}{2}s_i(s_i-1) 求得答案。

总时间复杂度为 \mathcal{O(n\log n)} ，由于树状数组常数较小，在没有特意卡常和精细实现的情况下都能跑到最优解（261ms），吊打一众线段树/平衡树写法（码量也是最小的）。

Code:

#include<bits/stdc++.h>
typedef long long LL;
typedef long double LD;
using namespace std;
const LL N=100010,M=1000010,INF=0x3f3f3f3f;
inline LL max(LL x,LL y){return x>y?x:y;}
inline LL min(LL x,LL y){return x<y?x:y;}
inline void swap(LL &x,LL &y){x^=y^=x^=y;}
LL n,w,ans,c[N];
struct node{LL h,k;}a[N];
bool cmp(node a,node b){return a.h<b.h;}
void add(LL x,LL y){
    for(;x<N;x+=x&-x)c[x]+=y;
}
LL ask(LL x){
    LL res=0;
    for(;x;x-=x&-x)res+=c[x];
    return res;
}
void upd(LL l,LL r,LL d){
    if(l>r)return;
    add(l,d),add(r+1,-d);
}
int main(){
    scanf("%lld",&n);
    for(LL i=1;i<=n;i++)
        scanf("%lld%lld",&a[i].h,&a[i].k);
    sort(a+1,a+n+1,cmp);
    for(LL i=1;i<=n;i++){
        int h=a[i].h,k=a[i].k;
        LL val=ask(h-k+1),l=0,r=0;
        for(LL j=17,sum=0;j>=0;j--)
            if(l+(1<<j)<=h&&sum+c[l+(1<<j)]>val)sum+=c[l+(1<<j)],l+=(1<<j);
        for(LL j=17,sum=0;j>=0;j--)
            if(r+(1<<j)<=h&&sum+c[r+(1<<j)]>=val)sum+=c[r+(1<<j)],r+=(1<<j);
        l=max(l+1,1);r=min(r,h);w=max(w,h);
        upd(r+1,h,1),upd(l,l+r-(h-k+1),1);
    }
    for(LL i=1;i<=w;i++){
        LL p=ask(i);
        ans+=p*(p-1)>>1;
    }
    printf("%lld\n",ans);
    return 0;
}