当前位置：网站首页>1004（树状数组+离线操作+离散化）

1004（树状数组+离线操作+离散化）

2022-08-10 14:09:00 【51CTO】

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

Sample Output

题目大概和思路：

求不重合数的和。用离线操作。

首先要进行离散化。还要把区间存起来，按照右端点排序。进行预处理。

然后从第一个数开始循环，把数放到树状数组里，如果数组中存在了，就再减去。每到一个右端点，就把和存到ans里。最后输出。

代码：

       
       #include <iostream>
       
       #include <cstdio>
       
       #include <algorithm>
       
       #include <cstring>
       
       #include <vector>
       
       using 
       
       namespace 
       
       std;
       
       int 
       
       n;
       
       int 
       
       b[
       
       30010],
       
       b1[
       
       30010];
       
       long 
       
       long 
       
       c[
       
       30010];
       
       long 
       
       long 
       
       ans[
       
       100010];
       
       int 
       
       vis[
       
       30005];
       
       struct 
       
       poin
       
{
       
       int 
       
       l,
       
       r,
       
       id;
       
}
       
       a[
       
       100010];
       
       bool 
       
       cmp(
       
       const 
       
       poin 
       
       a,
       
       const 
       
       poin 
       
       b)
       
{
       
       return 
       
       a.
       
       r
       
       <
       
       b.
       
       r;
       
}
       
       struct 
       
       poin1
       
{
       
       int 
       
       v,
       
       id;
       
}
       
       a1[
       
       30005];
       
       int 
       
       cmp1(
       
       const 
       
       poin1 
       
       a,
       
       const 
       
       poin1 
       
       b)
       
{
       
       if(
       
       a.
       
       v
       
       <
       
       b.
       
       v)
       
       return 
       
       1;
       
       else 
       
       return 
       
       0;
       
}
       
       int 
       
       lowbit(
       
       int 
       
       x)
       
{
       
       return 
       
       x
       
       &(
       
       -
       
       x);
       
}
       
       int 
       
       add(
       
       int 
       
       x,
       
       int 
       
       v)
       
{
       
       while(
       
       x
       
       <=
       
       30001)
       
    {
       
       c[
       
       x]
       
       +=
       
       v;
       
       x
       
       =
       
       x
       
       +
       
       lowbit(
       
       x);
       
    }
       
}
       
       long 
       
       long 
       
       sum(
       
       int 
       
       x)
       
{
       
       long 
       
       long 
       
       su
       
       =
       
       0;
       
       while(
       
       x
       
       >
       
       0)
       
    {
       
       su
       
       +=
       
       c[
       
       x];
       
       x
       
       -=
       
       lowbit(
       
       x);
       
    }
       
       return 
       
       su;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       t;
       
       scanf(
       
       "%d",
       
       &
       
       t);
       
       while(
       
       t
       
       --)
       
   {    
       
       memset(
       
       c,
       
       0,
       
       sizeof(
       
       c));
       
       memset(
       
       ans,
       
       0,
       
       sizeof(
       
       ans));
       
       memset(
       
       vis,
       
       0,
       
       sizeof(
       
       vis));
       
       scanf(
       
       "%d",
       
       &
       
       n);
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++)
       
        {
       
       scanf(
       
       "%d",
       
       &
       
       b[
       
       i]);
       
       a1[
       
       i].
       
       v
       
       =
       
       b[
       
       i];
       
       a1[
       
       i].
       
       id
       
       =
       
       i;
       
        }
       
       sort(
       
       a1
       
       +
       
       1,
       
       a1
       
       +
       
       n
       
       +
       
       1,
       
       cmp1);
       
       b1[
       
       a1[
       
       1].
       
       id]
       
       =
       
       1;
       
       int 
       
       o
       
       =
       
       2;
       
       for(
       
       int 
       
       i
       
       =
       
       2;
       
       i
       
       <=
       
       n;
       
       i
       
       ++)
       
       {
       
       if(
       
       a1[
       
       i].
       
       v
       
       ==
       
       a1[
       
       i
       
       -
       
       1].
       
       v)
       
       b1[
       
       a1[
       
       i].
       
       id]
       
       =
       
       b1[
       
       a1[
       
       i
       
       -
       
       1].
       
       id];
       
       else 
       
       b1[
       
       a1[
       
       i].
       
       id]
       
       =
       
       o
       
       ++;
       
       }
       
       int 
       
       m
       
       =
       
       0;
       
       scanf(
       
       "%d",
       
       &
       
       m);
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       m;
       
       i
       
       ++)
       
        {
       
       int 
       
       q,
       
       w;
       
       scanf(
       
       "%d%d",
       
       &
       
       q,
       
       &
       
       w);
       
       a[
       
       i].
       
       l
       
       =
       
       q;
       
       a[
       
       i].
       
       r
       
       =
       
       w;
       
       a[
       
       i].
       
       id
       
       =
       
       i;
       
        }
       
       sort(
       
       a
       
       +
       
       1,
       
       a
       
       +
       
       m
       
       +
       
       1,
       
       cmp);
       
       int 
       
       j
       
       =
       
       1;
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       m;
       
       i
       
       ++)
       
        {
       
       for(;
       
       j
       
       <=
       
       a[
       
       i].
       
       r;
       
       j
       
       ++)
       
            {
       
       if(
       
       vis[
       
       b1[
       
       j]])
       
       add(
       
       vis[
       
       b1[
       
       j]],
       
       -
       
       b[
       
       j]);
       
       vis[
       
       b1[
       
       j]]
       
       =
       
       j;
       
       add(
       
       j,
       
       b[
       
       j]);
       
            }
       
       ans[
       
       a[
       
       i].
       
       id]
       
       =
       
       sum(
       
       a[
       
       i].
       
       r)
       
       -
       
       sum(
       
       a[
       
       i].
       
       l
       
       -
       
       1);
       
        }
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       m;
       
       i
       
       ++)
       
        {
       
       printf(
       
       "%I64d\n",
       
       ans[
       
       i]);
       
        }
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15747246/5563473

当前位置：网站首页>1004（树状数组+离线操作+离散化）

1004（树状数组+离线操作+离散化）

边栏推荐

猜你喜欢

随机推荐