首页 > 代码库 > HDU Turing Tree --树状数组+离线处理

HDU Turing Tree --树状数组+离线处理

题意:统计一段序列【L,R】的和,重复元素只算一次。

解法:容易看出在线做很难处理重复的情况,干脆全部讲查询读进来,然后将查询根据右端点排个序,然后离散化数据以后就可以操作了。

每次读入一个数,如果这个数之前出现过,那么删除之前出现的那个数,改加上这个数,然后进行所有右端点小于等于此时下标的查询即可。

关于正确性,引用sdj222555的话来说,"观察一个区间,我们可以发现,如果出现重复的,尽量删除左边的,保留右边的,那么右端点相同的区间都可以进行查询。"

代码:

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <map>#define lll __int64using namespace std;#define N 30007lll c[N],ans[3*N+10004];map<int,int> mp;int a[N],pos[N],n,b[N],d[N];struct Query{    int L,R,ind;}Q[3*N+10004];int cmp(Query ka,Query kb){    return ka.R < kb.R;}inline int lowbit(int x) { return x&(-x); }void modify(int pos,lll val){    while(pos <= n)    {        c[pos] += val;        pos += lowbit(pos);    }}lll getsum(int pos){    lll ans = 0;    while(pos > 0)    {        ans += c[pos];        pos -= lowbit(pos);    }    return ans;}int main(){    int t,i,j,q;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        for(i=1;i<=n;i++)            scanf("%d",&a[i]),b[i] = a[i];        scanf("%d",&q);        for(i=1;i<=q;i++)            scanf("%d%d",&Q[i].L,&Q[i].R),Q[i].ind = i;        memset(c,0,sizeof(c));        sort(b+1,b+n+1);        sort(Q+1,Q+q+1,cmp);        int ind = unique(b+1,b+n+1)-b-1;        for(i=1;i<=ind;i++)            mp[b[i]] = i;        for(i=1;i<=n;i++)   //d[i]为a[i]离散化后的数            d[i] = mp[a[i]];        memset(pos,0,sizeof(pos));  //pos 存上次出现的位置        j = 1;        for(i=1;i<=n;i++)        {            if(pos[d[i]]) modify(pos[d[i]],-a[i]);            modify(i,a[i]);            pos[d[i]] = i;            while(j <= q && Q[j].R == i)            {                ans[Q[j].ind] = getsum(Q[j].R)-getsum(Q[j].L-1);                j++;            }            if(j > q)                break;        }        for(i=1;i<=q;i++)            printf("%I64d\n",ans[i]);    }    return 0;}
View Code

 

HDU Turing Tree --树状数组+离线处理