当前位置:网站首页>1004 (tree array + offline operation + discretization)
1004 (tree array + offline operation + discretization)
2022-08-10 14:23:00 【51CTO】
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
Sample Output
Topics and ideas:
Find the sum of disjoint numbers.Use offline operation.
The first is to discretize.Also save the range,按照右端点排序.进行预处理.
Then loop from the first number,Put the numbers into a tree-like array,if it exists in the array,就再减去.Each to a right endpoint,Put and saveans里.最后输出.
代码:
边栏推荐
- 雨水中存在的PFAS化学物质对饮用水安全构成了威胁
- AWS 安全基础知识
- 【POI 2008, BLO】割点
- 字节终面:CPU 是如何读写内存的?
- 第三方软件测评有什么作用?权威软件检测机构推荐
- Lack of comparators, op amps come to the rescue!(Op amp is recorded as a comparator circuit)
- 文件系统设计
- 公网IP和内网IP的区别[通俗易懂]
- Error: Rule can only have one resource source (provided resource and test + include + exclude)
- Fragment-hide and show
猜你喜欢
随机推荐
数据产品经理那点事儿 二
[target detection] small script: extract training set images and labels and update the index
R语言使用gt包和gtExtras包优雅地、漂亮地显示表格数据:gtExtras包的gt_highlight_rows函数高亮(highlight)表格中特定的数据行、配置高亮行的特定数据列数据加粗
vivado闪退或者message无显示
Drive IT Modernization with Low Code
the height of the landscape
【POI 2008, BLO】割点
1W字详解线程本地存储 ThreadLocal
借数据智能,亚马逊云科技助力企业打造品牌内生增长力
强意识 压责任 安全培训筑牢生产屏障
C# WPF image is displayed without problems, but the solution does not display the image at runtime
缺少比较器,运放来救场!(运放当做比较器电路记录)
黑客入门,从HTB开始
leetcode 739. Daily Temperatures 每日温度(中等)
作业8.9 构建TCP协议的服务器
领域驱动实践总结(基本理论总结与分析V+架构分析与代码设计+具体应用设计分析)
d为何用模板参数
AWS Security Fundamentals
Unfinished mathematics test paper ----- test paper generator (Qt includes source code)
leetcode 739. Daily Temperatures Daily Temperatures (Moderate)