离散化+线段树/二分查找/尺取法 HDOJ 4325 Flowers

题意：给出一些花开花落的时间，问某个时间花开的有几朵

分析：这题有好几种做法，正解应该是离散化坐标后用线段树成端更新和单点询问。还有排序后二分查找询问点之前总花开数和总花凋谢数，作差是当前花开的数量，放张图易理解：

还有一种做法用尺取法的思想，对暴力方法优化，对询问点排序后再扫描一遍，花开+1，花谢-1。详细看代码。

收获：一题收获很多：1. 降低复杂度可以用二分 2. 线段计数问题可以在端点标记1和-1 3. 离散化+线段树终于会了:) (听说数据很水？)

代码1：离散化+线段树

/************************************************

* Author        :Running_Time

* Created Time  :2015-8-25 8:55:54

* File Name     :F.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

typedef pair<int, int> P;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

struct ST	{

	int sum[N<<2], col[N<<2];

	void push_up(int rt)	{

        sum[rt] = sum[rt<<1] + sum[rt<<1|1];

	}

	void push_down(int rt, int len)	{

		if (col[rt])	{

			col[rt<<1] += col[rt];

			col[rt<<1|1] += col[rt];

			sum[rt<<1] += col[rt] * (len - (len >> 1));

			sum[rt<<1|1] += col[rt] * (len >> 1);

			col[rt] = 0;

		}

	}

	void build(int l, int r, int rt)	{

		col[rt] = 0;	sum[rt] = 0;

		if (l == r)	return ;

		int mid = (l + r) >> 1;

		build (lson);	build (rson);

//		push_up (rt);

	}

	void updata(int ql, int qr, int l, int r, int rt)	{

		if (ql <= l && r <= qr)	{

			sum[rt] += (r - l + 1);	col[rt] += 1;	return ;

		}

		push_down (rt, r - l + 1);

		int mid = (l + r) >> 1;

		if (ql <= mid)	updata (ql, qr, lson);

		if (qr > mid)	updata (ql, qr, rson);

//		push_up (rt);

	}

	int query(int ql, int qr, int l, int r, int rt)	{

		if (ql <= l && r <= qr)	return sum[rt];

		push_down (rt, r - l + 1);

		int mid = (l + r) >> 1;

		if (ql <= mid)	return query (ql, qr, lson);

		if (qr > mid)	return query (ql, qr, rson);

	}

}st;

int x1[N], x2[N], q[N];

int X[N*3];

int my_binary_search(int l, int r, int key)	{

	while (l <= r)	{

		int mid = (l + r) >> 1;

		if (X[mid] == key)	return mid;

		if (X[mid] < key)	l = mid + 1;

		else	r = mid - 1;

	}

	return -1;

}

int main(void)	{

	int T, cas = 0;	scanf ("%d", &T);

	while (T--)	{

		int n, m;

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

		int tot = 0;

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

			scanf ("%d%d", &x1[i], &x2[i]);

			X[tot++] = x1[i];	X[tot++] = x2[i];

		}

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

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

			X[tot++] = q[i];

		}

		sort (X, X + tot);

		int k = 1;

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

			if (X[i] != X[i-1])	X[k++] = X[i];

		}

		st.build (0, k, 1);

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

			ql = lower_bound (X, X+k, x1[i]) - X;

			qr = lower_bound (X, X+k, x2[i]) - X;

//			ql = my_binary_search (0, k-1, x1[i]);

//			qr = my_binary_search (0, k-1, x2[i]);

			st.updata (ql, qr, 0, k, 1);

		}

		printf ("Case #%d:\n", ++cas);

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

			p = lower_bound (X, X+k, q[i]) - X;

//			p = my_binary_search (0, k-1, q[i]);

			printf ("%d\n", st.query (p, p, 0, k, 1));

		}

	}

    return 0;

}

代码2：二分查找

/************************************************

* Author        :Running_Time

* Created Time  :2015-8-25 8:55:54

* File Name     :F.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

int x1[N], x2[N];

int n, m;

int main(void)    {

	int T, cas = 0;	scanf ("%d", &T);

	while (T--)	{

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

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

			scanf ("%d%d", &x1[i], &x2[i]);

		}

		sort (x1+1, x1+1+n);	sort (x2+1, x2+1+n);

		printf ("Case #%d:\n", ++cas);

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

			int p;	scanf ("%d", &p);

			printf ("%d\n", lower_bound (x1+1, x1+1+n, p) - (x1 + 1) - (lower_bound (x2+1, x2+1+n, p) - (x2 + 1)));

		}

	}

    return 0;

}

代码3：尺取法

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

P p[N], q[N];

int ans[N];

int n, m;

int main(void)    {

	int T, cas = 0;	scanf ("%d", &T);

	while (T--)	{

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

		int tot = 0;

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

			scanf ("%d%d", &a, &b);

			p[++tot] = P (a, 1);

			p[++tot] = P (b + 1, -1);

		}

		sort (p+1, p+1+tot);

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

			int x;	scanf ("%d", &x);

			q[i] = P (x, i);

		}

		sort (q+1, q+1+m);

		printf ("Case #%d:\n", ++cas);

		for (int j=1, cnt=0, i=1; i<=m; ++i)	{

			while (j <= tot && p[j].first <= q[i].first)	{

				cnt += p[j].second;	++j;

			}

			ans[q[i].second] = cnt;

		}

		for (int i=1; i<=m; ++i)	printf ("%d\n", ans[i]);

	}

    return 0;

}

巴特西

离散化+线段树/二分查找/尺取法 HDOJ 4325 Flowers

最新文章

热门文章