Necklace

Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1957    Accepted Submission(s): 702

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

3
7
14
1
3
6

题意:

算法: 树状数组求一段序列连续和 + 离线处理

思路:

            算是很基础的树桩数组题目了, 比赛的时候怎么也想不到，赛后看了下别人的题解才知道，比起学弟学妹们的 AC 了的才找题解 

     实在是弱爆了Orz

            题目的关键：如何消除序列中的重复的元素。

                                 先将所有的询问记录下来,再按照询问的连续和区间的右端点由小到大排序。

                                 可以用 map<int, int> 来记录当前元素是否出现过。前一个int 记录元素的值, 后一个 int 标记元素出现的最新下标

                                 开始初始化 map 为空

                                 从第一个元素 index = 1 开始加入树桩数组

                                 依次遍历排序后的询问:

                                            如果当前元素在前面出现过, 则删除它出现在树状数组的在前面的位置。同时把它当前的位置加入树桩数组

                                            也就是说：对于相同的元素，只使用它最后出现的位置，前面出现过的全部消除。

                                            这样就相当于转换成求一段连续区间的序列和了,因为重复出现的元素已经消除了。

                                 这个思路也是看的别人的，具体看代码实现把。

                                 很多问题的转换自己还是怎么也想不到Orz

code:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iostream>
using namespace std;

const int maxn = 50000+10;
const int maxQ = 200000+10;
int a[maxn];
__int64 c[maxn];
__int64 ans[maxQ];
map<int,int> mp;
int n,m;

struct Que{
    int left, right;
    int index;
}q[maxQ];

bool cmp(Que a, Que b)
{
    return a.right < b.right;
}

int lowbit(int x)
{
    return x&(-x);
}

void add(int index, int value)
{
    while(index <= n)
    {
        c[index] += value;
        index += lowbit(index);
    }
}

__int64 sum(int index)
{
    __int64 ret = 0;
    while(index > 0) // 下标从 1 开始
    {
        ret += c[index];
        index -= lowbit(index);
    }
    return ret; //勿忘记
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        memset(a, 0, sizeof(a));
        memset(c, 0, sizeof(c));

        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);

        scanf("%d", &m);
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d", &q[i].left, &q[i].right);
            q[i].index = i;
        }
        sort(q+1, q+1+m, cmp);

        mp.clear(); //清空标记
        int index = 1; //从 1 遍历

        for(int i = 1; i <= m; i++)
        {
            while(index <= q[i].right) // 对每一次询问,一直遍历到区间的最右端
            {
                if(mp[a[index]] != 0) //如果前面出现过当前数字, 删除它在前面位置形成的影响
                    add(mp[a[index]], -a[index]);
                mp[a[index]] = index;  //记录新的元素值为 a[index]的位置 index
                add(index, a[index]);//重新加入在当前“最后”位置形成的影响,
                index++; //遍历下一个元素
            }
            ans[q[i].index] = sum(q[i].right) - sum(q[i].left-1); //树状数组求连续序列和
        }

        for(int i = 1; i <= m; i++)
            printf("%I64d\n", ans[i]);
    }
    return 0;
}