[原创]SPOJ DQUERY - D-query [树状数组+离线 || 主席树 ]【数据结构】
[原创]SPOJ DQUERY - D-query [树状数组+离线 || 主席树 ]【数据结构】
2017-03-11 14:18:35 Tabris_ 阅读数:312
博客爬取于2020-06-14 22:41:21
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/61416622
题目连接:http://www.spoj.com/problems/DQUERY/
——————————————————————————————————————————
DQUERY - D-query
#sorting #tree
English Vietnamese
Given a sequence of n numbers a1, a2, …, an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, …, aj.
Input
Line 1: n (1 ≤ n ≤ 30000).
Line 2: n numbers a1, a2, …, an (1 ≤ ai ≤ 106).
Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).
Output
For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, …, aj in a single line.
Example
Input
5
1 1 2 1 3
3
1 5
2 4
3 5
Output
3
2
3
——————————————————————————————————————————
题目大意:
就是给你一个序列 ,和q次询问,
询问区间不同元素的个数
解题思路:
本来是做的主席树专题 ,然而主席树怎么做 还不会,
于是就用离线树状数组的做法水了一发
主要就是对询问的r值 排序。
然后遍历一遍序列,
每次对在树状数组上更新最后一次出现的位置,如果已经出现了 就将之前出现过的删掉就好了
每次维护查询 就是计算区间标记的个数
============== 主席树的做法 Update===================
仔细想了想主席树的做法,
其实思路上和离线的树状数组并没有什么区别,
但是因为主席树的特性,我们可以维护一颗颗树,所以能拿到线上解决这个问题
在一颗颗树进行更新的时候,当这个值出现过,我们就将之前的删去,然后在更新,就好了
对树的维护和线段树基本相同,不赘述了
但是在处理的时候发现一个问题
1 | int tem; |
上面的能AC 而下面的却不能
1 | for(int i=1;i<=n;i++){ |
最后也没弄明白怎么回事
附本题代码
——————————————————————————————————————————
1 | /*** |