洛谷 P3616 富金森林公园题解（树状数组）

P3616 富金森林公园

题目描述

博艾的富金森林公园里有一个长长的富金山脉，山脉是由一块块巨石并列构成的，编号从1到N。每一个巨石有一个海拔高度。而这个山脉又在一个盆地中，盆地里可能会积水，积水也有一个海拔高度，所有严格低于这个海拔高度的巨石，就会在水面下隐藏。

由于地壳运动，巨石的海拔高度可能会随时变化，每次一块的巨石会变成新的海拔高度。当然，水面的高度也会随时发生变化。

因为有这样奇妙的地质奇观，吸引了很多游客来游玩。uim作为一个游客，可以告诉你此时水位海拔，你得告诉他，能看到有几个连续露出水面的部分。（与水面持平我们也认为是露出）

输入输出格式

输入格式：

第一行两个整数N和M,分别表示N块石头，M个询问。

接下来一行，N个整数Ai表示每个巨石的初始海拔。

接下来M行，每行有两个或者三个数，每一行如果第一个数是1，那么后面跟一个Bj，表示水面海拔。如果第一个数是2，后面跟两个整数，Cj和Dj，表示编号Cj的巨石海拔变为Dj。

输出格式：

对于每个"1"询问，给出一个整数答案，也就是露出了几部分的山峰。

输入输出样例

输入样例#1：

5 4

8 6 3 5 4

1 5

2 4 1

1 5

1 3

输出样例#1：

2

1

2

说明

10%的数据， N,M<=2000

另外30%的数据，只有"1"的询问。

100%的数据， 1<=N,M<=200000,1<=Ai,Bj,Dj<=10^9，一定有"1"询问

这题解法还是挺巧妙的

先考虑暴力

对于水平面高度为x

当h[i-1] < x <= h[i]时 ans++

正解：

观察暴力，对于h[i], h[i-1] 我们就给ans[h[i-1]+1 ~ h[i]] 加1

那么我们可以先对所有高度离散化一下，再搞一颗树状数组或线段树，区间修改单点询问

code:

#include<bits/stdc++.h>

using namespace std;

const int N = 200010;

struct node {

 	int v, id;

 	bool flag; // 0山的高度 1询问出现的高度

 	bool operator <(node z) const {

	 	return v < z.v;

	}

}h[N<<1];

struct question {

	int k, c, d;

}q[N];

int a[N];

#define lowbit(x) (x&(-x))

int t[N<<1], n, m, s;

inline void add(int x, int k) {

	while (x <= s) {

		t[x] += k;

		x += lowbit(x);

	}

	return ;

}

inline int get(int x) {

	int sum = 0;

	while (x) {

		sum += t[x];

		x -= lowbit(x);

	}

	return sum;

}

int main() {

	scanf("%d%d", &n, &m);

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

		h[i].id = i;

		scanf("%d", &h[i].v);

	}

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

		scanf("%d", &q[i].k);

		if (q[i].k == 1)

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

		else scanf("%d%d", &q[i].c, &q[i].d);

		h[i+n].id = i; h[i+n].flag = 1;

		h[i+n].v = q[i].d;

	}

	sort(h+1, h+1+n+m);

	s = 0;

	for (int i = 1; i <= m+n; i++) {

		if (h[i].v != h[i-1].v || i == 1) s++;

		if (!h[i].flag)

			a[h[i].id] = s;

		else q[h[i].id].d = s;

	}

	for (int i = 1; i <= n; i++)

		if (a[i] > a[i-1]) add(a[i-1]+1, 1), add(a[i]+1, -1);

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

		if (q[i].k == 1)

			printf("%d\n", get(q[i].d));

		else {

			if (a[q[i].c] > a[q[i].c-1]) add(a[q[i].c-1]+1, -1), add(a[q[i].c]+1, 1);

			if (a[q[i].c+1] > a[q[i].c]) add(a[q[i].c]+1, -1), add(a[q[i].c+1]+1, 1);

			a[q[i].c] = q[i].d;

			if (a[q[i].c] > a[q[i].c-1]) add(a[q[i].c-1]+1, 1), add(a[q[i].c]+1, -1);

			if (a[q[i].c+1] > a[q[i].c]) add(a[q[i].c]+1, 1), add(a[q[i].c+1]+1, -1);

		}

	}

	return 0;

}

巴特西

洛谷 P3616 富金森林公园题解（树状数组）

P3616 富金森林公园

code:

最新文章

热门文章