首页 > ACM题库 > HDU-杭电 > HDU 3874-Necklace-排序-[解题报告]HOJ
2015
04-13

HDU 3874-Necklace-排序-[解题报告]HOJ

Necklace

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

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

来源:http://acm.hdu.edu.cn/showproblem.php?pid=3874

题意:有一些数,这些数中有重复的,问从[L,R]区间的和是多少,重复的数只能算一次。

思路:因为有多次询问,所以暴力的话肯定超时,又因为是区间求和问题,所以可以考虑用树状数组求。树状数组可以解决没有重复数的情况,因此这道题我们可以特殊处理一下。首先我们可以把所有的询问都存起来,然后对询问按右端点排序,然后每次询问,对于排序后的每次询问,我们只考虑到该区间的右端点,并且记录每个数最后出现的位置,若出现相同的数,则需要从该数的位置开始减去该数。

代码:

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <set>
using namespace std;
const int N = 50010;
const int M = 200010;
int dit[N];
__int64 num[N];
__int64 ans[M];
struct interval{
    int lp,rp,id;
}rr[M];
bool  cmp(interval a,interval b){
    if(a.rp == b.rp)
        return a.lp < b.lp;
    return a.rp < b.rp;
}
int inline lowbit(int x){
    return x & (-x);
}
void inline update(int x,int add){
    while(x < N){
      num[x] += add;
      x += lowbit(x);
    }
}
__int64 inline sum(int x){
    __int64 s = 0;
    while(x > 0){
      s += num[x];
      x -= lowbit(x);
    }
    return s;
}
int main(){
    int numcase;
    map<int,int> mp;
    scanf("%d",&numcase);
    while(numcase--){
       int n,m;
       scanf("%d",&n);
       memset(dit,0,sizeof(dit));
       for(int i = 1; i <= n; ++i){
          scanf("%d",&dit[i]);
       }
       scanf("%d",&m);
       for(int i = 0; i < m; ++i){
          scanf("%d%d",&rr[i].lp,&rr[i].rp);
          if(rr[i].rp < rr[i].lp)
             swap(rr[i].lp,rr[i].rp);
          rr[i].id = i;
       }
       sort(rr,rr+m,cmp);
       memset(num,0,sizeof(num));
       memset(ans,0,sizeof(ans));
       mp.clear();
       int rp = 1;
       for(int i = 0; i < m; ++i){
           while(rp <= rr[i].rp){
              int x = dit[rp];
              if(mp[x] != 0){
                 update(mp[x],-x);
              }
              update(rp,x);
              mp[x] = rp;
              rp++;
           }
           ans[rr[i].id] = sum(rr[i].rp) - sum(rr[i].lp - 1); 
       }
       for(int i = 0; i < m; ++i){
          printf("%I64d\n",ans[i]);
       }
       
    }
    //system("pause");
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wmn_wmn/article/details/8011455


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示