【线段树+离散化+离线方法】杭电 hdu 3333 Turing Tree

 

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2012 panyanyany All rights reserved.

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=3333
    Name  : 3333 Turing Tree

    Date  : Friday, April 20, 2012
    Time Stage : 2 hours

    Result:
5812358	2012-04-20 20:19:31	Accepted	3333
515MS	3480K	3538 B
C++	pyy								

Test Data :

Review :
离线方法+线段树+离散化
参考了大牛的文章，才AC的
http://www.cnblogs.com/staginner/archive/2012/04/13/2445104.html
我只是做了些注释……
没有想到MAXQ开小了也会TLE
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>

using namespace std ;

#define MEM(a, v)        memset (a, v, sizeof (a))    // a for address, v for value
#define max(x, y)        ((x) > (y) ? (x) : (y))
#define min(x, y)        ((x) < (y) ? (x) : (y))

#define INF     (0x3f3f3f3f)
#define MAXN	30009
#define MAXQ	100010

#define L(x)	((x)<<1)
#define R(x)	(((x)<<1)|1)

#define DB    /##/
typedef __int64	LL;

struct NODE {
	int x, y;
	LL  sum;
};

int		tcase, n, q, iDis;	// iDis 表示 iDiscrete 
int		src[MAXN], ssrc[MAXN], idques[MAXQ], idseg[MAXN];
LL		sum[MAXN*4];

NODE	question[MAXQ];

bool cmp(const int &i, const int &j)
{
	return question[i].y < question[j].y;
}

int rank(int val)
{
	int mid, lw = 0, up = iDis;
	while (lw <= up)
	{
		mid = (lw + up) >> 1;
		if (ssrc[mid] == val)
			break;

		if (val < ssrc[mid])
			up = mid - 1;
		else
			lw = mid + 1;
	}
	return mid;
}

inline void build()
{
	MEM(sum, 0);
}

void update(int id, int lf, int rh, int pos, int f)
{
	if (lf == rh)
	{
		sum[id] = f ? src[pos] : 0;	// 不是 sum[lf] 或 sum[pos]
		return ;
	}

	int mid = (lf + rh) >> 1;
	if (pos <= mid)
		update(L(id), lf, mid, pos, f);
	else
		update(R(id), mid+1, rh, pos, f);

	sum[id] = sum[L(id)] + sum[R(id)];
}

LL query(int id, int lf, int rh, int s, int t)
{
	if (s == lf && t == rh)
		return sum[id];
	
	int mid = (lf + rh) >> 1;
	if (t <= mid)
		return query(L(id), lf, mid, s, t);
	else if (mid < s)
		return query(R(id), mid+1, rh, s, t);

	return query(L(id), lf, mid, s, mid) + query(R(id), mid+1, rh, mid+1, t);
}

int main()
{
	int i, j, k;
	while (scanf("%d", &tcase) != EOF)
	{
		while (tcase--)
		{
			scanf("%d", &n);
			for (i = 0; i < n; ++i)
			{
				scanf("%d", src+i);
				ssrc[i] = src[i];	// ssrc 表示被排序过的src 即 sorted src
			}
			// 离散化
			sort(ssrc, ssrc+n);
			for (i = iDis = 1; i < n; ++i)
			{
				if (ssrc[iDis-1] != ssrc[i])
					ssrc[iDis++] = ssrc[i];
			} // 离散化完

			scanf("%d", &q);
			for (i = 0; i < q; ++i)
			{
				scanf("%d %d", &question[i].x, &question[i].y);
				--question[i].x; --question[i].y;
				idques[i] = i;
			}

			// 对 question 的下标进行排序，相当于间接排序了 question 数组
			sort(idques, idques+q, cmp);

			MEM(idseg, -1);

			// build
			build();
			for (i = j = 0; i < n; ++i)
			{
				k = rank(src[i]);
				if (-1 != idseg[k])
					// 到上一次 src[i] 出现的位置（idseg[k]），将 src[i] 删除.
					update(1, 0, n-1, idseg[k], 0);
				idseg[k] = i;	// 记录此次 src[i] 出现的位置
				update(1, 0, n-1, i, 1);// 将 src[i] 加入线段树中

				// 对排序过的查询区间进行处理
				while (j < q && question[idques[j]].y == i)
				{
					question[idques[j]].sum = query(1, 0, n-1,
						question[idques[j]].x, i);
					++j;
				}
			}

			// 按原顺序输出结果
			for (i = 0; i < q; ++i)
				printf ("%I64d\n", question[i].sum);
		}
	}
	return 0;
}