正題

---

題目大意

$n$個連續的數，第$i$個為$h_i$。有操作

給出一個$H$，詢問大于等于$H$的數能組成多少個聯通塊

修改一個位置的數。

---

解題思路

考慮計算連通塊尾的數量，我們可以發現一個位置作為聯通塊尾部當且僅當$h_i\ge H$且$h_{i+1}<H$。

也就是如果$h_{i+1}>h_i$，那$h_i$能作為尾部的情況當且僅當$H\in [h_{i+1}+1,h_i]$。用樹狀數組維護每個位置的貢獻區間即可。

時間復雜度$O((n+q)\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) (x&-x) using namespace std; const int N=2e6+10,S=2e6+1; int n,m,t[N],a[N]; void Change(int x,int w){x++;while(x<S){t[x]+=w;x+=lowbit(x);}return; } int Ask(int x){int ans=0;x++;while(x){ans+=t[x];x-=lowbit(x);}return ans; } int main() {freopen("patrick.in","r",stdin);freopen("patrick.out","w",stdout);scanf("%d%d",&n,&m);a[n+1]=0;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=0;i<=n;i++)if(a[i]>a[i+1]){Change(a[i+1],1);Change(a[i],-1);}int last=0;for(int i=1;i<=m;i++){char op[5];int x,y;scanf("%s",op);if(op[0]=='Q'){scanf("%d",&x);x^=last;x--;printf("%d\n",last=Ask(x));}else{scanf("%d%d",&x,&y);x^=last;y^=last; if(a[x-1]>a[x])Change(a[x],-1),Change(a[x-1],1);if(a[x]>a[x+1])Change(a[x],1),Change(a[x+1],-1);a[x]=y;if(a[x-1]>a[x])Change(a[x],1),Change(a[x-1],-1);if(a[x]>a[x+1])Change(a[x],-1),Change(a[x+1],1);}} }

總結

以上是生活随笔為你收集整理的jzoj6801-NOIP2020.9.19模拟patrick【树状数组】的全部內容，希望文章能夠幫你解決所遇到的問題。

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