POJ 2528 线段树

本体思路其实很简单,离散化后线段树段修改,最后统计一遍即可。

不过此题数据甚是恶心,HASH改了好几遍才AC,想想以后离散化还是不用HASH比较好= =。。

不过也借由此题促使咱回去看《统计的力量》熟悉重口味版线段树,收获良多>u<。。

# include <cstdio>
# include <algorithm>
# include <cstring>
using namespace std;
const int MOD = 50007;
int t, n;

struct POST
{
	int l, r, id;
	bool show;
	POST(){ show = false; }
}p[10003];

int list[40003], tot, f[MOD+2], trans[MOD+2];
int hash(int x)
{
	int pos;
	pos = (3*x + x%107 + x>>2) % MOD;
	while ( f[pos] && f[pos] != x ) pos = (pos + 173)%MOD;
	if ( pos < 0 ) pos += MOD;
	return pos;
}

int M, tree[131077], tf[131007], time;
const int tsize = sizeof(tree), fsize = sizeof(f);
void modify(int s, int t, int c)
{
	++time;
	for ( s+=M-1, t+=M+1; s^t^1; s>>=1, t>>=1 )
	{
		if (~s&1 ) tree[s^1] = c, tf[s^1] = time;
		if ( t&1 ) tree[t^1] = c, tf[t^1] = time;
	}
}
void ask(int x, int mt, int c)
{
	if ( x <= M + tot && tree[x] && tf[x] > mt ) c = tree[x], mt = tf[x];
	if ( x >= M )
	{
		if (c) p1.show = true;
		return ;
	}
	ask(x<<1, mt, c);
	ask((x<<1)+1, mt, c);
}

void work()
{
	int i, a, b;
	tot = time = 0;
	memset(f, 0, sizeof(f));
	scanf("%d", &n);
	if ( n == 0 )
	{
		printf("0\n");
		return ;
	}
	for ( i = 1; i <= n; ++i ) scanf("%d%d", &p[i].l, &p[i].r);
	for ( i = 1; i <= n; ++i )
	{
		p[i].id = i;
		p[i].show = false;
		a = hash(p[i].l);
		b = hash(p[i].r);
		if ( !f[a] ) f[a] = p[i].l, list[++tot] = p[i].l;
		if ( !f[b] ) f[b] = p[i].r, list[++tot] = p[i].r;
	}
	sort(list+1, list+1+tot);
	a = tot;
	for (i = 1; i < a; ++i )
		if ( list[i] + 1 < list[i+1] ) list[++tot] = list[i] + 1;
	sort(list+1, list+1+tot);

	for ( i = 1; i <= tot; ++i ) trans[hash(list[i])] = i;
	for ( i = 1; i <= n; ++i )
	{
		p[i].l = trans[hash(p[i].l)];
		p[i].r = trans[hash(p[i].r)];
	}
	for ( M = 1; M < tot+2; M<<=1 );
	memset(tree, 0, tsize);

	for ( i = 1; i <= n; ++i ) modify(p[i].l, p[i].r, p[i].id);
	ask(1, 0, 0);
	for ( a = 0, i = 1; i<= n; ++i ) if ( p[i].show ) ++a;
	printf("%d\n", a);
}

int main()
{
	scanf("%d", &t);
	while ( t-- ) work();
	return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>