题意 ： 给出一段n个数的序列，接下来给出m个询问，询问的内容SPOJ是(L, R)这个区间内不同的数的个数，HDU是不同数的和
分析 ：
一个经典的问题，思路是将所有问询区间存起来，然后按右端点排序
最后从左到右将原区间扫一遍，扫的过程当中不断将重复出现的数字右移
也就是如果一个数字重复出现，那么我们记录最右边的那个为有效的，其他都视为不存在
这样一旦遇到一个问询区间的右端点就线段树查询即可。
SPOJ：
#include<bits/stdc++.h>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
;
];
void PushUP(int rt) {
sumv[rt] = sumv[rt<<] + sumv[rt<<|];
}
void update(int p,int sc,int l,int r,int rt) {
if (l == r) {
sumv[rt] += sc;
return ;
}
);
if (p <= m) update(p , sc , lson);
else update(p , sc , rson);
PushUP(rt);
}
long long query(int L,int R,int l,int r,int rt) {
if (L <= l && r <= R) {
return sumv[rt];
}
);
;
if (L <= m) ret += query(L , R , lson);
if (R > m) ret += query(L , R , rson);
return ret;
}
struct Interval{
int l, r, id;
bool operator < (const Interval& other) const{
return this->r < other.r;
}
};
Interval sec[];
map<int, int> mp;
int arr[maxn];
int pre[maxn];
long long ans[maxn];
int main(void)
{
, m;
scanf("%d", &n);
; i<=n; i++){
scanf("%d", &arr[i]);
if(!mp.count(arr[i]))
mp[arr[i]] = cnt++;//区间上的每一个数都有一个独特的编号，使用map来进行映射，目的是方便判断此数是否已经重复出现过
}
scanf("%d", &m);
; i<=m; i++){
scanf("%d %d", &sec[i].l, &sec[i].r);
sec[i].id = i;//因为后续有排序操作，而我们又要对问询答案顺序给出，所以记录给出的顺序，方便输出答案
}
sort(sec+, sec++m);//按照右端点排序
bool vis[maxn];
memset(vis, false, sizeof(vis));
, j=; j<=m && i<=n; i++){
int tmp = mp[arr[i]];//拿出这个数的编号
if(vis[tmp]){//如果这个数在前面已经访问过
update(pre[tmp], -, , n, );//将之前的位置信息抹去
update(i, , , n, );//当前的位置才是有效的，所以给当前位置+1
pre[tmp] = i;//更新pre数组方便下次操作
}else{
vis[tmp] = true;
update(i, , , n, );
pre[tmp] = i;
}
while(sec[j].r == i){
ans[sec[j].id] = query(sec[j].l, sec[j].r, , n, );
j++;
}
}
; i<=m; i++){
printf("%I64d\n", ans[i]);
}
;
}
HDU：
#include<bits/stdc++.h>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
;
];
void PushUP(int rt) {
sumv[rt] = sumv[rt<<] + sumv[rt<<|];
}
void update(int p,long long sc,int l,int r,int rt) {
if (l == r) {
sumv[rt] += sc;
return ;
}
);
if (p <= m) update(p , sc , lson);
else update(p , sc , rson);
PushUP(rt);
}
long long query(int L,int R,int l,int r,int rt) {
if (L <= l && r <= R) {
return sumv[rt];
}
);
;
if (L <= m) ret += query(L , R , lson);
if (R > m) ret += query(L , R , rson);
return ret;
}
struct interval{
int L, R, id;
bool operator < (const interval & other) const{
return this->R < other.R;
}
};
interval sec[maxn<<];
bool vis[maxn];
];
int per[maxn];
long long arr[maxn];
map<long long, int> mp;
int main(void)
{
int nCase;
scanf("%d", &nCase);
while(nCase--){
int n;
mp.clear(); ;
memset(sumv, , sizeof(sumv));
scanf("%d", &n);
; i<=n; i++){
scanf("%I64d", &arr[i]);
if(!mp.count(arr[i]))
mp[arr[i]] = cnt++;
}
int m;
scanf("%d", &m);
; i<=m; i++){
scanf("%d %d", &sec[i].L, &sec[i].R);
sec[i].id = i;
}
sort(sec+, sec++m);
memset(vis, false, sizeof(vis));
, j=; j<=m && i<=n; i++){
int num = mp[arr[i]];
if(vis[num]){
update(per[num],-arr[i],,n,);
update(i, arr[i], , n, );
per[num] = i;
}else{
vis[num] = true;
update(i, arr[i], , n, );
per[num] = i;
}
while(i==sec[j].R){
ans[sec[j].id] = query(sec[j].L, sec[j].R, , n, );
j++;
}
}
; i<=m; i++){
printf("%I64d\n", ans[i]);
}
}
}
update in 2018-06-08
学了主席树、以上的离线算法都可以变成在线算法了、戳 主席树