SPOJ D-query && HDU 3333 Turing Tree (线段树 && 区间不相同数个数or和 && 离线处理)

2017年08月21日 9点热度 0人点赞 0条评论

题意 : 给出一段n个数的序列,接下来给出m个询问,询问的内容SPOJ是(L,
R)这个区间内不同的数的个数,HDU是不同数的和

 

分析 :一个经典的问题,思路是将所有问询区间存起来,然后按右端点排序,最后从左到右将原区间扫一遍,扫的过程当中不断将重复出现的数字右移,也就是如果一个数字重复出现,那么我们记录最右边的那个为有效的,其他都视为不存在,这样一旦遇到一个问询区间的右端点就线段树查询即可。

 

//求区间不同的数的和 
#include
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 300005;
long long sumv[maxn<<2];
void PushUP(int rt) {
    sumv[rt] = sumv[rt<<1] + sumv[rt<<1|1];
}
void update(int p,int sc,int l,int r,int rt) {
    if (l == r) {
        sumv[rt] += sc;
        return ;
    }
    int m = l + ((r - l)>>1);
    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];
    }
    int m = l + ((r - l)>>1);
    long long ret = 0;
    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[200005];
map mp;
int arr[maxn];
int pre[maxn];
long long ans[maxn];
int main(void) {
    int n, cnt = 0, m,T;
    scanf("%d",&T);
    while(T--) {
        //init
        cnt=0;
        mp.clear();
        memset(sumv, 0, sizeof(sumv));
        scanf("%d", &n);
        for(int i=1; i<=n; i++) {
            scanf("%d", &arr[i]);
            if(!mp.count(arr[i]))
                mp[arr[i]] = cnt++;//区间上的每一个数都有一个独特的编号,使用map来进行映射,目的是方便判断此数是否已经重复出现过
        }
        scanf("%d", &m);
        for(int i=1; i<=m; i++) {
            scanf("%d %d", &sec[i].l, &sec[i].r);
            sec[i].id = i;//因为后续有排序操作,而我们又要对问询答案顺序给出,所以记录给出的顺序,方便输出答案
        }
        sort(sec+1, sec+1+m);//按照右端点排序
        bool vis[maxn];
        memset(vis, false, sizeof(vis));
        for(int i=1, j=1; j<=m && i<=n; i++) {
            int tmp = mp[arr[i]];//拿出这个数的编号
            if(vis[tmp]) { //如果这个数在前面已经访问过
                update(pre[tmp], -arr[i], 1, n, 1);//将之前的位置信息抹去
                update(i, arr[i], 1, n, 1);//当前的位置才是有效的,所以给当前位置+1
                pre[tmp] = i;//更新pre数组方便下次操作
            } else {
                vis[tmp] = true;
                update(i, arr[i], 1, n, 1);//如果是求个数,则把arr[i]改成1,上面的两个位置也要改 
                pre[tmp] = i;
            }
            while(sec[j].r == i) {
                ans[sec[j].id] = query(sec[j].l, sec[j].r, 1, n, 1);
                j++;
            }
        }
        for(int i=1; i<=m; i++) {
            printf("%I64dn", ans[i]);
        }
    }
    return 0;
}

未经允许不得转载!SPOJ D-query && HDU 3333 Turing Tree (线段树 && 区间不相同数个数or和 && 离线处理)

update

纸上得来终觉浅, 绝知此事须躬行。