2018 UESTC 线段树专题

A - 一棵简单的线段树

A[1...n]初始全为0.

$p$ A[p] <- x

2. 给两个数L和R (1≤L<R≤n), L到R区间里这几个数去掉一个最大值和一个最小值后剩下的数的和是多少。用到了max, min, sum

  1 #include <iostream>
  2 #include <cmath>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <algorithm>
  6 using namespace std;
  7 const int maxn = 1e6+6;
  8 #define LL long long
  9 #define INF 0x7fffffff
 10 
 11 int n,a[maxn],q;
 12 
 13 struct node
 14 {
 15     int l,r,mx,mn;
 16     long long sum;
 17     void update(long long x) {sum=x;mx=x;mn=x;}
 18 }tree[maxn*4];
 19 
 20 void push_up(int x)
 21 {
 22     tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
 23     tree[x].mx=max(tree[x<<1].mx,tree[x<<1|1].mx);
 24     tree[x].mn=min(tree[x<<1].mn,tree[x<<1|1].mn);
 25 }
 26 
 27 void build(int x,int l,int r)
 28 {
 29     tree[x].l=l,tree[x].r=r;
 30     tree[x].sum=0,tree[x].mx=0,tree[x].mn=0;
 31     if(l==r)
 32     {
 33         tree[x].sum=tree[x].mx=tree[x].mn=a[l];
 34     }
 35     else
 36     {
 37         int mid = (l+r)/2;
 38         build(x<<1,l,mid);
 39         build(x<<1|1,mid+1,r);
 40         push_up(x);
 41     }
 42 }
 43 
 44 void update(int x,int pos,long long val)
 45 {
 46     int L =tree[x].l, R = tree[x].r;
 47     if(L==pos&&R==pos)
 48     {
 49         tree[x].update(val);
 50     }
 51     else
 52     {
 53         int mid = (L+R)/2;
 54         if(mid>=pos)update(x<<1,pos,val);
 55         if(pos>mid)update(x<<1|1,pos,val);
 56         push_up(x);
 57     }
 58 }
 59 
 60 long long query(int x,int l,int r)
 61 {
 62     int L =tree[x].l, R = tree[x].r;
 63     if(l<=L&&R<=r)
 64         return tree[x].sum;
 65     else
 66     {
 67         long long ans=0;
 68         int mid = (L+R)/2;
 69         if(mid>=l)ans+=query(x<<1,l,r);
 70         if(r>mid)ans+=query(x<<1|1,l,r);
 71         push_up(x);
 72         return ans;
 73     }
 74 }
 75 
 76 int query_max(int x,int l,int r)
 77 {
 78     int L =tree[x].l, R = tree[x].r;
 79     if(l<=L&&R<=r)
 80         return tree[x].mx;
 81     else
 82     {
 83         int ans=-1e9-2;
 84         int mid = (L+R)/2;
 85         if(mid>=l)ans=max(ans,query_max(x<<1,l,r));
 86         if(r>mid)ans=max(ans,query_max(x<<1|1,l,r));
 87         push_up(x);
 88         return ans;
 89     }
 90 }
 91 
 92 
 93 int query_min(int x,int l,int r)
 94 {
 95     int L =tree[x].l, R = tree[x].r;
 96     if(l<=L&&R<=r)
 97         return tree[x].mn;
 98     else
 99     {
100         int ans=1e9+2;
101         int mid = (L+R)/2;
102         if(mid>=l)ans=min(ans,query_min(x<<1,l,r));
103         if(r>mid)ans=min(ans,query_min(x<<1|1,l,r));
104         push_up(x);
105         return ans;
106     }
107 }
108 
109 int main() {
110     scanf("%d",&n);
111     for(int i=1;i<=n;i++)a[i]=0;
112     build(1,1,n);
113     scanf("%d",&q);
114     for(int i=1;i<=q;i++)
115     {
116         int x,y,o;
117         scanf("%d%d%d",&o,&x,&y);
118         if(o==0)update(1,x,y);
119         else
120         {
121             long long sum=query(1,x,y);
122             int mx=query_max(1,x,y);
123             int mn=query_min(1,x,y);
124             printf("%lld
",sum-mx-mn);
125         }
126     }
127     return 0;
128 }

B - 一棵普通的线段树

A[1...n]初始全为0。

一棵裸的区间修改、区间查询的线段树

1. 区间加v

2. 区间求和

区间修改(带lazy 标记)、区间查询的线段树可以在 O(log n) 的时间内维护区间和

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 1e6+6;
 7 #define LL long long
 8 #define INF 0x7fffffff
 9 
10 int n,q,a[maxn];
11 
12 struct node{
13     int l, r;
14     LL sum, lazy;
15     void update(int x) {
16         sum += 1LL*(r-l+1)*x;
17         lazy += x;
18     }
19 }tree[maxn*4];
20 
21 void push_up(int x) {
22     tree[x].sum = tree[x<<1].sum + tree[x<<1|1].sum;
23 }
24 
25 void push_down(int x) {
26     int lazy = tree[x].lazy;
27     if(lazy) {
28         tree[x<<1].update(lazy);
29         tree[x<<1|1].update(lazy);
30         tree[x].lazy = 0;
31     }
32 }
33 
34 void build(int x, int l, int r) {
35     tree[x].l = l, tree[x].r = r;
36     tree[x].sum = tree[x].lazy = 0;
37     if(l == r) {
38         tree[x].sum = a[l];
39     }
40     else {
41         int mid = (l+r) / 2;
42         build(x<<1, l, mid);
43         build(x<<1|1, mid+1, r);
44         push_up(x);
45     }
46 }
47 
48 void update(int x, int l, int r, int val) {
49     int L = tree[x].l, R = tree[x].r;
50     if(l <= L && R <= r) {
51         tree[x].update(val);
52     }
53     else {
54         push_down(x);
55         int mid = (L+R) / 2;
56         if(mid >= l) update(x<<1, l, r, val);
57         if(r > mid) update(x<<1|1, l, r, val);
58         push_up(x);
59     }
60 }
61 
62 LL query(int x, int l, int r) {
63     int L = tree[x].l, R = tree[x].r;
64     if(l <= L && R <= r) return tree[x].sum;
65     else {
66         push_down(x);
67         int mid = (L+R) / 2;
68         LL ans = 0;
69         if(mid >= l) ans += query(x<<1, l, r);
70         if(r > mid) ans += query(x<<1|1, l, r);
71         push_up(x);
72         return ans;
73     }
74 }
75 
76 
77 int main() {
78     scanf("%d",&n);
79     for(int i=1;i<=n;i++)a[i]=0;
80     build(1,1,n);
81     scanf("%d",&q);
82     for(int i=1;i<=q;i++)
83     {
84         int o,l,r,val;
85         scanf("%d%d%d%d",&o,&l,&r,&val);
86         if(o==0)update(1,l,r,val);
87         else printf("%lld
",query(1,l,r));
88     }
89     return 0;
90 }

C - 一棵像样的线段树

假设每个Ci = i ， bn最大为n+1。

对于每个Ci，相当于询问b[i-ci] 到 b[i-1] 区间内最小未出现的数。

可以设s[x] 为x最后出现的位置。对于每个Ci，我们可以得到左区间 i - Ci；

s[1]= 0 , 其他位置初始化-1（其他值都未出现过，所以都满足s[x] < i - ci ）

凡是s[x] < i - Ci 的x均未在区间内出现过，那么我们只要找出最小的x，满足：s[x] < i - ci 即可。

可以用线段树维护s[x] ，1 <= x <= n+1 , 区间的最小值。

每次给出左区间 i - ci ，就从最大的区间查询，如果左子树的最小值>=i-ci，就递归访问右子树，否则访问左子树。

最终区间长度为1时，l（或r)即为答案。

总结：可以发现b数组最多就是1到n，那么对于1到n开一棵线段树，每个结点储存当前数出现的最后的位置。因为我们要求的是 i-ci到i-1的范围内没有出现过的第一个数，

那么我们现在储存了每个数出现的最后的位置，那么我们就找一个这个位置不在i-ci到i-1的范围内且最小的数即可。因为我们线段树是默认1到n即从小到大，所以即尽可能地往左子树找，

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int N = 1e6+6;
  5 const int maxn = N<<2;
  6 
  7 int n,a[N];
  8 int tree[maxn];
  9 int ans[N];
 10 
 11 void update_tree(int a, int b, int pos, int node, int value) {
 12     if(a>b || a>pos || b<pos) return;
 13     if(a==b) {
 14         tree[node]=value;
 15         return;
 16     }
 17     update_tree(a,(a+b)>>1,pos,node<<1,value);
 18     update_tree(((a+b)>>1)+1,b,pos,(node<<1)|1,value);
 19     tree[node]=min(tree[node<<1],tree[(node<<1)|1]);
 20 }
 21 
 22 int query_tree(int a, int b, int node, int value) {
 23     if(a==b) return a;
 24     if(tree[node<<1]<value) return query_tree(a,(a+b)>>1,node<<1,value);
 25     else return query_tree(((a+b)>>1)+1,b,(node<<1)|1,value);
 26 }
 27 
 28 int main() {
 29     int i;
 30     scanf("%d", &n);
 31     for(i=1;i<=n;i++)
 32     {
 33         scanf("%d", &a[i]);
 34     }
 35     for(i=1;i<=n;i++)
 36     {
 37         if(i==1)update_tree(1,1000003,1,1,1);
 38         else update_tree(1,1000003,ans[i],1,i);
 39         int l=i-a[i]+1;
 40         ans[i+1]=query_tree(1,1000003,1,l);
 41     }
 42     for(i=2;i<=n+1;i++)
 43         if(i<n+1)printf("%d ", ans[i]);
 44         else printf("%d
", ans[i]);
 45 
 46     return 0;
 47 }
 48 
 49 #include <bits/stdc++.h>
 50 using namespace std;
 51 
 52 const int N = 1e6+6;
 53 const int maxn = N<<2;
 54 
 55 int n, a[N], ans[N];
 56 
 57 struct node
 58 {
 59     int l,r;
 60     int min_left;
 61     void update(int value){min_left=value;}
 62 }tree[maxn];
 63 
 64 void push_up(int x)
 65 {
 66     tree[x].min_left = min(tree[x<<1].min_left,tree[x<<1|1].min_left);
 67 }
 68 
 69 void build(int x,int l,int r)
 70 {
 71     tree[x].l=l,tree[x].r=r;
 72     if(l==r)
 73     {
 74         tree[x].min_left = -1;
 75     }
 76     else
 77     {
 78         int mid = (l+r)/2;
 79         build(x<<1,l,mid);
 80         build(x<<1|1,mid+1,r);
 81         push_up(x);
 82     }
 83 }
 84 void update_tree(int x, int l, int r, int pos, int value) {
 85     if(l>r || l>pos || r<pos) return;
 86     if(l==r)
 87     {
 88         tree[x].update(value);
 89     }
 90     else
 91     {
 92         int mid = (l+r)/2;
 93         if(pos<=mid)update_tree(x<<1,l,mid,pos,value);
 94         if(pos<=r)update_tree(x<<1|1,mid+1,r,pos,value);
 95         push_up(x);
 96     }
 97 }
 98 
 99 int query_tree(int x, int l, int r, int value) {
100     if(l==r) return l;
101     int mid = (l+r)/2;
102     if(tree[x<<1].min_left<value) return query_tree(x<<1,l,mid,value);
103     else return query_tree(x<<1|1,mid+1,r,value);
104 }
105 
106 int main() {
107     int i;
108     scanf("%d", &n);
109     for(i=1;i<=n;i++)
110     {
111         scanf("%d", &a[i]);
112     }
113     build(1,1,1000003);
114     for(i=1;i<=n;i++)
115     {
116         if(i==1)update_tree(1,1,1000003,1,1);
117         else update_tree(1,1,1000003,ans[i],i);
118         int l=i-a[i]+1;
119         ans[i+1]=query_tree(1,1,1000003,l);
120     }
121     for(i=2;i<=n+1;i++)
122         if(i<n+1)printf("%d ", ans[i]);
123         else printf("%d
", ans[i]);
124 
125     return 0;
126 }

D - 一棵复杂的线段树

A[1...n]为1到n的一个全排列

对[L,R]区间，升序排序或降序排序

排完后查找第K个数

思路：线段树+二分答案

结果只要求a[k]的值，并且a数列是1-n的一个全排列，那么可以二分答案。
排序过程不好想，假设mid为答案，将>mid的设为1，<=mid的设为0。
当对 [L,R] 区间进行排序时，
1. 先求出区间内1的个数。
2. 区间全置为0.
3. 升序排序时，将最后c个数（ [R-c+1, R] ）置为1.
4. 降序排序时，将前c个数（ [L, L + c - 1] ）置为1.
所有操作进行结束后，如果 [k, k] == 1 说明 a[k] > mid ( li = mid + 1 ) , 为 0 说明 a[k] <= mid ( ri = mid ) 。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int AX = 1e5+66;
  4 int lazy[AX<<2];
  5 int s[AX<<2];
  6 int a[AX];
  7 int op[AX];
  8 int l[AX];
  9 int r[AX];
 10 int n,k;
 11 int tot;
 12 
 13 void push_down( int rt , int l , int r ){
 14     if( lazy[rt] != -1 ){
 15         int mid = ( l + r ) >> 1 ;
 16         s[rt<<1] = ( mid - l + 1 ) * lazy[rt] ;
 17         s[rt<<1|1] = ( r - mid ) * lazy[rt];
 18         lazy[rt<<1] = lazy[rt];
 19         lazy[rt<<1|1] = lazy[rt];
 20         lazy[rt] = -1;
 21     }
 22     return ;
 23 }
 24 
 25 
 26 void push_up( int rt ){
 27     s[rt] = s[rt<<1] + s[rt<<1|1];
 28     return ;
 29 }
 30 
 31 void build( int l , int r , int rt , int v ){
 32     lazy[rt] = -1;
 33     if( l == r ){
 34         s[rt] =  ( a[l] > v ) ;
 35         return ;
 36     }
 37     int mid = ( l + r ) >> 1 ;
 38     build( l , mid , rt << 1 , v );
 39     build( mid + 1 , r , rt << 1 | 1 , v);
 40     push_up(rt);
 41 }
 42 
 43 void update( int L , int R , int v , int l , int r , int rt ){
 44     if( L <= l &&  r <= R ){
 45         s[rt] = v * ( r - l + 1 );
 46         lazy[rt] = v;
 47         return;
 48     }
 49     push_down(rt,l,r);
 50     int mid = ( l + r ) >> 1;
 51     if( L <= mid ) update( L , R , v , l , mid , rt << 1 );
 52     if( R > mid )  update( L , R , v , mid + 1 , r , rt << 1 | 1);
 53     push_up(rt);
 54 }
 55 
 56 int query( int L , int R , int l , int r , int rt ){
 57     if( L <= l && r <= R ){
 58         return s[rt];
 59     }
 60     push_down(rt,l,r);
 61     int ans = 0 ;
 62     int mid = ( l + r ) >> 1;
 63     if( L <= mid ) ans += query( L , R , l , mid, rt << 1 );
 64     if( R > mid )  ans += query( L , R , mid + 1, r , rt << 1 | 1 );
 65     return ans ;
 66 }
 67 
 68 int main(){
 69     scanf("%d%d",&n,&k);
 70     for( int i = 1 ; i <= n ; i++ ){
 71         scanf("%d",&a[i]);
 72     }
 73     int m ;
 74     scanf("%d",&m);
 75     for( int i = 0 ; i < m ; i++ ){
 76         scanf("%d%d%d",&op[i],&l[i],&r[i]);
 77     }
 78     int li = 1 , ri = n ;
 79     while( li < ri ){    // [li,ri]
 80         int mid = ( li + ri ) >> 1 ;
 81         build( 1 , n , 1 , mid );
 82         for( int i = 0 ; i < m ; i++ ){
 83             int L = l[i];
 84             int R = r[i];
 85             int c = query( L , R , 1 , n , 1 ); // 区间查询 > mid 的个数
 86             update( L , R , 0 , 1 , n , 1 );    // 区间更新 为0
 87             if( op[i] ){
 88                 if( L <= L + c - 1 ){
 89                     update( L , L + c - 1 , 1 , 1, n , 1 ); // 区间更新
 90                 }
 91             }else{
 92                 if( R - c + 1 <= R ){
 93                     update( R - c + 1 , R , 1 , 1 , n , 1 ); // 区间更新
 94                 }
 95             }
 96         }
 97         if( query( k , k , 1 , n , 1 )) li = mid + 1; // 单点查询
 98         else ri = mid;
 99     }
100     printf("%d
",li);
101     return 0 ;
102 }