目錄

• 線段樹
  • 例題
    • 題面
  • 練習
    • 1
    • 2
    • 3
    • 4
    • 5
  • 小解區間操作
• 二叉堆
  • 例題
  • 思路

@

線段樹

例題

題面

時間限制: 1 Sec 內存限制: 128 MB 【題意】給出N個數，兩種操作：1、C x y：修改第x個數的值為y；2、P x y：求第x到第y個的最大值，注：x未必比y小【輸入格式】第一行輸入N和M（0<N<=200000,0<M<5000），N表示有N個數，M表示有M個操作；下來N個數ai（ 0<=|ai|<=10^6 ）；然后是M個操作。【輸出格式】遇到P操作的時候，輸出結果。【樣例輸入】 5 61 2 3 4 5P 1 5C 3 6P 3 4P 4 5C 2 9P 1 5 【樣例輸出】 5659

### 思路
我們都知道，江湖上有個算法叫線段樹。

他是怎么搞的呢？

首先我們看向這么一個序列：\(1,2,3,4,5\)

我們申請一個根節點管理的是\(1,2,3,4,5\)。

但是這么多點是不是有點麻煩？

于是，根節點又申請了左右兒子，左兒子管理的是\(1,2,3\)，右兒子是\(4,5\)。

也就是\(l=1,r=5,mid=(l+r)/2=3\)，然后左兒子管理的是\(l,mid\)，右兒子管理的是\(mid+1,r\)。

然后左右兒子又去申請左右兒子，直到他管理的是一個人。

然后每個點都要維護區間的信息。

查詢修改跳兒子就行了。

#include<bits/stdc++.h> using namespace std; int a[210000]; struct node {int l,r,lc,rc,c; }tr[410000];int len,n,m; void bt(int l,int r) {len++;int now=len;tr[now].l=l;tr[now].r=r;if(l==r)tr[now].c=a[l];else{int mid=(l+r)/2;tr[now].lc=len+1;bt(l,mid);tr[now].rc=len+1;bt(mid+1,r);tr[now].c=max(tr[tr[now].lc].c,tr[tr[now].rc].c);} } void change(int now,int x,int k) {if(tr[now].l==tr[now].r){tr[now].c=k;return ;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(x<=mid)change(lc,x,k);else change(rc,x,k);tr[now].c=max(tr[lc].c,tr[rc].c);//在每次change完別忘記維護自己的信息 } int findans(int now,int l,int r) {if(tr[now].l==l && tr[now].r==r)return tr[now].c;int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(r<=mid)return findans(lc,l,r);else if(mid+1<=l)return findans(rc,l,r);else return max(findans(lc,l,mid),findans(rc,mid+1,r)); } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);bt(1,n);for(int i=1;i<=m;i++){char ss[10];int x,y;scanf("%s%d%d",ss,&x,&y);if(ss[0]=='C')change(1,x,y);else{if(x>y)swap(x,y);printf("%d\n",findans(1,x,y));}}return 0; }

很容易看出時間復雜度為\(O(nlogn)\)。

練習

1

時間限制: 1 Sec 內存限制: 128 MB 【題意】有L段線段（編號為1～L， (0 <= L <= 1000000)），一開始全部線段是顏色1。有兩種操作： 1、C A B tt ：把第A至第B個線段染成第tt種顏色 2、P A B ：詢問第A至第B個線段有多少種不一樣的顏色。注意： 1、A有可能比B大。 2、顏色的編號<=50; 數據較水，不用擔心特殊的情況，按照題解打也能AC，數據強的版本已放在1238 【輸入格式】第一行含有兩個整數 L and M (1 <= M <= 100000). M代表操作次數. 下來M行操作【輸出格式】有詢問的時候輸出【樣例輸入】 2 4C 1 1 2P 1 2C 2 2 2P 1 2 【樣例輸出】 21

這題我們的\(c\)表示的是如果有多種顏色的話為\(-1\)，否則就為這個唯一的顏色的編號。
查詢是暴力區間查。
但是正解應該是每個節點多套個bitset（STL里面的好東西），外面也用個bitset記錄答案，然后辦到\(O(nlogn)\)。

這種非正解做法理論復雜度\(O(n^2)\)，但數據水呀。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node {int l,r,lc,rc,c; }tr[2100000];int len,n,m; bool v[2100]; void bt(int l,int r) {len++;int now=len;tr[now].l=l;tr[now].r=r;tr[now].c=1;if(l<r){int mid=(l+r)/2;tr[now].lc=len+1;bt(l,mid);tr[now].rc=len+1;bt(mid+1,r);} } int findans(int now,int l,int r) {if(tr[now].c!=-1){if(v[tr[now].c]==true){v[tr[now].c]=false;return 1;}else return 0;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(r<=mid)return findans(lc,l,r);else if(mid+1<=l)return findans(rc,l,r);else return findans(lc,l,mid)+findans(rc,mid+1,r); } void change(int now,int l,int r,int c) {if(tr[now].c==c)return ;if(tr[now].l==l && tr[now].r==r){tr[now].c=c;return ;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(tr[now].c!=-1)tr[lc].c=tr[rc].c=tr[now].c;if(r<=mid)change(lc,l,r,c);else if(mid+1<=l)change(rc,l,r,c);else change(lc,l,mid,c),change(rc,mid+1,r,c);if(tr[lc].c!=tr[rc].c)tr[now].c=-1;else tr[now].c=tr[lc].c;//維護本身的信息 } int main() {scanf("%d%d",&n,&m);bt(1,n);for(int i=1;i<=m;i++){char ss[10];int x,y,c;scanf("%s%d%d",ss,&x,&y);if(x>y)swap(x,y);if(ss[0]=='P'){memset(v,true,sizeof(v));printf("%d\n",findans(1,x,y));}else{scanf("%d",&c);change(1,x,y,c);}}return 0; }

2

時間限制: 1 Sec 內存限制: 128 MB 【題意】有L段線段（編號為1～L， (1 <= L <= 1 0000 0000 沒錯，就是1億 )） ，一開始全部線段是顏色1。有兩種操作： 1、C A B tt ：把第A至第B個線段染成第tt種顏色 2、P A B ：詢問第A至第B個線段有多少種不一樣的顏色。注意： 1、A有可能比B大。 2、顏色的編號<=50; 【輸入格式】第一行含有兩個整數 L and M (1 <= M <= 100000). M代表操作次數. 下來M行操作【輸出格式】有詢問的時候輸出【樣例輸入1】 2 4C 1 1 2P 1 2C 2 2 2P 1 2 【樣例輸出1】 21 【樣例輸入2】 10 3C 1 2 2C 4 10 3P 1 10 【樣例輸出2】 3

不就是個離散化嗎，離散化什么，就是把每個編號從小到大排一遍，然后把他的值改成排名，然后再操作的時候一直用排名操作，使得省了一坨空間。

但是這題有點不一樣，如果你的線段樹的每個點維護的是區間內點情況，那么每個排名之間要留個位置，為什么？因為有可能你把編號\(1,2,4,5\)改成了\(1,2,3,4\)，導致查詢的時候原本的\(3\)查不到，當然還有另外一種辦法，線段樹維護的是一個區間，然后右兒子維護的是\(mid,r\)，然后直到\(l+1==r\)的話就不申請節點了，這樣子的話也可以改成\(1,2,3,4\)，也是比較推介的做法。

這里用的是第一種方法：

#include<bits/stdc++.h> using namespace std; struct LSnode {int x,y,z; }A[510000],B[510000]; struct node {int l,r,lc,rc,c; }tr[510000];int len,n,m,kk[110000],tt; char st[110000][5]; bool cmp(LSnode x,LSnode y){return x.x<y.x;} void bt(int l,int r) {len++;int now=len;tr[now].l=l;tr[now].r=r;tr[now].c=1;if(l<r){int mid=(l+r)/2;tr[now].lc=len+1;bt(l,mid);tr[now].rc=len+1;bt(mid+1,r);} } bool v[2100]; int find(int now,int l,int r) {if(tr[now].c>0){if(v[tr[now].c]==true){v[tr[now].c]=false;return 1;}else return 0;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(r<=mid)return find(lc,l,r);else if(mid+1<=l)return find(rc,l,r);else return find(lc,l,mid)+find(rc,mid+1,r); } void change(int now,int l,int r,int k) {if(tr[now].c==k)return ;if(tr[now].l==l && tr[now].r==r){tr[now].c=k;return ;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(tr[now].c>0)tr[lc].c=tr[rc].c=tr[now].c;if(r<=mid)change(lc,l,r,k);else if(mid+1<=l)change(rc,l,r,k);else change(lc,l,mid,k),change(rc,mid+1,r,k);if(tr[lc].c==tr[rc].c)tr[now].c=tr[lc].c;else tr[now].c=-1; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%s",st[i]);if(st[i][0]=='C')scanf("%d%d%d",&A[i*2-1].x,&A[i*2].x,&kk[i]);else scanf("%d%d",&A[i*2-1].x,&A[i*2].x);if(A[i*2-1].x>A[i*2].x)swap(A[i*2-1].x,A[i*2].x);A[i*2-1].z=i*2-1;A[i*2].z=i*2;B[i*2-1]=A[i*2-1];B[i*2]=A[i*2];}sort(B+1,B+m*2+1,cmp);B[0].x=999999999;for(int i=1;i<=m*2;i++){if(B[i].x!=B[i-1].x){if(B[i].x==B[i-1].x+1)tt++;//如果兩個數字不是貼在一起的話，就直接+2else tt+=2;}A[B[i].z].y=tt;}bt(1,tt);for(int i=1;i<=m;i++){if(st[i][0]=='C')change(1,A[i*2-1].y,A[i*2].y,kk[i]);else{memset(v,true,sizeof(v));printf("%d\n",find(1,A[i*2-1].y,A[i*2].y));}} return 0; }

3

【題意】有n(1~100000)個連續的格子，編號為1……n，每個格子的顏色有3種（分別是1、2、3）。有m（1~100000）操作，操作有2種：1 x y k：表示第x個格子至第y個格子全染色為k（1<=k<=3)2 x y:表示詢問第x個格子至第y個格子有多少條線段（相鄰兩個格子的顏色相同則同屬一條線段）。【輸入格式】第一行n和m。第二行n個數，分別表格n個格子的顏色。下來m行，每行表示一個操作。【輸出格式】遇到操作2，則輸出答案【樣例輸入】 5 52 1 1 2 12 1 51 4 4 12 1 51 1 1 12 1 5 【樣例輸出】 421

第2個需要設個全局變量。
然后就沒什么了。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node {int l,r,lc,rc,c; }tr[210000];int len,n,m,a[110000],cc/*多設一個全局變量*/; void bt(int l,int r) {len++;int now=len;tr[now].l=l;tr[now].r=r;if(l==r)tr[now].c=a[l];else{int mid=(l+r)/2;tr[now].lc=len+1;bt(l,mid);tr[now].rc=len+1;bt(mid+1,r);if(tr[tr[now].lc].c==tr[tr[now].rc].c)tr[now].c=tr[tr[now].lc].c;else tr[now].c=-1;} } void change(int now,int l,int r,int k) {if(tr[now].c==k)return ;if(tr[now].l==l && tr[now].r==r){tr[now].c=k;return ;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(tr[now].c>0)tr[lc].c=tr[rc].c=tr[now].c;if(r<=mid)change(lc,l,r,k);else if(mid+1<=l)change(rc,l,r,k);else change(lc,l,mid,k),change(rc,mid+1,r,k);if(tr[lc].c==tr[rc].c)tr[now].c=tr[lc].c;else tr[now].c=-1; } int find(int now,int l,int r) {if(tr[now].c>0){if(cc!=tr[now].c){cc=tr[now].c;return 1;}else return 0;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(r<=mid)return find(lc,l,r);else if(mid+1<=l)return find(rc,l,r);else return find(lc,l,mid)+find(rc,mid+1,r); } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);bt(1,n);while(m--){int x,y,k,z;scanf("%d%d%d",&k,&x,&y);if(x>y)swap(x,y);if(k==1){scanf("%d",&z);change(1,x,y,z);}else{cc=0;printf("%d\n",find(1,x,y));}}return 0; }

4

【題目描述】 先是在數軸區間 0 到10^9 (10的9次方）之間畫上了白色。然后，這個區間的某一些部分又畫上了黑色。然后某一些部分又畫上白色，等等。請你找出經歷M(1 <= M <= 5000)次著色操作后，最長的白色區間。【輸入格式】首行位M,以下M行位重著色的信息，每一行格式如下：ai bi ci 這里 ai ，bi 都是整數, ci 為字符'b' 或'w'，用空格隔開。這三個參數描述：從ai到bi,著顏色ci, ('w'表示白，'b'表示黑），可以認為0 < ai <= bi < 10^9 【輸出格式】輸出x，y (x < y)，之間用空格隔開，表示最長的白色區間。假如有多個答案，輸出x最小的那個 【樣例輸入】 41 999999997 b40 300 w300 634 w43 47 b 【樣例輸出】 47 634這道題：線段樹+離散化 PS:最開始1-10^9的染白不算在M次操作里面

一道海星的題目，挺簡單的，就實現復雜罷了。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct LSnode {int x,y,z; }A[21000],B[21000]; int K[21000]; struct node {int l,r,lc,rc,c; }tr[210000];int len,m,kk,tt[21000],ans1,ans2,cc,tt1,tt2; bool cmp(LSnode x,LSnode y){return x.x<y.x;} void bt(int l,int r) {len++;int now=len;tr[now].l=l;tr[now].r=r;tr[now].c=0;if(l+1<r){int mid=(l+r)/2;tr[now].lc=len+1;bt(l,mid);tr[now].rc=len+1;bt(mid,r);} } void change(int now,int l,int r,int k) {if(tr[now].c==k)return ;if(tr[now].l==l && tr[now].r==r){tr[now].c=k;return ;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(tr[now].c>=0)tr[lc].c=tr[rc].c=tr[now].c;if(r<=mid)change(lc,l,r,k);else if(mid<=l)change(rc,l,r,k);else change(lc,l,mid,k),change(rc,mid,r,k);if(tr[lc].c==tr[rc].c)tr[now].c=tr[lc].c;else tr[now].c=-1; } void find(int now,int l,int r) {if(tr[now].c>=0){if(cc!=tr[now].c){cc=tr[now].c;if(cc==0)tt1=l,tt2=tt[r]-tt[l];else if(tt2>ans2){ans1=tt1,ans2=tt2;}}else{if(cc==0)tt2+=tt[r]-tt[l];}return ;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;find(lc,l,mid);find(rc,mid,r); } int main() {scanf("%d",&m);for(int i=1;i<=m;i++){char ss[10];scanf("%d%d%s",&A[i*2-1].x,&A[i*2].x,ss);if(A[i*2-1].x>A[i*2].x)swap(A[i*2-1].x,A[i*2].x);A[i*2-1].z=i*2-1;A[i*2].z=i*2;B[i*2-1]=A[i*2-1];B[i*2]=A[i*2];if(ss[0]=='w')K[i]=0;else K[i]=1;}sort(B+1,B+m*2+1,cmp);kk++;for(int i=1;i<=m*2;i++){if(B[i].x!=B[i-1].x){kk++;tt[kk]=tt[kk-1]+(B[i].x-B[i-1].x);}A[B[i].z].y=kk;}if(B[m*2].x!=1000000000){kk++;tt[kk]=tt[kk-1]+(1000000000-B[2*m].x);}bt(1,kk);for(int i=1;i<=m;i++){if(A[i*2-1].y!=A[i*2].y)change(1,A[i*2-1].y,A[i*2].y,K[i]);}find(1,1,kk);if(cc==0){if(tt2>ans2){ans1=tt1,ans2=tt2;}}printf("%d %d\n",tt[ans1],tt[ans1]+ans2);return 0; }

5

【題目描述】遠望城市的地平線，地平線上豎立著一些矩形的建筑物，現在要求知道這些矩形的覆蓋面積（會有重疊面積，但不重復算，只算所有建筑物輪廓覆蓋的面積）。所有矩形的下邊與地平線重疊。現在有N個矩形，每個矩形給出 左邊X坐標Ai和右邊的X坐標Bi，和上邊的Y坐標Hi（下邊的Y坐標就是0）【范圍】1 ≤ N ≤ 40,000 , 0 ≤ Ai ≤ Bi ≤ 1,000,000,000, 1 ≤ Hi ≤ 1,000,000,000 【輸入格式】第一行 N ，下來N行，每行三個整數 Ai, Bi, and Hi 【輸出格式】一個整數，整個建筑群的輪廓覆蓋的總面積。 Sample Input42 5 19 10 46 8 24 6 3Sample Output16 提示：3*1 + 1*4 + 2*2 + 2*3 - 1 = 16.

離散化，然后每個線段樹的區間表示的是這個區間的輪廓。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node {int l,r,lc,rc,c; }tr[210000];int len,n; struct LSnode {int x,y,z; }A[210000],B[210000];int K[210000],kk,tt[210000]; bool cmp(LSnode x,LSnode y){return x.x<y.x;} void bt(int l,int r) {len++;int now=len;tr[now].l=l;tr[now].r=r;if(l+1<r){int mid=(l+r)/2;tr[now].lc=len+1;bt(l,mid);tr[now].rc=len+1;bt(mid,r);} } void change(int now,int l,int r,int k) {if(tr[now].c>=k)return ;if(tr[now].l==l && tr[now].r==r && tr[now].c>=0){tr[now].c=k;return ;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(tr[now].c>=0)tr[lc].c=tr[rc].c=tr[now].c;if(r<=mid)change(lc,l,r,k);else if(mid<=l)change(rc,l,r,k);else change(lc,l,mid,k),change(rc,mid,r,k);if(tr[lc].c==tr[rc].c)tr[now].c=tr[lc].c;else tr[now].c=-1; } int find(int now,int l,int r) {if(tr[now].c>=0)return tr[now].c*(tt[r]-tt[l]);int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;return find(lc,l,mid)+find(rc,mid,r); } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&A[i*2-1].x,&A[i*2].x,&K[i]);A[i*2-1].z=i*2-1;A[i*2].z=i*2;B[i*2-1]=A[i*2-1];B[i*2]=A[i*2];}sort(B+1,B+n*2+1,cmp);kk=1;A[B[1].z].y=1;for(int i=2;i<=n*2;i++){if(B[i].x!=B[i-1].x){kk++;tt[kk]=tt[kk-1]+B[i].x-B[i-1].x;}A[B[i].z].y=kk;}bt(1,kk);for(int i=1;i<=n;i++){if(A[i*2-1].y!=A[i*2].y)change(1,A[i*2-1].y,A[i*2].y,K[i]);}printf("%d\n",find(1,1,kk));return 0; }

小解區間操作

區間修改我們可以通過打懶標記的方式實現，什么是懶標記，就是當一個點的區間和我們要修改的樣的時候，我們可以靈性的給他打個標記，然后在查詢的時候在下傳標記就行了。

區間查詢我們早就會了。

二叉堆

例題

【題意】 給出n個正整數，輸出最大的m個數。【輸入格式】 第一行兩個整數n和m（1<=n<=500000,1<=m<=5000）第二行給出n個整數（0<=a[i]<=100000) 【輸出格式】按照從大到小的順序輸出。兩數之間有空格。【樣例輸入】 5 32 4 5 1 3 【樣例輸出】 5 4 3

思路

二叉堆的思路很簡單，就是盡量構造一個完美二叉樹，然后維護每個點的點權大（小）于自己的兒子節點，而且一個點\(x\)的父親是\(x>>1\)，兒子是\(x<<1\)和\((x<<1)+1\)。

然后加點就\(++len\)，然后從下往上傳。

\(POP\)就是把\(a[1]\)和\(a[len]\)交換一下，然后從\(1\)開始下傳。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[210000],n,m; void heap(int i)//自上往下的函數，自下往上的自己想想，十分簡單 {int j=i*2;while(j<=n){if(j<n && a[j]<a[j+1])j++;if(a[j]>a[i]){swap(a[i],a[j]);i=j;j=i*2;}else break;} } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=n/2;i>=1;i--)heap(i);//建堆for(int i=1;i<m;i++){printf("%d ",a[1]);a[1]=a[n];n--;heap(1);}printf("%d\n",a[1]);return 0; }

轉載于:https://www.cnblogs.com/zhangjianjunab/p/11362396.html

總結

以上是生活随笔為你收集整理的线段树、二叉堆以及离散化入门的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。