HNCU专题训练_线段树（2）

1.统计颜色，或运算的运用
2.区间第k大数
3.一个很经典的题
5.求区间相等数字的个数
6.RMQ模板题，区间最大值和最小值的差


1.很好的思路，用或运算来避免左右儿子树总相同颜色的情况。由于
T颜色种类最多30种，__int64 足够用了。
注意初始化就行。

5.关键是写对make_up()这个函数，向上更新需要考虑的问题。经典题型。

1001

  1 /*
  2 
  3 求区间[l,r]中，颜色的总类。
  4 如何避免重复？----或运算。
  5 
  6 */
  7 
  8 #include<iostream>
  9 #include<cstdio>
 10 #include<cstdlib>
 11 #include<algorithm>
 12 #define HH 1
 13 using namespace std;
 14 
 15 
 16 struct node
 17 {
 18     int l;
 19     int r;
 20     int color;
 21     __int64 num;
 22 }f[100003*8];
 23 
 24 
 25 void build(int l,int r,int n)
 26 {
 27     int mid=(l+r)/2;
 28     f[n].l=l;
 29     f[n].r=r;
 30     f[n].color=0;
 31     f[n].num=1<<1;
 32     if(l==r)
 33     return ;
 34     build(l,mid,n*2);
 35     build(mid+1,r,n*2+1);
 36 }
 37 
 38 void make_down(int n)
 39 {
 40     f[n*2].color=f[n*2+1].color=HH;
 41 
 42     f[n*2].num=f[n*2+1].num=f[n].num;
 43 
 44     f[n].color=0;
 45     f[n].num=0;
 46 }
 47 
 48 void update(int l,int r,int num,int n)
 49 {
 50     int mid=(f[n].l+f[n].r)/2;
 51 
 52     if(f[n].l==l && f[n].r==r)
 53     {
 54         f[n].color=HH;
 55         f[n].num=1<<num;
 56         return;
 57     }
 58     if(f[n].color==HH)
 59     make_down(n);
 60     if(mid>=r)
 61     update(l,r,num,n*2);
 62     else if(mid<l)
 63     update(l,r,num,n*2+1);
 64     else
 65     {
 66         update(l,mid,num,n*2);
 67         update(mid+1,r,num,n*2+1);
 68     }
 69     f[n].num=f[n*2].num|f[n*2+1].num;
 70 }
 71 
 72 __int64 query(int l,int r,int n)
 73 {
 74     int mid=(f[n].l+f[n].r)/2;
 75     __int64 cur=0;
 76     if(f[n].l==l && f[n].r==r)
 77     {
 78         return f[n].num;
 79     }
 80     if(f[n].color==HH)
 81     make_down(n);
 82     if(mid>=r)
 83     cur=query(l,r,n*2);
 84     else if(mid<l)
 85     cur=query(l,r,n*2+1);
 86     else
 87     {
 88         cur=query(l,mid,n*2)|query(mid+1,r,n*2+1);
 89     }
 90     f[n].num=f[n*2].num|f[n*2+1].num;
 91     return  cur;
 92 
 93 }
 94 
 95 int Get_num(__int64 num) //得到1的个数  很优化的算法。
 96 {
 97     int count=0;
 98     while(num)
 99     {
100         ++count;
101         num=(num-1)&num;
102     }
103     return count;
104 }
105 
106 void make_ini(int L,int T,int O)
107 {
108     int A,B,num,hxl;
109     __int64 tmp;
110     char a[5];
111     while(O--)
112     {
113         scanf("%s",a);
114         if(a[0]=='C')
115         {
116             scanf("%d%d%d",&A,&B,&num);
117             if(A>B)
118             {
119                 hxl=A;
120                 A=B;
121                 B=hxl;
122             }
123             if(num<=T)
124             update(A,B,num,1);
125         }
126         else if(a[0]=='P')
127         {
128             scanf("%d%d",&A,&B);
129             if(A>B)
130             {
131                 hxl=A;
132                 A=B;
133                 B=hxl;
134             }
135             tmp=query(A,B,1);
136             printf("%d
",Get_num(tmp));
137         }
138     }
139 }
140 
141 int main()
142 {
143     int L,T,O;
144     while(scanf("%d%d%d",&L,&T,&O)>0)
145     {
146         build(1,L,1);
147         make_ini(L,T,O);
148     }
149     return 0;
150 }
View Code

1002

 1 /*
 2 第k小的数
 3 
 4 */
 5 
 6 #include<iostream>
 7 #include<cstdio>
 8 #include<cstdlib>
 9 #include<cstring>
10 #include<algorithm>
11 #define NN 100010
12 using namespace std;
13 
14 
15 int toleft[30][NN];
16 int Tree[30][NN];
17 int Sort[NN];
18 
19 
20 void build(int l,int r,int dep)
21 {
22     int mid=(l+r)/2,sum=mid-l+1,lpos,rpos,i;
23     if(l==r) return ;
24     for(i=l;i<=r;i++)
25     if(Tree[dep][i]<Sort[mid]) sum--;
26     lpos=l;
27     rpos=mid+1;
28     for(i=l;i<=r;i++)
29     {
30         if(Tree[dep][i]<Sort[mid])
31         {
32             Tree[dep+1][lpos++]=Tree[dep][i];
33         }
34         else if(Tree[dep][i]==Sort[mid] && sum>0)
35         {
36             Tree[dep+1][lpos++]=Tree[dep][i];
37             sum--;
38         }
39         else
40         {
41             Tree[dep+1][rpos++]=Tree[dep][i];
42         }
43         toleft[dep][i]=toleft[dep][l-1]+lpos-l;
44     }
45     build(l,mid,dep+1);
46     build(mid+1,r,dep+1);
47 }
48 
49 int query(int L,int R,int l,int r,int k,int dep)
50 {
51     int mid=(L+R)/2,newl,newr,cur;
52     if(l==r) return Tree[dep][l];
53     cur=toleft[dep][r]-toleft[dep][l-1];
54     if(cur>=k)
55     {
56         newl=L+toleft[dep][l-1]-toleft[dep][L-1];
57         newr=newl+cur-1;
58         return query(L,mid,newl,newr,k,dep+1);
59     }
60     else
61     {
62         newr=r+(toleft[dep][R]-toleft[dep][r]);
63         newl=newr-(r-l-cur);
64         return query(mid+1,R,newl,newr,k-cur,dep+1);
65     }
66 }
67 
68 void make_ini(int N,int M)
69 {
70     int l,r,k;
71     while(M--)
72     {
73         scanf("%d%d%d",&l,&r,&k);
74         printf("%d
",query(1,N,l,r,k,0));
75     }
76 }
77 
78 int main()
79 {
80     int N,M,i;
81     while(scanf("%d%d",&N,&M)>0)
82     {
83         for(i=1;i<=N;i++)
84         {
85             scanf("%d",&Tree[0][i]);
86             Sort[i]=Tree[0][i];
87         }
88         sort(Sort+1,Sort+1+N);
89         build(1,N,0);
90         make_ini(N,M);
91     }
92     return 0;
93 }
View Code

1003

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstdlib>
  4 #define HH 1 //纯色
  5 using namespace std;
  6 
  7 struct st
  8 {
  9     __int64 l;
 10     __int64 r;
 11     __int64 num;
 12     __int64 color;
 13     __int64 max;
 14 }f[100003*4];
 15 __int64 date[100003];
 16 
 17 void build(__int64 l,__int64 r,__int64 n)
 18 {
 19     __int64 mid=(l+r)/2;
 20     f[n].l=l;
 21     f[n].r=r;
 22     f[n].color=0;
 23     f[n].num=0;
 24     if(l==r)
 25     {
 26         f[n].max=date[l];
 27         return;
 28     }
 29     build(l,mid,n*2);
 30     build(mid+1,r,n*2+1);
 31     f[n].max=f[n*2].max+f[n*2+1].max;
 32 }
 33 
 34 void make_down(__int64 n)
 35 {
 36 
 37     f[n*2].num+=f[n].num;
 38     f[n*2].color=HH;
 39     f[n*2].max+=f[n].num*(f[n*2].r-f[n*2].l+1);
 40 
 41     f[n*2+1].num+=f[n].num;
 42     f[n*2+1].color=HH;
 43     f[n*2+1].max+=f[n].num*(f[n*2+1].r-f[n*2+1].l+1);
 44 
 45     f[n].color=0;f[n].num=0;
 46 }
 47 
 48 void update(__int64 l,__int64 r,__int64 num,__int64 n)
 49 {
 50     __int64 mid=(f[n].l+f[n].r)/2;
 51     if(f[n].l==l && f[n].r==r)
 52     {
 53         f[n].num+=num;
 54         f[n].max+=num*(f[n].r-f[n].l+1);
 55         f[n].color=HH;
 56         return ;
 57     }
 58     if(f[n].color==HH)
 59         make_down(n);
 60     if(mid>=r)
 61         update(l,r,num,n*2);
 62     else if(mid<l)
 63         update(l,r,num,n*2+1);
 64     else
 65     {
 66         update(l,mid,num,n*2);
 67         update(mid+1,r,num,n*2+1);
 68     }
 69     f[n].max=f[n*2].max+f[n*2+1].max;
 70 }
 71 
 72 __int64 query(__int64 l,__int64 r,__int64 n)
 73 {
 74     __int64 mid=(f[n].l+f[n].r)/2;
 75     __int64 cur=0;
 76     if(f[n].l==l && f[n].r==r)
 77     {
 78         return f[n].max;
 79     }
 80     if(f[n].color==HH)
 81         make_down(n);
 82     if(mid>=r)
 83         cur= query(l,r,n*2);
 84     else if(mid<l)
 85         cur= query(l,r,n*2+1);
 86     else
 87     {
 88         cur+= query(l,mid,n*2);
 89         cur+=query(mid+1,r,n*2+1);
 90     }
 91     f[n].max=f[n*2].max+f[n*2+1].max;
 92     return cur;
 93 }
 94 
 95 int main()
 96 {
 97     __int64 n,q,i,l,r,num;
 98     char a[5];
 99     while(scanf("%I64d%I64d",&n,&q)>0)
100     {
101         for(i=1;i<=n;i++)
102             scanf("%I64d",&date[i]);
103         build(1,n,1);
104         while(q--)
105         {
106             scanf("%s",a);
107             if(a[0]=='Q')
108             {
109                 scanf("%I64d%I64d",&l,&r);
110                 printf("%I64d
",query(l,r,1));
111             }
112             else if(a[0]=='C')
113             {
114                 scanf("%I64d%I64d%I64d",&l,&r,&num);
115                 update(l,r,num,1);
116             }
117         }
118     }
119     return 0;
120 }
View Code

1005

  1 /*
  2 
  3 求区间[l,r]中，相等数字的最大个数
  4 试一试能不能A。
  5 
  6 */
  7 
  8 #include<iostream>
  9 #include<cstdio>
 10 #include<cstdlib>
 11 #include<algorithm>
 12 using namespace std;
 13 
 14 
 15 
 16 struct node
 17 {
 18     int l;
 19     int r;
 20     int lmax,rmax,max;
 21     int lnum,rnum;
 22     int len;
 23 }f[100003*4];
 24 int Date[100003];
 25 
 26 int hmax(int x,int y)
 27 {
 28     return x>y? x: y;
 29 }
 30 
 31 int hmin(int x,int y)
 32 {
 33     return x>y? y:x;
 34 }
 35 
 36 void make_up(node *father,node *l_child,node *r_child)
 37 {
 38     father->lnum=l_child->lnum;
 39     father->rnum=r_child->rnum;
 40     if(l_child->rnum!=r_child->lnum)
 41     {
 42         father->lmax=l_child->lmax;
 43         father->rmax=r_child->rmax;
 44         father->max=hmax(hmax(father->lmax,father->rmax),
 45                          hmax(l_child->max,r_child->max));
 46     }
 47     else
 48     {
 49         father->lmax=(l_child->lmax==l_child->len)? l_child->lmax+r_child->lmax:l_child->lmax;
 50         father->rmax=(r_child->rmax==r_child->len)? r_child->rmax+l_child->rmax:r_child->rmax;
 51         father->max= hmax(hmax(father->lmax,father->rmax),
 52                           hmax(l_child->max,
 53                                hmax(r_child->max,l_child->rmax+r_child->lmax)));
 54     }
 55 }
 56 
 57 void build(int l,int r,int n)
 58 {
 59     int mid=(l+r)/2;
 60     f[n].l=l;
 61     f[n].r=r;
 62     f[n].len=f[n].r-f[n].l+1;
 63     if(l==r)
 64     {
 65         f[n].lnum=Date[l];
 66         f[n].rnum=Date[l];
 67         f[n].lmax=f[n].rmax=f[n].max=1;
 68         return ;
 69     }
 70     build(l,mid,n*2);
 71     build(mid+1,r,n*2+1);
 72     make_up(&f[n],&f[n*2],&f[n*2+1]);
 73 }
 74 
 75 int query(int l,int r,int n)
 76 {
 77     int mid=(f[n].l+f[n].r)/2,cur=0,now1=0,now2=0;
 78 
 79     if(f[n].l==l && f[n].r==r)
 80     {
 81         return f[n].max;
 82     }
 83     if(mid>=r)
 84     cur=query(l,r,n*2);
 85     else if(mid<l)
 86     cur=query(l,r,n*2+1);
 87     else
 88     {
 89         now1=query(l,mid,n*2);
 90         now2=query(mid+1,r,n*2+1);
 91         if(f[n*2].rnum==f[n*2+1].lnum)
 92         {
 93             cur=hmax(hmax(now1,now2),hmin(mid-l+1,f[n*2].rmax)+
 94                      hmin(r-mid,f[n*2+1].lmax));
 95         }
 96         else
 97         {
 98             cur=hmax(now1,now2);
 99         }
100     }
101     return cur;
102 }
103 
104 void make_ini(int Q)
105 {
106     int l,r;
107     while(Q--)
108     {
109         scanf("%d%d",&l,&r);
110         printf("%d
",query(l,r,1));
111     }
112 }
113 
114 int main()
115 {
116     int N,Q,i;
117     while(scanf("%d",&N)>0)
118     {
119         if(N==0)break;
120         scanf("%d",&Q);
121         for(i=1;i<=N;i++)
122         scanf("%d",&Date[i]);
123         build(1,N,1);
124         make_ini(Q);
125     }
126 }
View Code

1006

 1 /*
 2 求区间[l,r],最大值和最小值的差值。
 3 */
 4 
 5 
 6 #include<iostream>
 7 #include<cstdio>
 8 #include<cstdlib>
 9 #include<cstring>
10 #include<algorithm>
11 #define MAX 1000010
12 using namespace std;
13 
14 
15 struct node
16 {
17     int l;
18     int r;
19     int min;
20     int max;
21 }f[50003*4];
22 int Date[50003];
23 
24 
25 int hmax(int x,int y)
26 {
27     return x>y? x:y;
28 }
29 
30 int hmin(int x,int y)
31 {
32     return x>y? y:x;
33 }
34 
35 void build(int l,int r,int n)
36 {
37     int mid=(l+r)/2;
38     f[n].l=l;
39     f[n].r=r;
40     if(l==r)
41     {
42         f[n].max=Date[l];
43         f[n].min=Date[l];
44         return;
45     }
46     build(l,mid,n*2);
47     build(mid+1,r,n*2+1);
48     f[n].max=hmax(f[n*2].max,f[n*2+1].max);
49     f[n].min=hmin(f[n*2].min,f[n*2+1].min);
50 }
51 
52 void query(int l,int r,int *a,int *b,int n)
53 {
54     int mid=(f[n].l+f[n].r)/2;
55     if(f[n].l==l && f[n].r==r)
56     {
57         if(f[n].min<*a)
58         *a=f[n].min;
59         if(f[n].max>*b)
60         *b=f[n].max;
61         return;
62     }
63     if(mid>=r)
64     query(l,r,a,b,n*2);
65     else if(mid<l)
66     query(l,r,a,b,n*2+1);
67     else
68     {
69         query(l,mid,a,b,n*2);
70         query(mid+1,r,a,b,n*2+1);
71     }
72 }
73 
74 int main()
75 {
76     int N,Q,i;
77     int a,b,l,r;
78     while(scanf("%d%d",&N,&Q)>0)
79     {
80         for(i=1;i<=N;i++)
81         scanf("%d",&Date[i]);
82         build(1,N,1);
83         while(Q--)
84         {
85             scanf("%d%d",&l,&r);
86             a=MAX;b=-1;
87             query(l,r,&a,&b,1);
88             printf("%d
",b-a);
89         }
90     }
91     return 0;
92 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/tom987690183/p/3236453.html