hdu 3874 Necklace[树状数组简单应用] - c++编程基础

TOP

hdu 3874 Necklace[树状数组简单应用]

2014-11-23 19:30:21 来源: 作者: 【大中小】浏览:6次

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

Problem Description
Mery has a beautiful necklace. The necklace is made up of N magic balls. Each ball has a beautiful value. The balls with the same beautiful value look the same, so if two or more balls have the same beautiful value, we just count it once. We define the beautiful value of some interval [x,y] as F(x,y). F(x,y) is calculated as the sum of the beautiful value from the xth ball to the yth ball and the same value is ONLY COUNTED ONCE. For example, if the necklace is 1 1 1 2 3 1, we have F(1,3)=1, F(2,4)=3, F(2,6)=6.

Now Mery thinks the necklace is too long. She plans to take some continuous part of the necklace to build a new one. She wants to know each of the beautiful value of M continuous parts of the necklace. She will give you M intervals [L,R] (1<=L<=R<=N) and you must tell her F(L,R) of them.

Input
The first line is T(T<=10), representing the number of test cases.
For each case, the first line is a number N,1 <=N <=50000, indicating the number of the magic balls. The second line contains N non-negative integer numbers not greater 1000000, representing the beautiful value of the N balls. The third line has a number M, 1 <=M <=200000, meaning the nunber of the queries. Each of the next M lines contains L and R, the query.

Output
For each query, output a line contains an integer number, representing the result of the query.

Sample Input
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

Sample Output
3
7
14
1
3
6

Source
2011 Multi-University Training Contest 4 - Host by SDU

Recommend
lcy

题意:

给你一段长度为 N 的序列,
然后是 M 个询问,要求计算每段区间的连续和
注意:重复的元素只能在连续和中出现一次

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

思路:

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

实在是弱爆了Orz

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

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

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

开始初始化 map 为空

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

依次遍历排序后的询问:

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

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

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

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

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

#include
#include
#include
#include
#include
using namespace std;

const int maxn = 50000+10;
const int maxQ = 200000+10;
int a[maxn];
__int64 c[maxn];
__int64 ans[maxQ];
map 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;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：UVA 11168 - Airport	下一篇：Strange Addition

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: