【35.39%】【hdu 3333】Turing Tree
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4776 Accepted Submission(s): 1690
Problem Description
After inventing Turing Tree, 3xian always felt boring when solving problems about intervals, because Turing Tree could easily have the solution. As well, wily 3xian made lots of new problems about intervals. So, today, this sick thing happens again…
Now given a sequence of N numbers A1, A2, …, AN and a number of Queries(i, j) (1≤i≤j≤N). For each Query(i, j), you are to caculate the sum of distinct values in the subsequence Ai, Ai+1, …, Aj.
Input
The first line is an integer T (1 ≤ T ≤ 10), indecating the number of testcases below.
For each case, the input format will be like this:
* Line 1: N (1 ≤ N ≤ 30,000).
* Line 2: N integers A1, A2, …, AN (0 ≤ Ai ≤ 1,000,000,000).
* Line 3: Q (1 ≤ Q ≤ 100,000), the number of Queries.
* Next Q lines: each line contains 2 integers i, j representing a Query (1 ≤ i ≤ j ≤ N).
Output
For each Query, print the sum of distinct values of the specified subsequence in one line.
Sample Input
2
3
1 1 4
2
1 2
2 3
5
1 1 2 1 3
3
1 5
2 4
3 5
Sample Output
1
5
6
3
6
Author
3xian@GDUT
Source
HDOJ Monthly Contest – 2010.03.06
题解
求一段区间内的不同元素的和。
需要离线处理询问。
先讲询问按照右端点升序排序;
之后顺序扫描每一个数字,如果这个数字之前出现过(用map判断),那么就更新那个那个数字最后的位置为当前位置。并把之前那个数字去掉。
这样可以保证我们维护了一段数字全都不相同的序列a[1..当前的位置],这个序列中用0代表重复的数字,然后处理右区间为当前位置的询问即可。
然后用线段树维护区间和,单点更新,单点上传。很简单。
之前一道类似的题用的是树状数组,所以这次用的线段树。很久没打线段树了。有点生疏。
#include <cstdio>
#include <algorithm>
#include <map>
#include <iostream>
#define lson begin,m,rt<<1
#define rson m+1,end,rt<<1|1
#define LL long long
using namespace std;
const int MAXN = 30000 + 100;
const int MAXQ = 1e5 + 100;
struct abc
{
int l, r, id;
};
int a[MAXN], m, n;
LL sum[MAXN << 2],ans[MAXQ];
map <int, int> frequent;
abc Q[MAXQ];
void input(int &r)
{
r = 0;
char t = getchar();
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
}
void build(int begin, int end,int rt)
{
sum[rt] = 0;
if (begin == end)
return;
int m = (begin + end) >> 1;
build(lson);
build(rson);
}
bool cmp(abc a, abc b)
{
return a.r < b.r;
}
void add(int begin, int end,int rt, int pos, int key)
{
if (begin == end)
{
sum[rt] += key;
return;
}
int m = (begin + end) >> 1;
if (pos <= m)
add(lson, pos, key);
else
add(rson, pos, key);
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
LL query(int l, int r, int begin, int end, int rt)
{
if (l <= begin && end <= r)
return sum[rt];
LL temp1 = 0,temp2 = 0;
int m = (begin + end) >> 1;
if (l <= m)
temp1 += query(l, r, lson);
if (m < r)
temp2 += query(l, r, rson);
return temp1 + temp2;
}
int main()
{
//freopen("F:\\rush.txt", "r", stdin);
int t;
input(t);
while (t--)
{
frequent.clear();
input(n);
build(1, n, 1);
for (int i = 1; i <= n; i++)
input(a[i]);
input(m);
for (int i = 1; i <= m; i++)
input(Q[i].l), input(Q[i].r), Q[i].id = i;
sort(Q + 1, Q + 1 + m, cmp);
int temp = 1;
for (int i = 1; i <= n; i++)
{
if (frequent[a[i]])
add( 1, n,1, frequent[a[i]],-a[i]);
frequent[a[i]] = i;
add(1, n, 1, i, a[i]);
while (temp <= m && Q[temp].r == i)
{
ans[Q[temp].id] = query(Q[temp].l, Q[temp].r, 1, n, 1);
temp++;
}
}
for (int i = 1; i <= m; i++)
printf("%I64d\n", ans[i]);
}
return 0;
}
最新文章
- DDD实践切入点(二)
- browserify压缩合并源码反编译
- C#(委托a)
- Nginx反向代理关于端口的问题
- JAVA equals, ==
- php 常用的好函数(持续更新)
- 章节2:SQL之多表连接
- partial类修饰符
- memcache缓存安装配置
- CentOS下RPM方式安装MySQL5.6(转载)
- 推荐一套Angular2的UI模板
- python深拷贝,浅拷贝
- 《http权威指南》读书笔记9
- 五种IO模型透彻分析
- Nginx 配置下载附件让浏览器提示用户是否保存
- ffmpeg命令的使用
- php 查看当前页中的post及get数据
- 团队项目个人进展——Day06
- Socket之简单的Unity3D聊天室__TCP协议
- 洛谷 P2022 有趣的数 解题报告
热门文章
- Codeforces Round #258 (Div. 2)——B. Sort the Array
- js进阶 12-13 jquery中one方法和trigger方法如何使用
- Maven 使用Eclipse构建Maven的SpringMVC项目
- iOS图片加载-SDWebImage
- APK瘦身记,怎样实现高达53%的压缩效果
- js cookie介绍和实例(用于自动登录,记住用户名等)
- 洛谷 偷天换日&;&;“访问”美术馆
- 从Lua调用C
- iOS开发webView的使用一
- 关于serialVersionUID的说明 分类: B1_JAVA 2014-05-24 11:02 1334人阅读 评论(0) 收藏