活用各种数据结构

线段树

基于线段树的RMQ(Range Minimum Query)的实现

实现功能：
　　在给定数列a0，a1，…，an-1的情况下，O(logn)时间内完成如下两种操作

　　①给定s和t，求as，as+1，…，at的最小值
　　②给定i和x，把ai的值改成x

实现：

  1 #include <cstdio>
  2 #include <cctype>
  3 #define number s-'0'
  4 
  5 using namespace std;
  6 
  7 const int MAX_N=1<<17;
  8 const int INT_MAX=0x3f3f3f3f;
  9 int  n,m,dat[2*MAX_N-1];//存储线段树的全局数组 
 10 
 11 void read(int &x){
 12     char s;
 13     x=0;
 14     bool flag=0;
 15     while(!isdigit(s=getchar()))
 16         (s=='-')&&(flag=true);
 17     for(x=number;isdigit(s=getchar());x=x*10+number);
 18     (flag)&&(x=-x);
 19 }
 20 
 21 void write(int x)
 22 {
 23     if(x<0)
 24     {
 25         putchar('-');
 26         x=-x;
 27     }
 28     if(x>9)
 29         write(x/10);
 30     putchar(x%10+'0');
 31 }
 32 
 33 void init(int n_);//初始化 
 34 void update(int k, int a);//把dat[k]更新为a 
 35 int query(int a, int b, int k, int l, int r);//求[a,b)的最小值 
 36 
 37 int min(int x, int y)
 38 {
 39     if (x<y) return x;
 40     return y;
 41 }
 42 
 43 int main()
 44 {
 45     read(n);read(m);
 46     int n0=n;
 47     init(n);
 48     for (int i=0; i<n0; i++)
 49     {
 50         int x;
 51         read(x);
 52         update(i,x);
 53     }
 54     for (int i=0; i<m; i++)
 55     {
 56         int x;
 57         read(x);
 58         switch (x)
 59         {
 60             case 1:
 61             int s,t,res;
 62             read(s);read(t);
 63             res=query(s,t,0,0,n);
 64             write(res);putchar('
');
 65             break;
 66             case 2:
 67             int i,x;
 68             read(i);read(x);
 69             update(i,x);
 70             break;
 71         }
 72     }
 73 }
 74 
 75 void init(int n_)
 76 {
 77     //为了简单起见，把元素个数扩大到2的幂 
 78     n=1;
 79     while (n<n_) n*=2;
 80     //把所有的值都设为INT_MAX 
 81     for (int i=0; i<2*n-1; i++) dat[i]=INT_MAX;
 82 }
 83 
 84 void update(int k, int a)
 85 {
 86     //叶子节点 
 87     k+=n-1;
 88     dat[k]=a;
 89     //向上更新 
 90     while (k>0)
 91     {
 92         k=(k-1)/2;
 93         dat[k]=min(dat[2*k+1],dat[2*k+2]);
 94     }
 95 }
 96 
 97 int query(int a, int b, int k, int l, int r)
 98 {
 99     //如果[a,b)和[l,r)不相交，则返回INT_MAX 
100     if (r<=a || b<=l) return INT_MAX;
101     //如果[a,b)完全包含[l,r)，则返回当前节点的值 
102     if (a<=l && b>=r) return dat[k];
103     //否则返回两个儿子中值较小者 
104     else 
105     {
106         int v1=query(a, b, k*2+1, l, (l+r)/2);
107         int v2=query(a, b, k*2+2, (l+r)/2, r);
108         return min(v1, v2);
109     }
110 }

 Crane(POJ 2991)

  • 原题如下：
    Crane
    Time Limit: 2000MS Memory Limit: 65536K
    Total Submissions: 8472 Accepted: 2290 Special Judge

    Description

    ACM has bought a new crane (crane -- jeřáb) . The crane consists of n segments of various lengths, connected by flexible joints. The end of the i-th segment is joined to the beginning of the i + 1-th one, for 1 ≤ i < n. The beginning of the first segment is fixed at point with coordinates (0, 0) and its end at point with coordinates (0, w), where w is the length of the first segment. All of the segments lie always in one plane, and the joints allow arbitrary rotation in that plane. After series of unpleasant accidents, it was decided that software that controls the crane must contain a piece of code that constantly checks the position of the end of crane, and stops the crane if a collision should happen. 

    Your task is to write a part of this software that determines the position of the end of the n-th segment after each command. The state of the crane is determined by the angles between consecutive segments. Initially, all of the angles are straight, i.e., 180o. The operator issues commands that change the angle in exactly one joint. 

    Input

    The input consists of several instances, separated by single empty lines. 

    The first line of each instance consists of two integers 1 ≤ n ≤10 000 and c 0 separated by a single space -- the number of segments of the crane and the number of commands. The second line consists of n integers l1,..., ln (1 li 100) separated by single spaces. The length of the i-th segment of the crane is li. The following c lines specify the commands of the operator. Each line describing the command consists of two integers s and a (1 ≤ s < n, 0 ≤ a ≤ 359) separated by a single space -- the order to change the angle between the s-th and the s + 1-th segment to a degrees (the angle is measured counterclockwise from the s-th to the s + 1-th segment).

    Output

    The output for each instance consists of c lines. The i-th of the lines consists of two rational numbers x and y separated by a single space -- the coordinates of the end of the n-th segment after the i-th command, rounded to two digits after the decimal point. 

    The outputs for each two consecutive instances must be separated by a single empty line.

    Sample Input

    2 1
10 5
1 90

3 2
5 5 5
1 270
2 90

    Sample Output

    5.00 10.00

-10.00 5.00
-5.00 10.00
  • 分析:
    本题可以使用线段树来解决，每个节点表示一段连续的线段的集合，并且维护下面两个值：①把对应的线段集合的第一条线段转至垂直方向之后，从第一条线段的起点指向最后一条线段的终点的向量，②如果该节点有儿子节点，两个儿子节点对应的部分连接之后，右儿子需要转动的角度。如果节点i表示的向量是vxi，vyi，角度是angi，两个儿子节点是chl和chr，那么就有，vxi=vxchl+(cos(angi)*vxchr-sin(angi)*vychr)，vyi=vychl+(sin(angi)*vxchr+cos(angi)*vychr)。这样，每次更新就可以在O(logn)时间内完成，而输出的值就是根节点对应的向量的值。
  • 代码： 
     1 #include <cstdio>
 2 #include <cctype>
 3 #include <cmath>
 4 #define number s-'0'
 5 
 6 using namespace std;
 7 
 8 const double M_PI=acos(-1.0);
 9 const int ST_SIZE=(1<<15)-1;
10 const int MAX_N=20000;
11 const int MAX_C=20000; 
12 int N,C;
13 int L[MAX_N];
14 int S[MAX_C],A[MAX_C];
15 double vx[ST_SIZE],vy[ST_SIZE];
16 double ang[ST_SIZE];
17 double prv[MAX_N]; 
18 
19 void read(int &x){
20     char s;
21     x=0;
22     bool flag=0;
23     while(!isdigit(s=getchar()))
24         (s=='-')&&(flag=true);
25     for(x=number;isdigit(s=getchar());x=x*10+number);
26     (flag)&&(x=-x);
27 }
28 
29 void write(int x)
30 {
31     if(x<0)
32     {
33         putchar('-');
34         x=-x;
35     }
36     if(x>9)
37         write(x/10);
38     putchar(x%10+'0');
39 }
40 
41 void init(int k, int l, int r);
42 void change(int s, double a, int v, int l, int r);
43 
44 int main()
45 {
46     while (scanf("%d %d", &N, &C)==2)
47     {
48         for (int i=0; i<N; i++) scanf("%d", &L[i]);
49         for (int i=0; i<C; i++)    scanf("%d %d", &S[i], &A[i]);
50         init(0, 0, N);
51         for (int i=0; i<N; i++) prv[i]=M_PI;
52         for (int i=0; i<C; i++)
53         {
54             int s=S[i];
55             double a=A[i]/360.0*2*M_PI;
56             change(s, a-prv[s], 0, 0, N);
57             prv[s]=a;
58             printf("%.2f %.2f
", vx[0], vy[0]);            
59         }
60 
61     }
62 }
63 
64 void init(int k, int l, int r)
65 {
66     vx[k]=ang[k]=0;
67     if (r-l==1) vy[k]=L[l];
68     else
69     {
70         int chl=2*k+1, chr=2*k+2, m=(l+r)/2;
71         init(chl, l, m);
72         init(chr, m, r);
73         vy[k]=vy[chl]+vy[chr];
74     }
75 }
76 
77 void change(int s, double a, int v, int l, int r)
78 {
79     if (s<=l) return;
80     else if (s<r)
81     {
82         int chl=v*2+1, chr=v*2+2, m=(l+r)/2;
83         change(s, a, chl, l, m);
84         change(s, a, chr, m, r);
85         if (s<=m) ang[v]+=a;
86         double s=sin(ang[v]), c=cos(ang[v]);
87         vx[v]=vx[chl]+vx[chr]*c-vy[chr]*s;
88         vy[v]=vy[chl]+vx[chr]*s+vy[chr]*c;
89     }
90 }
    Crane

基于稀疏表(Sparse Table)的RMQ(Range Minimum Query)

对于数列a1,a2,…,an构建Sparse Table，ti,j表示的是aj,aj+1,…,aj+2i的最小值

在给定x和y的情况下，通过这个表快速求出ax,ax+1,…,ay的最小值：首先求出满足2i≤y-x≤2i+1的i，也就是使得2i不超过y-x的最大的i，然后min{t_(i,x), t_(i,y-2i+1)}，就是ax,ax+1,…,ay的最小值了，而这个最大的i即为(int)(log(range) / log2)，因此它的单次查询复杂度为O(1)，效率比基于线段树的RMQ要高，但是，基于Sparse Table的RMQ在预处理时的时间复杂度和空间复杂度都达到了O(n log n)，而且和基于线段树的RMQ相比无法高效地对值进行更新。

树状数组(Binary Indexed Tree, BIT)

给一个 初始值全为0的数列a1,a2,…,an，树状数组可以：

　　①给定i，计算a1+a2+…+ai

　　②给定i和x，执行ai+=x

实现：如果使用线段树，只需要线段树每个节点上维护的是对应区间的和，在计算s到t的和时，线段树可以直接求得。但是如果我们可以计算（从1到t的和）-（从1到s-1的和），同样可以求得s到t的和，that is to say，只要对于任意的i，我们能够计算出1到i的部分就足够了，那么在这样的限制下，可以发现，线段树上每个节点的右儿子的值都不需要了，如果要用到这个值，只要用父亲节点的值减掉左边兄弟的值就可以了。基于上面思路的数据结构就是BIT。

复杂度：O(log n)

PS：i-=i&-i 也可以写作 i=i&(i-1)

 1 //[1,n]
 2 int bit[MAX_N+1], n;
 3 int sum(int i)
 4 {
 5     int s=0;
 6     while (i>0)
 7     {
 8         s+=bit[i];
 9         i-=i&-i;
10     }
11     return s;
12 }
13 void add(int i, int x)
14 {
15     while (i<=n)
16     {
17         bit[i]+=x;
18         i+=i&-i;
19     }
20 }

二维BIT：

对于W*H的二维BIT，只需要建立H个大小为x轴方向元素个数W的BIT，然后把这些BIT通过y轴方向的BIT管理起来就可以了。也就是说y轴方向的BIT的每个元素不是整数，而是一个x维方向的BIT。 这样所有操作的复杂度都是O(log W*log H)，用同样的方法可以扩展到更高维的情况。

冒泡排序的交换次数

  • 问题描述：给定一个1~n的排列a0,a1,…,an-1，求对这个数列进行冒泡排序所需要的交换次数。
  • 限制条件：1≤n≤100000
  • 分析：实际上就是求数列的逆序数，对于每一个j，要快速求出满足i<j,ai>aj的i的个数。我们构建一个值的范围是1~n的BIT，按照j=0,1,2,…,n-1的顺序，进行如下操作
    ①把j-(BIT查询得到的前aj项的和)加到答案中
    ②把BIT中aj位置上的值加1
    对于每一个j，(BIT查询得到的前aj项的和)就是满足i<j，ai≤aj的i的个数，因此把这个值从j中减去之后就是满足i<j,ai>aj的i的个数。对于每一个j的复杂度是O(log n)，所以整个算法的复杂度是O(n log n)。
  • 代码： 
     1 #include <cstdio>
 2 #include <cctype>
 3 #include <cmath>
 4 #define number s-'0'
 5 
 6 using namespace std;
 7 
 8 const int MAX_N=100000;
 9 int n,a[MAX_N],bit[MAX_N];
10 
11 int sum(int i)
12 {
13     int s=0;
14     while (i>0)
15     {
16         s+=bit[i];
17         i=i&(i-1);
18     }
19     return s;
20 }
21 
22 void add(int i, int x)
23 {
24     while (i<=n)
25     {
26         bit[i]+=x;
27         i+=i&-i;
28     }
29 }
30 
31 void read(int &x){
32     char s;
33     x=0;
34     bool flag=0;
35     while(!isdigit(s=getchar()))
36         (s=='-')&&(flag=true);
37     for(x=number;isdigit(s=getchar());x=x*10+number);
38     (flag)&&(x=-x);
39 }
40 
41 void write(long long x)
42 {
43     if(x<0)
44     {
45         putchar('-');
46         x=-x;
47     }
48     if(x>9)
49         write(x/10);
50     putchar(x%10+'0');
51 }
52 
53 void solve();
54 
55 int main()
56 {
57     read(n);
58     for (int i=0; i<n; i++) read(a[i]);
59     solve();
60 }
61 
62 void solve()
63 {
64     long long ans=0;
65     for (int j=0; j<n; j++)
66     {
67         ans+=j-sum(a[j]);
68         add(a[j], 1);
69     }
70     write(ans);putchar('
');
71 }
    逆序数

A Simple Problem with Integers(POJ 3468)

  • 原题如下：
    A Simple Problem with Integers
    Time Limit: 5000MS Memory Limit: 131072K
    Total Submissions: 141839 Accepted: 44020
    Case Time Limit: 2000MS

    Description

    You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

    Input

    The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
    The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
    Each of the next Q lines represents an operation.
    "C abc" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
    "Q ab" means querying the sum of Aa, Aa+1, ... , Ab.

    Output

    You need to answer all Q commands in order. One answer in a line.

    Sample Input

    10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

    Sample Output

    4
55
9
15

    Hint

    The sums may exceed the range of 32-bit integers.
  • 题解1：先考虑利用线段树，每个节点维护两个数据：①给这个节点对应的区间内的所有元素共同加上的值 ②在这个节点对应的区间中除去①之外其它的值的和。通过单独维护共同加上的值，给区间同时加一个值的操作就可以高效地进行了，如果对于父亲节点同时加了一个值，那么这个值就不会在儿子节点被重复考虑。在递归计算和时再把这一部分的值加到结果里面就可以了。这样不论是同时加一个值还是查询一段的和复杂度都是O(log n).
  • 代码1： 
     1 #include <cstdio>
 2 #include <cctype>
 3 #include <cmath>
 4 #define number s-'0'
 5 
 6 using namespace std;
 7 
 8 const int MAX_N=100000;
 9 const int MAX_Q=100000;
10 const int DAT_SIZE=(1<<18)-1;
11 int N,Q;
12 int A[MAX_N];
13 char T[MAX_Q];
14 int L[MAX_Q], R[MAX_Q], X[MAX_Q];
15 long long data[DAT_SIZE], datb[DAT_SIZE];
16 
17 void read(int &x){
18     char s;
19     x=0;
20     bool flag=0;
21     while(!isdigit(s=getchar()))
22         (s=='-')&&(flag=true);
23     for(x=number;isdigit(s=getchar());x=x*10+number);
24     (flag)&&(x=-x);
25 }
26 
27 void write(int x)
28 {
29     if(x<0)
30     {
31         putchar('-');
32         x=-x;
33     }
34     if(x>9)
35         write(x/10);
36     putchar(x%10+'0');
37 }
38 
39 int min(int x, int y)
40 {
41     if (x<y) return x;
42     return y;
43 }
44 
45 int max(int x, int y)
46 {
47     if (x>y) return x;
48     return y;
49 }
50 
51 void solve();
52 void add(int a, int b, int x, int k, int l, int r);
53 long long sum(int a, int b, int k, int l, int r); 
54 
55 int main()
56 {
57     read(N);read(Q);
58     for (int i=0; i<N; i++) read(A[i]);
59     for (int i=0; i<Q; i++)
60     {
61         scanf("%c", &T[i]);
62         if (T[i]=='Q') {read(L[i]);read(R[i]);}
63         else {read(L[i]);read(R[i]);read(X[i]);}
64     }
65     solve();
66 }
67 
68 void solve()
69 {
70     for (int i=0; i<N; i++) add(i, i+1, A[i], 0, 0, N);
71     for (int i=0; i<Q; i++)
72         if (T[i]=='C') add(L[i]-1, R[i], X[i], 0, 0, N);
73         else printf("%lld
", sum(L[i]-1, R[i], 0, 0, N));
74 }
75 
76 void add(int a, int b, int x, int k, int l, int r)
77 {
78     if (a<=l && r<=b) data[k]+=x;
79     else if (l<b && r>a)
80     {
81         datb[k]+=(min(b,r)-max(a,l))*x;
82         add(a, b, x, k*2+1, l, (l+r)/2);
83         add(a, b, x, k*2+2, (l+r)/2, r);
84     }
85 }
86 
87 long long sum(int a, int b, int k, int l, int r)
88 {
89     if (b<=l || a>=r) return 0;
90     else if(l>=a && r<=b) return data[k]*(r-l)+datb[k];
91     else 
92     {
93         long long res=(min(b,r)-max(a,l))*data[k];
94         res+=sum(a, b, k*2+1, l, (l+r)/2);
95         res+=sum(a, b, k*2+2, (l+r)/2, r);
96         return res;
97     }
98 }
    1
  • 题解2：树状数组也可以通过在每个节点上维护两个数据，高效地进行上述操作。如果给区间[l,r]同时加上x的话，考虑每个节点的值会如何变化。令s(i)是加上x之前的前缀和，s'(i)是加上x之后的前缀和。那么就有：
    i<l→s'(i)=s(i)
    l≤i≤r→s'(i)=s(i)+x*(i-l+1)
                    =s(i)+x*i-x*(l-1)
    r<i→s'(i)=s(i)+x*(r-l+1)
    下面记sum(bit,i)为树状数组bit的前i项和。我们构建两个树状数组bit0和bit1，并且设∑(j=1,i)aj=sum(bit1,i)*i+sum(bit0,i)
    那么在[l,r]区间上同时加上x就可以看成是
    1.在bit0的l位置加上-x(l-1)
    2.在bit1的l位置加上x
    3.在bit0的r+1位置加上xr
    4.在bit1的r+1位置加上-x
    这4个操作。因此查询和更新操作都可以在O(log n)时间里完成。
    更一般地，如果操作得到的结果可以用i的n次多项式表示，那么就可以使用n+1个树状数组来进行维护了。
  • 代码： 
     1 #include <cstdio>
 2 #include <cctype>
 3 #include <cmath>
 4 #define number s-'0'
 5 
 6 using namespace std;
 7 
 8 const int MAX_N=100000;
 9 const int MAX_Q=100000;
10 int N,Q;
11 int A[MAX_N+1]; 
12 char T[MAX_Q];
13 int L[MAX_Q], R[MAX_Q], X[MAX_Q];
14 long long bit0[MAX_N+1], bit1[MAX_N+1];
15 
16 
17 void read(int &x){
18     char s;
19     x=0;
20     bool flag=0;
21     while(!isdigit(s=getchar()))
22         (s=='-')&&(flag=true);
23     for(x=number;isdigit(s=getchar());x=x*10+number);
24     (flag)&&(x=-x);
25 }
26 
27 void write(long long x)
28 {
29     if(x<0)
30     {
31         putchar('-');
32         x=-x;
33     }
34     if(x>9)
35         write(x/10);
36     putchar(x%10+'0');
37 }
38 
39 long long sum(long long *b, int i)
40 {
41     long long s=0;
42     while (i>0)
43     {
44         s+=b[i];
45         i=i&(i-1);
46     }
47     return s;
48 }
49 
50 void add(long long *b, int i, int v)
51 {
52     while (i<=N)
53     {
54         b[i]+=v;
55         i+=i&-i;
56     }
57 }
58 
59 void solve();
60 
61 int main()
62 {
63     read(N);read(Q);
64     for (int i=1; i<=N; i++) read(A[i]);
65     for (int i=0; i<Q; i++)
66     {
67         scanf("%c", &T[i]);
68         if (T[i]=='Q') {read(L[i]);read(R[i]);}
69         else {read(L[i]);read(R[i]);read(X[i]);}
70     }
71     solve();
72 }
73 
74 void solve()
75 {
76     for (int i=1; i<=N; i++)
77     {
78         add(bit0, i, A[i]);
79     }
80     for (int i=0; i<Q; i++)
81     {
82         if (T[i]=='C')
83         {
84             add(bit0, L[i], -X[i]*(L[i]-1));
85             add(bit1, L[i], X[i]);
86             add(bit0, R[i]+1, X[i]*R[i]);
87             add(bit1, R[i]+1, -X[i]);
88         }
89         else
90         {
91             long long res=0;
92             res+=sum(bit0, R[i])+sum(bit1, R[i])*R[i];
93             res-=sum(bit0, L[i]-1)+sum(bit1, L[i]-1)*(L[i]-1);
94             printf("%lld
", res);
95         }
96     }
97 }
    2

 分桶法(bucket method)和平方分割(sqrt decomposition)

分桶法：把一排物品或者平面分成桶，每个桶分别维护自己内部的信息，以达到高效计算的目的的方法。

平方分割：把排成一排的n个元素每√n个分在一个桶内进行维护的方法的统称。这样的分割方法可以使对区间的操作的复杂度降至O(√n)。和线段树一样，根据维护的数据的不同，平方分割可以支持很多不同的操作。

基于平方分割的RMQ：

　　给定一个数列a1,a2,…,an，目标是在O(√n)复杂度内实现：
　　①给定s和t，求as，as+1，…，at的最小值
　　②给定i和x，把ai的值改成x

基于平方分割的RMQ的预处理：

　　令b=floor(√n)，把a中的元素每b分成一个桶，并且计算出每个桶内的最小值。

基于平方分割的RMQ的查询：

　　①如果桶完全包含在区间内，则查询桶的最小值

　　②如果元素所在的桶不完全被区间包含，则逐个检查最小值。

　　它们的最小值就是区间的最小值了。

基于平方分割的RMQ的值的更新：

　　在更新元素的值时，需要更新该元素所在的桶的最小值。这是只要遍历一遍桶内的元素就可以了。

基于平方分割的RMQ的复杂度：

　　在更新值时，因为每个桶内有b个元素，所以复杂度是O(b)=O(√n)

　　而在查询时，

　　①完全包含在区间内的桶的个数是O(n/b)

　　②所在的桶不被区间完全包含的元素个数是O(b)

　　因为b=O(√n)，所以操作的复杂度是O((n/b)+b)=O(√n+√n)=O(√n)

平方分割和线段树：

　　在平方分割中，对于任意区间，完全包含于其中的桶的数量和剩余元素的数量都是O(√n)，所以可以在O(√n)时间内完成各种操作。

　　在上面的RMQ例题中，线段树进行各种操作的复杂度是O(log n)，比平方分割快一些。

　　一般地，如果线段树和平方分割都能实现某个功能，多数情况下线段树会比平方分割快，但是，因为平方分割在实现上比线段树简单，所以如果运行时间限制不太紧时，可以考虑平方分割 。

　　除此之外，也有一些功能是线段树无法高效维护但是平方分割却可以做到的。

PS：这里介绍的平方分割的实现所用的数据结构通常也叫做块状数组。

K-th Number(POJ 2104)

  • 原题如下：
    K-th Number
    Time Limit: 20000MS Memory Limit: 65536K
    Total Submissions: 68387 Accepted: 24173
    Case Time Limit: 2000MS

    Description

    You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment. 
    That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?" 
    For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

    Input

    The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000). 
    The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given. 
    The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

    Output

    For each question output the answer to it --- the k-th number in sorted a[i...j] segment.

    Sample Input

    7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

    Sample Output

    5
6
3

    Hint

    This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.
  • 题解1：
  • 如果x是第k个数，那么一定有①在区间中不超过x的数不少于k ②在区间中小于x的数有不到k个，因此，只要快速求出区间里不超过x的数的个数，就可以通过对x进行二分搜索来求出第k个数是多少。如果不进行预处理，就只能遍历一遍所有元素，如果每个区间有序，可以用二分高效地求不超过x的数的个数，但每个查询做一次排序无法降低复杂度。综上，考虑平方分割或线段树求解。
    平方分割：把数列每b个一组分到各个桶里，每个桶内保存排好序的数列。这样的话，如果要求在某个区间内不超过x的数的个数就可以①对于完全包含在区间内的桶用二分搜索计算②对于所在的桶不完全包含在区间内的元素，逐个检查，如果把b设为√n，复杂度就为O((n/b)logb+b)=O(√nlogn)。其中对于每个元素的处理只需要O(1)的时间，而对于每个桶的处理则需要O(logb)，为了让程序更加高效，应该把桶的数量设置成比桶内元素个数略少一些。如果把b设为√(nlogn)，复杂度就变为O((n/b)logb+b)=O(√(nlogn))，接下来只需要对x进行二分搜索就行了，二分搜索需要执行O(logn)次，因此，如果b=√(nlogn),包括预处理在内的整个算法的复杂度就是O(nlogn+m(√n)log1.5n)。
  • 代码1： 
     1 #include <cstdio>
 2 #include <cctype>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <cstring>
 6 #define number s-'0'
 7 using namespace std;
 8 
 9 const int MAX_N=100005;
10 int N,M;
11 int A[MAX_N], nums[MAX_N], bucket[MAX_N];
12 
13 void read(int &x){
14     char s;
15     x=0;
16     bool flag=0;
17     while(!isdigit(s=getchar()))
18         (s=='-')&&(flag=true);
19     for(x=number;isdigit(s=getchar());x=x*10+number);
20     (flag)&&(x=-x);
21 }
22 
23 void write(int x)
24 {
25     if(x<0)
26     {
27         putchar('-');
28         x=-x;
29     }
30     if(x>9)
31         write(x/10);
32     putchar(x%10+'0');
33 }
34 
35 int main()
36 {
37     read(N);read(M);
38     for (int i=0; i<N; i++) read(A[i]);
39     int B=sqrt(N*log(N+0.0)+0.0);
40     if (!B) B++;
41     memcpy(nums, A, sizeof(A));
42     memcpy(bucket, A, sizeof(A));
43     sort(nums, nums+N);
44     for (int i=0; i+B<=N; i+=B) sort(bucket+i, bucket+i+B);
45     int l, r, k;
46     for (int i=0; i<M; i++)
47     {
48         read(l);read(r);read(k);
49         l--;
50         int s=(l/B+1)*B, e=r/B*B;
51         int lb=-1, ub=N-1, md, x;
52         while (ub-lb>1)
53         {
54             md=(lb+ub)/2;
55             x=nums[md];
56             int c=0;
57             for (int i=l; i<s && i<r; i++) if (A[i]<=x) c++;
58             for (int i=e; i<r && i>l; i++) if (A[i]<=x) c++;
59             for (int i=s; i+B<=e; i+=B)
60             {
61                 c+=upper_bound(bucket+i, bucket+i+B, x)-bucket-i;
62             }
63             if (c>=k) ub=md;
64             else lb=md;
65         }
66         write(nums[ub]);putchar('
');
67     }
68 }
    平方分割
  • 题解2：
    线段树：把数列用线段树维护起来，线段树的每个节点保存对应区间排好序后的结果。这里和之前接触到的线段树节点保存数值不同，这里每个节点保存了一个数列。建立线段树的过程和归并排序的类似，而每个节点的数列就是其两个儿子节点的数列合并后的结果。建树的复杂度是O(nlogn)。这棵线段树正是归并排序的完整再现，所以这样的线段树也叫归并树。要计算在某个区间中不超过x的数的个数，只需要递归地进行如下操作：①如果所给区间和当前节点的区间完全没有交集，那么返回0 ②如果所给区间完全包含了当前节点对应的区间那么使用二分搜索对该节点上保存的数列进行查找 ③否对对两个儿子递归地进行计算之后求和即可。由于对于同一深度的节点最多只访问常数个，因此可以在O(log2n)时间里求出不超过x的数的个数。所以整个算法的复杂度是O(nlogn+mlog3n)。
  • 代码2： 
     1 #include <cstdio>
 2 #include <cctype>
 3 #include <cmath>
 4 #include <vector>
 5 #include <algorithm>
 6 #define number s-'0'
 7 
 8 using namespace std;
 9 
10 const int ST_SIZE=(1<<18)-1;
11 const int MAX_N=100000;
12 const int MAX_M=5000;
13 int N,M;
14 int A[MAX_N];
15 int I[MAX_M], J[MAX_M], K[MAX_M];
16 int nums[MAX_N];
17 vector<int> dat[ST_SIZE];
18 
19 void read(int &x){
20     char s;
21     x=0;
22     bool flag=0;
23     while(!isdigit(s=getchar()))
24         (s=='-')&&(flag=true);
25     for(x=number;isdigit(s=getchar());x=x*10+number);
26     (flag)&&(x=-x);
27 }
28 
29 void write(int x)
30 {
31     if(x<0)
32     {
33         putchar('-');
34         x=-x;
35     }
36     if(x>9)
37         write(x/10);
38     putchar(x%10+'0');
39 }
40 
41 void solve();
42 void init(int k, int l, int r);
43 int query(int i, int j, int x, int k, int l, int r);
44 
45 int main()
46 {
47     read(N);read(M);
48     for (int i=0; i<N; i++) read(A[i]);
49     for (int i=0; i<M; i++) {read(I[i]);read(J[i]);read(K[i]);}
50     solve();
51 }
52 
53 void solve()
54 {
55     for (int i=0; i<N; i++) nums[i]=A[i];
56     sort(nums, nums+N);
57     init(0, 0, N);
58     for (int i=0; i<M; i++)
59     {
60         int l=I[i]-1, r=J[i], k=K[i];
61         int lb=-1, ub=N-1;
62         while (ub-lb>1)
63         {
64             int md=(ub+lb)/2;
65             int c=query(l, r, nums[md], 0, 0, N);
66             if (c>=k) ub=md;
67             else lb=md;
68         }
69         write(nums[ub]);putchar('
');
70     }
71 }
72 
73 void init(int k, int l, int r)
74 {
75     if (r-l==1) dat[k].push_back(A[l]);
76     else
77     {
78         int lch=k*2+1, rch=k*2+2;
79         init(lch, l, (l+r)/2);
80         init(rch, (l+r)/2, r);
81         dat[k].resize(r-l);
82         merge(dat[lch].begin(), dat[lch].end(), dat[rch].begin(), dat[rch].end(), dat[k].begin());
83     }
84 }
85 
86 int query(int i, int j, int x, int k, int l, int r)
87 {
88     if (j<=l || r<=i) return 0;
89     else if (i<=l && r<=j) return upper_bound(dat[k].begin(), dat[k].end(), x)-dat[k].begin();
90     else
91     {
92         int lc=query(i, j, x, k*2+1, l, (l+r)/2);
93         int rc=query(i, j, x, k*2+2, (l+r)/2, r);
94         return lc+rc;
95     }
96 }
    线段树

区域树(Range Tree)

上面提到的每个节点维护一个数组的线段树和每个节点维护一棵树的线段树也叫做区域树。

如果把数列ai考虑成平面上(i,ai)的点列，那么上面问题中的查询"计算区间[l,r)中不超过v的数的个数"就可以看成是"计算满足1≤x<r,y≤v的点的个数"

Range Tree适合对矩形的区域进行处理，并且和树状数组一样通过多重嵌套的线段树也可以实现高维度的Range Tree

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Ymir-TaoMee/p/9510685.html