/* 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;
}
分享到:
相关推荐
Hdu 3333解题报告 题意描述: 给你n个数现在要你求在k个区间上[ai, bi]的不相同的数之和各是多少. N,000; k,000; 显然,这题不能用暴力来做。 这题我们选择用线段数来做。
杭州电子科技大学ACM培训课件 来自杭电ACM官方论坛 拿来和大家分享一下 想到有些朋友论坛积分不够 现在特地拿来免费供大家下载 希望对ACM初学者能够有所帮助
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
计算机网络复习大纲_杭电hdu.pdf
计算机网络复习大纲_杭电hdu借鉴.pdf
计算机网络复习大纲_杭电hdu整理.pdf
计算机网络复习大纲_杭电hdu参考.pdf
杭电ACM1005题源代码,AC了的程序,无问题……
杭州电子科技大学 oj离线版
杭电ACMhdu1163
离线OJ题库(HDU ZJU等,部分有答案),需联网。
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
hdu 1166线段树代码
杭电hdu acm资料所用杭电的acm题
hdu 1166线段树
为了方便广大没有网络的朋友.......
HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字