題意：給定n個點的高度，支持修改和求高度大等于給定的值的連續的段數量。n<=100000

題解：段數=大等于高度的數量-相鄰兩個數的較小值大等于高度的數量。線段樹或者樹狀數組

復雜度nlogn

#include<iostream> #include<cstdio> #include<algorithm> #define N 524288 using namespace std; int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}return x*f; } int T1[N*2+5],T2[N*2+5]; struct ques {int op,x,y; }c[200005];int n,m,cnt=0; int s[200005]; int l[500005];int query(int*T,int l,int r) { // cout<<"query"<<l<<" "<<r<<endl;int sum=0;for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1){if(~l&1) sum+=T[l+1];if( r&1) sum+=T[r-1]; }return sum; }void renew(int*T,int x,int ad) {T[x+=N]+=ad;for(x>>=1;x;x>>=1)T[x]=T[x<<1]+T[(x<<1)+1]; }int main() {n=read();m=read();for(int i=1;i<=n;i++)s[i]=l[i]=read();for(int i=1;i<=m;i++){c[i].op=read();c[i].x=read();if(c[i].op==2) l[i+n]=c[i].y=read();else l[i+n]=c[i].x;}sort(l+1,l+n+m+1);for(int i=1;i<=n+m;i++)if(l[i]!=l[i-1]) l[++cnt]=l[i];for(int i=1;i<=n;i++){s[i]=lower_bound(l+1,l+cnt+1,s[i])-l;renew(T1,s[i],1);}for(int i=1;i<=n;i++)renew(T2,min(s[i],s[i-1]),1); for(int i=1;i<=m;i++){if(c[i].op==1){c[i].x=lower_bound(l+1,l+cnt+1,c[i].x)-l;printf("%d\n",query(T1,c[i].x,cnt)-query(T2,c[i].x,cnt));}else {c[i].y=lower_bound(l+1,l+cnt+1,c[i].y)-l;if(c[i].x!=1) renew(T2,min(s[c[i].x],s[c[i].x-1]),-1);if(c[i].x!=n) renew(T2,min(s[c[i].x],s[c[i].x+1]),-1);renew(T1,s[c[i].x],-1);s[c[i].x]=c[i].y;renew(T1,c[i].y,1);if(c[i].x!=1) renew(T2,min(s[c[i].x],s[c[i].x-1]),1);if(c[i].x!=n) renew(T2,min(s[c[i].x],s[c[i].x+1]),1);}}return 0; }

提答題亂搞大概50分，34題都不會

轉載于:https://www.cnblogs.com/FallDream/p/luogu2.html

總結

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

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