当前位置：网站首页>1004 (tree array + offline operation + discretization)

1004 (tree array + offline operation + discretization)

2022-08-10 14:23: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

Topics and ideas：

Find the sum of disjoint numbers.Use offline operation.

The first is to discretize.Also save the range,按照右端点排序.进行预处理.

Then loop from the first number,Put the numbers into a tree-like array,if it exists in the array,就再减去.Each to a right endpoint,Put and saveans里.最后输出.

代码：

       
       #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://yzsam.com/2022/222/202208101406430217.html

当前位置：网站首页>1004 (tree array + offline operation + discretization)

1004 (tree array + offline operation + discretization)

边栏推荐

猜你喜欢

随机推荐