hdu 3333(樹状配列+離散化+hash)
10467 ワード
Turing Tree
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3847 Accepted Submission(s): 1306
Problem Description
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
Author
3xian@GDUT
Source
HDOJ Monthly Contest – 2010.03.06
Recommend
lcy | We have carefully selected several similar problems for you:
1542
3397
1394
1540
1255
タイトルの説明:1つのシーケンスの中であるネタの区間の相異数の和を求めます.
异なる数の和を求めるならば、同じ数を消せばよいのですが、クエリの区间が不确定なので、被削除数を调べる前に被削除数を含む区间の和を仮定すると、困ります.
まずすべてのクエリーを読み込み、ツリー配列を作成する過程でiで終わる数までのすべてのクエリーに一度に答えることができ、重複があれば削除します.
iより小さいので、最後にすべてのクエリーが保存されます.結果を順番に出力するため、各クエリーの操作番号をあげます.また、小さいから大きいまでiで終わるためです.
のすべてのクエリーを使用するので、メンバー変数はそれぞれL,R,IDです.Rで構造体を並べ替え、結果をmapsに格納する.
s[ID]では、2次元配列を用いる空間を浪費し、mapを用いてマッピングを行う.
最後に注意したいのはc配列の大きさがnの最大値なら×4;
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3847 Accepted Submission(s): 1306
Problem Description
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
Author
3xian@GDUT
Source
HDOJ Monthly Contest – 2010.03.06
Recommend
lcy | We have carefully selected several similar problems for you:
1542
3397
1394
1540
1255
タイトルの説明:1つのシーケンスの中であるネタの区間の相異数の和を求めます.
异なる数の和を求めるならば、同じ数を消せばよいのですが、クエリの区间が不确定なので、被削除数を调べる前に被削除数を含む区间の和を仮定すると、困ります.
まずすべてのクエリーを読み込み、ツリー配列を作成する過程でiで終わる数までのすべてのクエリーに一度に答えることができ、重複があれば削除します.
iより小さいので、最後にすべてのクエリーが保存されます.結果を順番に出力するため、各クエリーの操作番号をあげます.また、小さいから大きいまでiで終わるためです.
のすべてのクエリーを使用するので、メンバー変数はそれぞれL,R,IDです.Rで構造体を並べ替え、結果をmap
s[ID]では、2次元配列を用いる空間を浪費し、mapを用いてマッピングを行う.
最後に注意したいのはc配列の大きさがnの最大値なら×4;
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
#define maxn 55555*4
#define LL long long
#define inf 0x3f3f3f3f3f3f3f3f3f3f
#define lowbit(x) x & (-x)
using namespace std;
//int visit[maxn];
//int VISIT[maxn];
map <LL,LL > visit;
map <LL ,LL > VISIT;
LL A[maxn];
int n,cnt;
struct node
{
int L,R,id;
};
node Q[maxn];
LL c[maxn];
LL ans[maxn];
void init()
{
memset(c,0,sizeof(c));
//memset(visit,0,sizeof(visit));
//memset(VISIT,0,sizeof(VISIT));
visit.clear();
VISIT.clear();
cnt=0;
}
LL sum(int x)
{
LL ret=0;
while(x>0)
{
ret+=c[x];
x-=(x&(-x) );
}
return ret;
}
void add(int x,LL d)
{
while(x<=n)
{
c[x]+=d;
x+=(x& (-x) );
}
}
void solve()
{
for(int i=1;i<=n;i++)
{
if(visit[A[i]]!=0)
{
add(visit[A[i]],-A[i]);
}
visit[A[i]]=i;
add(i,A[i]);
if(VISIT[i]!=0)
{
for(int j=1;j<=VISIT[i];j++)
{
cnt++;
ans[Q[cnt].id]=sum(Q[cnt].R)-sum(Q[cnt].L-1);
//printf("%lld
",ans[Q[cnt].id]);
}
}
}
}
bool cmp(node a,node b)
{
if(a.R==b.R)
return a.L<b.L;
else
return a.R<b.R;
}
int main()
{
//freopen("test.txt","r",stdin);
int t,q;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&A[i]);
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&Q[i].L,&Q[i].R);
Q[i].id=i;
// printf("%d
",Q[i].id);
++VISIT[Q[i].R];
}
sort(Q+1,Q+q+1,cmp);
/* for(int i=1;i<=q;i++)
{
printf("%d
",Q[i].id);
}*/
solve();
for(int i=1;i<=q;i++)
{
printf("%lld
",ans[i]);
}
}
return 0;
}