●洛谷 P3616 富金森林公园

题链：

https://www.luogu.org/problemnew/show/3616

题解：

树状数组，，，

本题思路挺巧妙。

考虑这种暴力算法：（设H[i]为i位置的高度,水面的高度为B）

从左枚举到右，如果 H[i-1]<B<=H[i]，那么就可以贡献答案，即 ANS++。

基于上述暴力，可以得出：

如果 H[i-1] < H[i]，且询问的 B 在这两个H值之间，则会贡献答案。

所以，用数据结构维护区间修改（把区间H[i-1]+1～H[i]的值加一）和单点查询（查询当前的水面高度B的ANS）即可。

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 200500

using namespace std;

int H[MAXN],tmp[MAXN*3];

int N,M,tnt;

struct Question{

	int a,b,c;

}Q[MAXN];

struct BIT{

	int A[MAXN*3],len;

	void Reset(int n){

		len=n; memset(A,0,sizeof(A));

	}

	int Lowbit(int x){return x&-x;}

	void Modify(int l,int r,int x){

		r++;

		while(l<=len) A[l]+=x,l+=Lowbit(l);

		while(r<=len) A[r]-=x,r+=Lowbit(r);

	}

	int Query(int p){

		static int ret; ret=0;

		while(p) ret+=A[p],p-=Lowbit(p);

		return ret;

	}

}DT;

int main(){

	scanf("%d%d",&N,&M); tmp[++tnt]=0;

	for(int i=1;i<=N;i++) scanf("%d",&H[i]),tmp[++tnt]=H[i];

	for(int i=1;i<=M;i++){

		scanf("%d",&Q[i].a);

		if(Q[i].a==1) scanf("%d",&Q[i].b),tmp[++tnt]=Q[i].b;

		else scanf("%d%d",&Q[i].b,&Q[i].c),tmp[++tnt]=Q[i].c;

	}

	sort(tmp+1,tmp+tnt+1);

	tnt=unique(tmp+1,tmp+tnt+1)-tmp-1;

	DT.Reset(tnt); H[0]=lower_bound(tmp+1,tmp+tnt+11,H[0])-tmp;

	for(int i=1;i<=N;i++){

		H[i]=lower_bound(tmp+1,tmp+tnt+1,H[i])-tmp;

		if(H[i]>H[i-1]) DT.Modify(H[i-1]+1,H[i],1);

	}

	for(int i=1;i<=M;i++){

		if(Q[i].a==1){

			Q[i].b=lower_bound(tmp+1,tmp+tnt+1,Q[i].b)-tmp;

			printf("%d\n",DT.Query(Q[i].b));

		}

		else{

			if(H[Q[i].b]>H[Q[i].b-1]) DT.Modify(H[Q[i].b-1]+1,H[Q[i].b],-1);

			if(H[Q[i].b+1]>H[Q[i].b]) DT.Modify(H[Q[i].b]+1,H[Q[i].b+1],-1);

			H[Q[i].b]=lower_bound(tmp+1,tmp+tnt+1,Q[i].c)-tmp;

			if(H[Q[i].b]>H[Q[i].b-1]) DT.Modify(H[Q[i].b-1]+1,H[Q[i].b],1);

			if(H[Q[i].b+1]>H[Q[i].b]) DT.Modify(H[Q[i].b]+1,H[Q[i].b+1],1);

		}

	}

	return 0;

}

巴特西

●洛谷 P3616 富金森林公园

最新文章

热门文章