題目描述

博艾的富金森林公園里有一個長長的富金山脈，山脈是由一塊塊巨石并列構成的，編號從1到N。每一個巨石有一個海拔高度。而這個山脈又在一個盆地中，盆地里可能會積水，積水也有一個海拔高度，所有嚴格低于這個海拔高度的巨石，就會在水面下隱藏。

由于地殼運動，巨石的海拔高度可能會隨時變化，每次一塊的巨石會變成新的海拔高度。當然，水面的高度也會隨時發生變化。

因為有這樣奇妙的地質奇觀，吸引了很多游客來游玩。uim作為一個游客，可以告訴你此時水位海拔，你得告訴他，能看到有幾個連續露出水面的部分。（與水面持平我們也認為是露出）

輸入輸出格式

輸入格式：

?

第一行兩個整數N和M,分別表示N塊石頭，M個詢問。

接下來一行，N個整數Ai表示每個巨石的初始海拔。

接下來M行，每行有兩個或者三個數，每一行如果第一個數是1，那么后面跟一個Bj，表示水面海拔。如果第一個數是2，后面跟兩個整數，Cj和Dj，表示編號Cj的巨石海拔變為Dj。

?

輸出格式：

?

對于每個"1"詢問，給出一個整數答案，也就是露出了幾部分的山峰。

?

輸入輸出樣例

輸入樣例#1： 5 4 8 6 3 5 4 1 5 2 4 1 1 5 1 3 輸出樣例#1： 2 1 2

說明

10%的數據， N,M<=2000

另外30%的數據， 只有"1"的詢問。

100%的數據， 1<=N,M<=200000,1<=Ai,Bj,Dj<=10^9，一定有"1"詢問

?

題解

話說模擬賽的時候這題打個暴力騙了50分

然后去網上找題解的時候愣是沒一個能看懂的

最后找了份代碼瞪了三個小時才明白是怎么回事

還是來詳細的講講好了

首先，考慮暴力，掃一遍數組，如果$h[i-1]<H<=h[i]$,那么就++ans

然后我們先撇開詢問不管，根據上述式子可以得出，如果$h[i-1]<h[i]$，那么$(h[i-1],h[i]]$之間的答案都會加一，這是一個典型的區間修改，我們可以用線段樹實現

最后，考慮詢問和修改。詢問的話，直接在線段樹上單點查詢。至于修改操作，我們可以發現，一個點被修改之后，和$h[i-1]$以及$h[i+1]$之間的關系發生改變，影響了答案，所以改之前把之前答案的影響刪去就好

ps：最后有個小細節，我們是按高度建線段樹，所以必須進行離散

1 // luogu-judger-enable-o2 2 //minamoto 3 #include<bits/stdc++.h> 4 #define N 400005 5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<15,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<15],*p1=buf,*p2=buf; 8 inline int read(){ 9 #define num ch-'0' 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch=='-')&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 int sum[N<<2|1],tag[N<<2|1]; 19 struct node{ 20 int h,id; 21 inline bool operator <(const node &b)const 22 {return h<b.h;} 23 }a[N<<1|1]; 24 int h[N<<1|1],x[N<<1|1],k[N<<1|1]; 25 int n,m,mx; 26 void pushdown(int p){ 27 if(!tag[p]) return; 28 int lson=p<<1,rson=p<<1|1; 29 sum[lson]+=tag[p],sum[rson]+=tag[p]; 30 tag[lson]+=tag[p],tag[rson]+=tag[p]; 31 tag[p]=0; 32 } 33 void change(int p,int l,int r,int ql,int qr,int x){ 34 if(ql<=l&&qr>=r){ 35 sum[p]+=x,tag[p]+=x;return; 36 } 37 pushdown(p); 38 int mid=(l+r)>>1; 39 if(ql<=mid) change(p<<1,l,mid,ql,qr,x); 40 if(qr>mid) change(p<<1|1,mid+1,r,ql,qr,x); 41 } 42 int query(int p,int l,int r,int x){ 43 if(l==r) return sum[p]; 44 pushdown(p); 45 int mid=(l+r)>>1; 46 if(x<=mid) return query(p<<1,l,mid,x); 47 else return query(p<<1|1,mid+1,r,x); 48 } 49 int main(){ 50 //freopen("testdata.in","r",stdin); 51 n=read(),m=read(); 52 for(int i=1;i<=n;++i) 53 a[i].h=read(),a[i].id=i; 54 for(int i=n+1;i<=n+m;++i){ 55 k[i]=read(); 56 if(k[i]==2) x[i]=read(); 57 a[i].h=read(); 58 a[i].id=i; 59 } 60 sort(a+1,a+1+n+m);h[a[1].id]=1; 61 for(int i=2;i<=n+m;++i) 62 h[a[i].id]=a[i].h>a[i-1].h?h[a[i-1].id]+1:h[a[i-1].id]; 63 mx=h[a[n+m].id]; 64 for(int i=1;i<=n;++i) 65 if(h[i-1]<h[i]) change(1,1,mx,h[i-1]+1,h[i],1); 66 for(int i=n+1;i<=n+m;++i){ 67 if(k[i]==2){ 68 int t=x[i]; 69 if(h[t-1]<h[t])change(1,1,mx,h[t-1]+1,h[t],-1); 70 if(t!=n&&h[t]<h[t+1])change(1,1,mx,h[t]+1,h[t+1],-1); 71 h[t]=h[i]; 72 if(h[t-1]<h[t])change(1,1,mx,h[t-1]+1,h[t],1); 73 if(t!=n&&h[t]<h[t+1])change(1,1,mx,h[t]+1,h[t+1],1); 74 75 } 76 else printf("%d\n",query(1,1,mx,h[i])); 77 } 78 return 0; 79 }

?

轉載于:https://www.cnblogs.com/bztMinamoto/p/9369585.html

總結

以上是生活随笔為你收集整理的洛谷P3616 富金森林公园的全部內容，希望文章能夠幫你解決所遇到的問題。

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