SPOJ DQUERY - D-query（主席树-区间不同数的个数）
赵开诚
大体题意：
给你n 个数，给你q个询问，每个询问问你某个区间上不同数的个数是多少？
思路：
主席树入门题：
简单记录一下：
这里先建立一个完整的线段树，这里的区间就代表区间了，不再是第几大了，
定义的sum 是这个区间上的不同数的个数有几个。
因为是主席树嘛，所以肯定要建立n 棵线段树，每个线段树是以每个位置的数为根，比如说该建立第i 个线段树了，如果这个数字之前没有出现过，那么我们直接以位置为划分依据，在线段树上包含这个位置的加1即可，表示这个区间上又多了一种数。
但是如果这个数字出现过了，我们先求出上一个同样数在哪里出现，我们就在第i 个线段树上以那个位置为划分依据给它减去1，在在第i 个线段树上 包含位置的i 的区间加1，这样我们就保证了 区间中数字不重复，只保留最后一个。
update代码：
int update(int pos,int c,int v,int l,int r){
int nc = ++cnt;
p[nc] = p[c];
p[nc].sum += v;
if (l == r) return nc;
int m = l+r>>1;
if (m >= pos){
p[nc].l = update(pos,p[c].l,v,l,m);
}
else {
p[nc].r = update(pos,p[c].r,v,m+1,r);
}
return nc;
}
在来说查询：
比如说我们要查询[L,R]这个区间上不同数的个数，我们就以L 为划分依据，在第R个线段树上进行查询，当发现往左走时，右边是一个完整的，我们直接加上右儿子的sum即可，在递归左儿子，如果发现是往右走，那么直接递归右边就好了，左边的不用加，因为左边的比L小，肯定会加多。
这样加到底，我们就可以得到一个完整区间[L,R]上不同数的个数。
int query(int pos,int c,int l,int r){
if (l == r) return p[c].sum;
int m = l + r >> 1;
if (m >= pos){
return p[p[c].r ].sum + query(pos,p[c].l,l,m);
}
else return query(pos,p[c].r,m+1,r);
}
完整代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 30000 + 10;
int n,q;
int cnt = 0;
struct Node{
int l,r,sum;
}p[maxn*40];
int la[1000000 + 10];
int a[maxn];
int root[maxn];
int build(int l,int r){
int nc = ++cnt;
p[nc].sum = 0;
p[nc].l = p[nc].r = 0;
if (l == r) return nc;
int m = l + r >> 1;
p[nc].l = build(l,m);
p[nc].r = build(m+1,r);
return nc;
}
int update(int pos,int c,int v,int l,int r){
int nc = ++cnt;
p[nc] = p[c];
p[nc].sum += v;
if (l == r) return nc;
int m = l+r>>1;
if (m >= pos){
p[nc].l = update(pos,p[c].l,v,l,m);
}
else {
p[nc].r = update(pos,p[c].r,v,m+1,r);
}
return nc;
}
int query(int pos,int c,int l,int r){
if (l == r) return p[c].sum;
int m = l + r >> 1;
if (m >= pos){
return p[p[c].r ].sum + query(pos,p[c].l,l,m);
}
else return query(pos,p[c].r,m+1,r);
}
int main(){
scanf("%d",&n);
memset(la,-1,sizeof la);
for (int i = 1; i <= n; ++i){
scanf("%d",a+i);
}
root[0] = build(1,n);
for (int i = 1 ; i <= n; ++i){
int v = a[i];
if (la[v] == -1){
root[i] = update(i,root[i-1],1,1,n);
}
else{
int t = update(la[v],root[i-1],-1,1,n);
root[i] = update(i,t,1,1,n);
}
la[v] = i;
}
scanf("%d",&q);
while(q--){
int x,y;
scanf("%d %d",&x, &y);
printf("%d\n",query(x,root[y],1,n));
}
return 0;
}
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
类似资料：