正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P4879

---

題目大意

有若干種操作

$Cxy:a_x?=y$

$Ixy:$加一個(原本有的話就改變)$a_x=y$

$Q:$詢問所以數的和

$Dx:$刪除第$x$個(有的才算)數。

---

解題思路

我們發現只有單點修改，和全部求和。所以$ans$表示全部的和，然后前三個操作就搞定了。
第四個操作維護一個分塊，記錄每塊有的數的個數，然后找到目標在那個塊，之后這個塊里暴力尋找，這個操作時間負責度$O(\sqrt{n})$

總體時間復雜度:$O(n\sqrt{n})$

---

$code$

#include<cstdio> #include<cmath> #include<iostream> #define ll long long #define N 500000 #define T 1000 using namespace std; ll n,m,a[N+10],ans,no[N+10],x,y,t; ll L[T],R[T],num[T],pos[N+10]; char c; int main() {scanf("%lld%lld",&n,&m);t=sqrt(N);for(ll i=1;i<=N;i++){pos[i]=(i-1)/t+1;if(i>n)no[i]=1;}for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);num[pos[i]]++;ans+=a[i];}for(ll i=1;i<=m;i++){cin>>c;if(c=='Q')printf("%lld\n",ans);else if(c=='I'){scanf("%lld%lld",&x,&y);ans-=a[x];a[x]=y;ans+=y;n=max(n,x);if(no[x]){no[x]=0;num[pos[x]]++;}}else if(c=='C'){scanf("%lld%lld",&x,&y);if(no[x]) continue;ans-=y;a[x]-=y;}else if(c=='D'){scanf("%lld",&x);ll k=1;while(x-num[k]>0)x-=num[k],k++;for(int i=(k-1)*t+1;i<=min(k*t,n);i++){if(!no[i]) --x;if(!x){num[k]--;no[i]=1;ans-=a[i];a[i]=0;break;}}}} } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P4879-ycz的妹子【分块】的全部內容，希望文章能夠幫你解決所遇到的問題。

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