Necklace HDU - 3874 (线段树/树状数组 + 离线处理)
Now Mery thinks the necklace is too long. She plans to take some continuous part of the necklace to build a new one. She wants to know each of the beautiful value of M continuous parts of the necklace. She will give you M intervals [L,R] (1<=L<=R<=N) and you must tell her F(L,R) of them.
InputThe first line is T(T<=10), representing the number of test cases.
For each case, the first line is a number N,1 <=N <=50000, indicating the number of the magic balls. The second line contains N non-negative integer numbers not greater 1000000, representing the beautiful value of the N balls. The third line has a number M, 1 <=M <=200000, meaning the nunber of the queries. Each of the next M lines contains L and R, the query.OutputFor each query, output a line contains an integer number, representing the result of the query.Sample Input
2
6
1 2 3 4 3 5
3
1 2
3 5
2 6
6
1 1 1 2 3 5
3
1 1
2 4
3 5
Sample Output
3
7
14
1
3
6
题意:给n个数字,代表项链每个单位的价值。在给m组查询,代表需要查询的[l,r]中的项链价值的总和;
项链区间价值的计算方法:区间中不同数字的和,即是该区间项链价值的总和。
做法:因为查询的区间已知,采用线段树/树状数组 + 离线查找的方法
将需要查找的区间根据 右端点 从小到大排序。从左往右逐步把数据加入到线段树中,当达到某一查询区间的右端点时,进行一次区间和的计算。
建立一个map数组,若某个数已经在序列中,则在最近出现的位置删除该数,这样就能保证每个数任意时刻只在线段树的中存储一次。
(举个栗子:如样例输入中 map[1] = 1,当第二个1放入线段树的时候,需要将第一个1清除,并更新map[1] = 2,以此保证线段树中该价值仅存在一个,
并且如果区间可以覆盖上一个map[1],那么区间必定可以覆盖现在的map[1]。)
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<string>
#include<set>
#include<stack>
#include<queue>
using namespace std;
const int maxn = ;
typedef long long ll;
struct node{
int l,r;
ll sum;
}tree[maxn];//建立线段树
ll T,n,m;
ll value[maxn],ans[maxn];// ans数组储存答案,value储存每个单位项链的价值
map<ll,int> mp;// 储存价值i在数组中最近出现的位置
struct node2
{
int l,r;
int index;//题目中要求的访问的顺序
}q[maxn]; void build(int rt,int left,int right){
tree[rt].l = left;
tree[rt].r = right;
tree[rt].sum = ;// 令每个根节点的值都为零,在计算的过程中再更新节点的值
if(left == right){
return;
}else{
int mid = (left + right)>>;
build(rt<<,left,mid);
build((rt<<)|, mid + , right);
}
}
void updata(int rt,int pos,ll val){//逐步将数据放入线段树中
tree[rt].sum += val;
if(tree[rt].l == tree[rt].r && tree[rt].l == pos){
return;
}
int mid = (tree[rt].l + tree[rt].r)>>;
if(pos <= mid){
updata(rt<<,pos,val);
}else{
updata((rt<<)|,pos,val);
}
}
ll query(int rt,int left,int right){
if(tree[rt].l == left && tree[rt].r == right){
return tree[rt].sum;
}
int mid = (tree[rt].l + tree[rt].r)>>;
if(right <= mid){
return query(rt<<,left,right);
}else if(left > mid){
return query((rt<<)| ,left ,right);
}else{
return query(rt<<,left,mid) + query((rt<<)| ,mid + ,right);
}
} bool cmp(node2 & a, node2 & b){//按照查询区间的右端点从小到大排序
return a.r < b.r;
}
int main(){
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
build(,,n);
mp.clear();
for(int i = ; i <= n ; i++){
scanf("%lld",&value[i]);
}
scanf("%lld",&m);
for(int i = ; i <= m ;i++){
scanf("%d %d",&q[i].l,&q[i].r);
q[i].index = i;
}
sort(q + , q + + m , cmp);
int id = ;//代表目前已经计算了几次题目想要查询的区间值
for(int i = ; i <= n ; i++){ updata(,i,value[i]);//按顺序从左到右将数组中的数据放入线段树中
if(mp[value[i]]) updata(,mp[value[i]],-value[i]); //如果价值value[i],将之前的数据进行删除,并将线段树更新
mp[value[i]] = i;// 更新value[i]最新出现的位置 while(id <= m && q[id].r == i){//当计算次数小于总次数,并且线段树对应下标等于某个查询区间的右端点时,进行一次查询
ans[q[id].index] = query(,q[id].l, q[id].r);
id++;
}
}
for(int i = ; i <= m ; i++){
printf("%lld\n",ans[i]);
}
}
return ;
}
线段树+离线处理做法
一个从很久以前就开始做的梦。
最新文章
- 如何获取网页上的LOGO
- jquery 动态添加表格行
- MySQL 请选择合适的列! 转载(http://www.cnblogs.com/baochuan/archive/2012/05/23/2513224.html)
- UIStepper
- eclipse 工程加入ant以支持自动打war包
- 手把手教你玩转SOCKET模型之重叠I/O篇(上)
- CodeForces 474.D Flowers
- Codeforces Round #341 (Div. 2) ABCDE
- spring mvc获取路径参数的几种方式 - 浅夏的个人空间 - 开源中国社区
- jQuery中的常用内容总结(三)
- hadoop学习大纲
- 前端工程化(三)---Vue的开发模式
- 【VS工具】vs2017中的一些小功能
- MySQL5.7的安装配置
- SpringBoot------全局异常捕获
- LeetCode--125--验证回文串
- poj1511
- JavaSE(八)之Map总结
- Java网络编程学习A轮_07_基于Buffer的Socket编程
- centOS上安装MySQL5.7
热门文章
- 三十、SAP中的内置图标
- Windows + Python + flup + flask + fastcgi + Nginx配置
- NumPy 矩阵库函数
- 编程入门-Eclipse基本使用
- 15. react UI组件和容器组件的拆分 及 无状态组件
- 目标检测评价标准(mAP, 精准度(Precision), 召回率(Recall), 准确率(Accuracy),交除并(IoU))
- oracle 查询char类型的数据
- 十八、CI框架之数据库操作update用法
- 十一、CI框架之输出用户IP地址
- js 格式化时间日期