Algorithm
Problem link- https://www.spoj.com/problems/DQUERY/
DQUERY - D-query
| 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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int N = 3e4+5;
const int M = 2e5+5;
const int SQN = sqrt(N) + 1;
int n, q;
struct query{
int l, r;
int idx;
int block;
query(){}
query(int _l, int _r, int _id){
l = _l;
r = _r;
idx = _id;
block = l/SQN;
}
bool operator < (const query &b) const{
if(block != b.block){
return block < b.block;
}
return r < b.r;
}
};
int arr[N];
query Q[M];
int print[M];
int cnt[1000005];
int main(){
scanf("%d", &n);
for(int i = 1;i <= n; i++){
scanf("%d", arr+i);
}
cin >> q;
for(int i = 1;i <= q; i++){
int l, r;
scanf("%d%d", &l, &r);
Q[i] = query(l, r, i);
}
sort(Q+1, Q+1+q);
int curl = 1, curr = 0;
ll ans = 0;
for(int i = 1;i <= q; i++){
int l = Q[i].l;
int r = Q[i].r;
int id = Q[i].idx;
while(curr < r){
++curr;
cnt[arr[curr]]++;
if(cnt[arr[curr]] == 1>
ans++;
}
while(curl > l){
--curl;
cnt[arr[curl]]++;
if(cnt[arr[curl]] == 1)
ans++;
}
while(curr > r){
cnt[arr[curr]]--;
if(cnt[arr[curr]] == 0)
ans--;
--curr;
}
while(curl < l){
cnt[arr[curl]]--;
if(cnt[arr[curl]] == 0)
ans--;
++curl;
}
print[id] = ans;
}
for(int i = 1; i <= q; i++)
printf("%d\n", print[i]);
return 0;
}Input
5
1 1 2 1 3
3
1 5
2 4
3 5
1 1 2 1 3
3
1 5
2 4
3 5
Output
3
2
3
2
3
#2 Code Example with Java Programming
Code -
Java Programming
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
/**
* Created by sreps on 7/31/2016.
*/
public class DQUERY {
static Integer input[];
static Integer answer;
static HashMap < Integer, Integer> count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Integer N = Integer.parseInt(br.readLine());
String temp[] = br.readLine().split(" ");
input = new Integer[N + 1];
answer = 0;
count = new HashMap < >();
for (int i = 1; i <= N; i++) {
input[i] = Integer.parseInt(temp[i - 1]);
}
Integer Q = Integer.parseInt(br.readLine());
ArrayList<Query> queries = new ArrayList<>();
for (int i = 0; i < Q; i++) {
temp = br.readLine().split(" ");
Integer left = Integer.parseInt(temp[0]);
Integer right = Integer.parseInt(temp[1]);
queries.add(new Query(left, right));
}
int currentLeft = 1, currentRight = 1;
for (Query query : queries) {
int left = query.left;
int right = query.right;
while (left < currentLeft) {
currentLeft--;
addition(currentLeft);
}
while (left > currentLeft) {
removal(left);
left--;
}
while (right < currentRight) {
addition(right);
right++;
}
while (right > currentRight) {
removal(right);
right--;
}
System.out.println(answer);
currentLeft = query.left;
currentRight = query.right;
}
}
static class Query {
public Integer left;
public Integer right;
Query(Integer left, Integer right) {
this.left = left;
this.right = right;
}
}
public static void addition(int position) {
Integer current = count.get(input[position]);
if (current == null) {
count.put(input[position], 1);
answer++;
return;
}
if (current == 0) {
answer++;
current = 0;
}
count.put(input[position], current + 1);
}
public static void removal(int position) {
Integer current = count.get(input[position]);
if (current == null) {
return;
}
if (current == 1) {
answer--;
}
count.put(input[position], current - 1);
}
}Input
5
1 1 2 1 3
3
1 5
2 4
3 5
1 1 2 1 3
3
1 5
2 4
3 5
Output
3
2
3
2
3
Demonstration
SPOJ Solution-D-query-Solution in C, C++, Java, Python