浙江财经大学
信息管理与工程学院

HDU 3333 Turing Tree(线段树)

本文由 Ocrosoft 于 2016-11-14 10:19:48 发表

Turing Tree

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
 

Solution
题意:求询问区间中不同的数字的和,也就是同一个数字只计算一次。
思路(GodWang):按照询问区间右侧升序排序;新建一空树,将数字按次序放入,如果这个数字已存在,就删除后再添加。 
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define  rep(a,v,b) for(int a=v;a<b;a++)
#define  repe(a,v,b) for(int a=v;a<=b;a++)
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 300000+ 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
    if (!b)return a;
    return gcd(b, a%b);
} 
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧 (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
int x[MAXN * 4], y[MAXN * 4]; LL a[MAXN]; LL sum[MAXN * 4];
struct Node
{
    int a, b, c;
    bool operator<(const Node t)
    {
        return b < t.b;
    }
}b[MAXN];
map<LL, int> mp; LL ans[MAXN];
void build(int pos, int l, int r)
{
    x[pos] = l; y[pos] = r; sum[pos] = 0;//建空树
    if (x[pos] == y[pos])return;
    else
    {
        int mid = l + r >> 1;
        build(pos * 2, l, mid);
        build(pos * 2 + 1, mid + 1, r);
        //sum[pos] = (sum[pos * 2] * sum[pos * 2 + 1]) % MOD;
    }
}
void update(int pos, int p, LL v)
{
    if (x[pos] == p&&y[pos] == p)sum[pos] +=v;
    else
    {
        int mid = x[pos] + y[pos] >> 1;
        if (p <= mid)update(pos * 2, p, v);
        else update(pos * 2 + 1, p, v);
        sum[pos] = (sum[pos * 2] +sum[pos * 2 + 1]);
    }
}
LL query(int pos, int l, int r)
{
    if (x[pos] == l&&y[pos] == r)return sum[pos];
    else
    {
        int mid = x[pos] + y[pos] >> 1;
        LL ans = 0;
        if (l <= mid)ans+= query(pos * 2, l, min(mid,r));
        if (r > mid)ans+= query(pos * 2 + 1, max(mid+1,l), r);
        return ans;
    }
}
int main()
{
    int T; cin >> T;
    while (T--)
    {
        mp.clear();
        int n; cin >> n;
        repe(i, 1, n)scanf("%I64d", &a[i]);
        build(1, 1, n);
        int m; cin >> m;
        rep(i, 0, m)
        {
            scanf("%d%d", &b[i].a, &b[i].b);
            b[i].c = i;
        }
        sort(b, b + m);
        int k = 1;
        rep(i, 0, m)
        {
            for (; k <= b[i].b;k++)
            {
                if (mp[a[k]])update(1, mp[a[k]], -a[k]);//如果线段树中存在该数(点),则删除
                mp[a[k]] = k;
                update(1, k, a[k]);//往线段树添加这个数
            }
            ans[b[i].c] = query(1, b[i].a, b[i].b);
        }
        rep(i, 0, m)printf("%I64d\n", ans[i]);
    }
    return 0;
}

欢迎分享与转载,请保留链接与出处。Ocrosoft » HDU 3333 Turing Tree(线段树)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址