HDU 3333 Turing Tree（离线操作+线段树||树状数组）

朴灿烈づ我的快乐病毒、 2022-06-11 01:20 188阅读 0赞

After inventing Turing Tree, 3xian always felt boring when solving problems about intervals, because Turing Tree could easily have the solution. As well, wily 3xian made lots of new problems about intervals. So, today, this sick thing happens again...  
  
Now given a sequence of N numbers A1, A2, ..., AN and a number of Queries(i, j) (1≤i≤j≤N). For each Query(i, j), you are to caculate the sum of distinct values in the subsequence Ai, Ai+1, ..., Aj.

Input

The first line is an integer T (1 ≤ T ≤ 10), indecating the number of testcases below.  
For each case, the input format will be like this:  
\* Line 1: N (1 ≤ N ≤ 30,000).  
\* Line 2: N integers A1, A2, ..., AN (0 ≤ Ai ≤ 1,000,000,000).  
\* Line 3: Q (1 ≤ Q ≤ 100,000), the number of Queries.  
\* Next Q lines: each line contains 2 integers i, j representing a Query (1 ≤ i ≤ j ≤ N).

Output

For each Query, print the sum of distinct values of the specified subsequence in one line.

Sample Input

2
    3
    1 1 4
    2
    1 2
    2 3
    5
    1 1 2 1 3
    3
    1 5
    2 4
    3 5

Sample Output

1
    5
    6
    3
    6

题解：

这一题和之前做过的一题几乎一模一样，就是数据范围变大了，直接开数组会炸，只要用哈希+离散化搞一下或者直接用STL里的map，我哈希不太熟就用map了，也很快，第一次修改了以前做过的necklace就ac了，以前文章：[Nacklace][]，然后我用线段树做了一遍也ac了，果然树状数组会比线段树快个100ms左右，而且内存消耗也更小

思路：

和Nacklace思路一样，所谓离线操作，就是在处理各种询问前将数据和询问都按照一定规则处理一遍再得出答案，这一题就是这样，先将询问结果保存，按照右区间从小到大排序，如果相同按左区间从小到大排序，然后再处理，设j为当前更新区段，每处理一个询问，看右端点处于当前更新指针j的大小，如果比j大，那么要继续插入数据来更新区段，直到右端点处小于指针j，就可以开始询问了，这就避免了一些冲突

先树状数组代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    int a[30005];//存数值
    map<int,int>M;//存每个数出现的最后位置
    long long sum[30005];//树状数组
    struct node
    {
        int l,r;
        int id;
    };
    int cmp(node x,node y)//对询问区间右端点从小到大排序，如果相同对左端点从小到大排
    {
        if(x.r!=y.r)
            return x.r<y.r;
        else
            return x.l<y.l;
    }
    node ask[100005];//存询问区间
    long long ans[100005];//存id对应的答案
    int n,m;
    long long lowbit(long long x)//树状数组神器
    {
        return x&(-x);
    }
    long long query(long long x)//long long防爆
    {
        long long s=0;
        while(x>0)//向下连通的子区间询问和
        {
            s+=sum[x];
            x-=lowbit(x);
        }
        return s;
    }
    void insert(long long pos,long long v)//向上父区间累加和
    {
        while(pos<=n)
        {
            sum[pos]+=v;
            pos+=lowbit(pos);
        }
    }
    long long Getsum(long long x,long long y)//两以开头为左端点的线段和相减得出该线段和
    {
        return query(y)-query(x-1);
    }
    int main()
    {
        int i,j,test;
        scanf("%d",&test);
        while(test--)
        {
            M.clear();
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                sum[i]=0;
            }
            sum[0]=0;
            scanf("%d",&m);
            for(i=0;i<m;i++)
            {
                scanf("%d%d",&ask[i].l,&ask[i].r);
                ask[i].id=i;
            }
            sort(ask,ask+m,cmp);//排序
            j=1;//为当前插入位置，即更新好的区段
            for(i=0;i<m;)//离线操作
            {
                if(ask[i].r>=j)//访问区间还没更新好，要插入后才可以访问
                {
                    if(M.count(a[j])==0)//前面没出现过
                    {
                        M[a[j]]=j;//记录下插入位置
                        insert(j,a[j]);
                    }
                    else
                    {
                        insert(M[a[j]],-a[j]);//删去之前的位置
                        M[a[j]]=j;//记录当前位置
                        insert(j,a[j]);//插入当前位置
                    }
                    j++;
                }
                else//访问区间更新好了，访问
                {
                    ans[ask[i].id]=Getsum(ask[i].l,ask[i].r);
                    i++;
                }
            }
            for(i=0;i<m;i++)
                printf("%lld\n",ans[i]);
        }
        return 0;
    }

然后是线段树代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    map<int,int>M;
    struct node
    {
        int l,r;
        long long v;
    }t[30005*4];
    struct que
    {
        int l,r;
        int id;
    }ask[100005];//储存询问
    int a[30005],n;
    long long ans[100005];//储存询问结果
    int cmp(que x,que y)//按上述所说排序
    {
        if(x.r!=y.r)
            return x.r<y.r;
        return x.l<y.l;
    }
    void Build(int l,int r,int k)//日常建树
    {
        t[k].l=l;
        t[k].r=r;
        t[k].v=0;
        if(l==r)
            return;
        int mid=(l+r)/2;
        Build(l,mid,k*2);
        Build(mid+1,r,k*2+1);
    }
    long long query(int l,int r,int k)//日常询问
    {
        if(t[k].l==l&&t[k].r==r)
            return t[k].v;
        int mid=(t[k].l+t[k].r)/2;
        if(r<=mid)
            return query(l,r,k*2);
        else if(l>mid)
            return query(l,r,k*2+1);
        else
            return query(l,mid,k*2)+query(mid+1,r,k*2+1);
    }
    void insert(int pos,int v,int k)//日常插入
    {
        if(t[k].l==pos&&t[k].r==pos)
        {
            t[k].v+=v;//注意是+=，一开始写成=没发现错
            return;
        }
        int mid=(t[k].l+t[k].r)/2;
        if(pos<=mid)
            insert(pos,v,k*2);
        else
            insert(pos,v,k*2+1);
        t[k].v=t[k*2].v+t[k*2+1].v;
    }
    int main()
    {
        int i,j,test,m;
        scanf("%d",&test);
        while(test--)
        {
            M.clear();
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);//存起来慢点插入
            }
            Build(1,n,1);
            scanf("%d",&m);
            for(i=0;i<m;i++)
            {
                scanf("%d%d",&ask[i].l,&ask[i].r);
                ask[i].id=i;//记录问题id
            }
            sort(ask,ask+m,cmp);
            j=1;//当前更新区段位置
            for(i=0;i<m;)
            {
                if(ask[i].r>=j)//还没更新完，要先插入更新
                {
                    if(M.count(a[j])==0)//如果没出现过
                    {
                        M[a[j]]=j;//记录位置
                        insert(j,a[j],1);
                    }
                    else
                    {
                        insert(M[a[j]],-a[j],1);//出现过，消去原来位置的值
                        M[a[j]]=j;//记录当前位置
                        insert(j,a[j],1);//插入当前位置
                    }
                    j++;
                }
                else
                {
                    ans[ask[i].id]=query(ask[i].l,ask[i].r,1);
                    i++;
                }
            }
            for(i=0;i<m;i++)
                printf("%lld\n",ans[i]);
        }
        return 0;
    }

[Nacklace]: http://blog.csdn.net/qq_37497322/article/details/75039971