树状数组练习--Necklace(树状数组+离线处理)

2023-11-06 22:38

本文主要是介绍树状数组练习--Necklace(树状数组+离线处理),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原题:

Problem Description
Mery has a beautiful necklace. The necklace is made up of N magic balls. Each ball has a beautiful value. The balls with the same beautiful value look the same, so if two or more balls have the same beautiful value, we just count it once. We define the beautiful value of some interval [x,y] as F(x,y). F(x,y) is calculated as the sum of the beautiful value from the xth ball to the yth ball and the same value is ONLY COUNTED ONCE. For example, if the necklace is 1 1 1 2 3 1, we have F(1,3)=1, F(2,4)=3, F(2,6)=6.

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.

Input
The 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.

Output
For 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

题目链接:http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?cid=11842&pid=1006&ojid=0&hide=1&problem=Problem%20F

题意:

给出n个数,给出m个区间,让求这一区间的元素和。

如果有一样的数字,只算一遍。

例如Sample 2,1 2 区间段和是1.

思路:求区间段和,首先想到的就是用树状数组。那么怎么考虑一样的数字的问题呢?就要用到离线处理了。首先将所求区间和进行储存并记录其出现的初始位置。然后对所有区间按照右端点进行排序。然后用一个变量进行记录。如果该元素之前出现过,那么在之前位置往后减去该元素,然后再在当前位置后加上该元素。直到区间结束,更新过后求结果。对结果进行保存。

源代码:

/*1006离线处理。先将区间保存,然后按照右端点升序排列。离线处理要记录初始的区间位置然后从头开始查找。若该点的元素出现过,则从原来位置开始减去该元素。若没有出现过,则加上该元素。最后求和。*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stdio.h>
#include <vector>
#define MAX 1000000
using namespace std;
long long C[MAX];
long long a[MAX];
long long flag[MAX];
long long jieguo[MAX];
struct Qujian
{int i;int j;int id;
}qujian[MAX];
bool cmp(Qujian a,Qujian b)
{return a.j < b.j;
}
long long lowbit(long long x)
{return x & (-x);
}
long long getsum(long long x)
{long long sum = 0;while (x > 0){sum += C[x];x -= lowbit(x);}return sum;
}
void add(long long x,long long v)
{while (x < MAX){C[x] += v;x += lowbit(x);}
}
int main()
{int n;scanf("%d",&n);while (n--){int m;memset(flag,0,sizeof(flag));memset(C,0,sizeof(C));memset(a,0,sizeof(a));scanf("%d",&m);for (int i = 1; i <= m; i++)scanf("%lld",&a[i]);int k;scanf("%d",&k);for (int p = 1; p <= k; p++){scanf("%d%d",&qujian[p].i,&qujian[p].j);qujian[p].id = p;}sort(qujian+1,qujian+k+1,cmp);//for (int i = 1; i <= k; i++)//{//    cout << qujian[i].i << endl << qujian[i].j << endl;//    cout << qujian[i].id << endl;//}long long flag1 = 1;for (int i = 1; i <= k; i++){while (flag1 <= qujian[i].j){long long b;b = a[flag1];if (flag[b])add(flag[b],-b);add(flag1,b);flag[b] = flag1;flag1++;}//cout << getsum(qujian[i].j) << endl << getsum(qujian[i]. i - 1)<< endl;jieguo[qujian[i].id] = getsum(qujian[i].j) - getsum(qujian[i].i-1);}for (int i = 1; i <= k; i++)printf("%lld\n",jieguo[i]);}return 0;
}



这篇关于树状数组练习--Necklace(树状数组+离线处理)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/359470

相关文章

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题:墙体两侧特征混淆误匹配,导致建图和定位偏差,表现为过门跳变、外月台走歪等 ·解决思路:预期的根治方案IGICP需要较长时间完成上线,先使用切分地图的工程化方案,即墙体两侧切分为不同地图,在某一侧只使用该侧地图进行定位 方案思路 切分原理:切分地图基于关键帧位置,而非点云。 理论基础:光照是直线的,一帧点云必定只能照射到墙的一侧,无法同时照到两侧实践考虑:关

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

RabbitMQ练习(AMQP 0-9-1 Overview)

1、What is AMQP 0-9-1 AMQP 0-9-1(高级消息队列协议)是一种网络协议,它允许遵从该协议的客户端(Publisher或者Consumer)应用程序与遵从该协议的消息中间件代理(Broker,如RabbitMQ)进行通信。 AMQP 0-9-1模型的核心概念包括消息发布者(producers/publisher)、消息(messages)、交换机(exchanges)、

Thymeleaf:生成静态文件及异常处理java.lang.NoClassDefFoundError: ognl/PropertyAccessor

我们需要引入包: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-thymeleaf</artifactId></dependency><dependency><groupId>org.springframework</groupId><artifactId>sp

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou

【Rust练习】12.枚举

练习题来自:https://practice-zh.course.rs/compound-types/enum.html 1 // 修复错误enum Number {Zero,One,Two,}enum Number1 {Zero = 0,One,Two,}// C语言风格的枚举定义enum Number2 {Zero = 0.0,One = 1.0,Two = 2.0,}fn m