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> 來記錄當前元素是否出現過。前一個int 記錄元素的值, 後一個 int 標記元素出現的最新下標
開始初始化 map 為空
從第一個元素 index = 1 開始加入樹樁數組
依次遍歷排序後的詢問:
如果當前元素在前面出現過, 則刪除它出現在樹狀數組的在前面的位置。同時把它當前的位置加入樹樁數組
也就是說：對於相同的元素，只使用它最後出現的位置，前面出現過的全部消除。
這樣就相當於轉換成求一段連續區間的序列和了,因為重復出現的元素已經消除了。
這個思路也是看的別人的，具體看代碼實現把。
很多問題的轉換自己還是怎麼也想不到Orz
#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;
}
