自动搬运

查看原文

来自洛谷，原作者为

	Diaоsi Enemy of God

搬运于2025-08-24 22:02:15，当前版本为作者最后更新于2022-06-30 14:28:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[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;
}