【线段树+离散化+离线方法】杭电 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:58123582012-04-20 20:19:31Accepted3333515MS3480K3538 BC++pyyTest 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 MAXN30009#define MAXQ100010#define L(x)((x)<<1)#define R(x)(((x)<<1)|1)#define DB /##/typedef __int64LL;struct NODE {int x, y;LL sum;};inttcase, n, q, iDis;// iDis 表示 iDiscrete intsrc[MAXN], ssrc[MAXN], idques[MAXQ], idseg[MAXN];LLsum[MAXN*4];NODEquestion[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;elselw = 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);elseupdate(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);// buildbuild();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;}?