解析

寫了不少線段樹上二分，原來樹狀數組上也是可以二分的

首先如果$a_i>i$，那必然無法刪除，下面只考慮$a_i<=i$的情況
本題試圖離線不難想到，但我一開始總是按照刻板思維嘗試按序移動左端點，結果根本沒法做…
反過來想，移動右端點就可做多了
設$f_i$表示當前右端點為r的情況下，[i,r]最多可以刪掉的數量
那么我們當把r移動到r+1時，只有$f_i>=i?a_i$時才會對$f_i$產生1的貢獻
不難發現這個f是單調不升的，所以符合上面那個條件的f應該是一段前綴，可以利用二分求出
然后就是簡單的對f區間+1，用樹狀數組維護即可

#include<bits/stdc++.h> using namespace std; const int N=3e5+100; const int mod=1e9+7; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; }int n,m;int f[N],a[N],mi[20]; inline void add(int p,int v){for(;p<=n;p+=p&-p) f[p]+=v;return; } inline int ask(int p){int res(0);for(;p;p-=p&-p) res+=f[p];return res; } inline int find(int val){int res=0,pl=0;for(int k=18;k>=0;k--){if(pl+mi[k]>n||res+f[pl+mi[k]]<val) continue;pl+=mi[k];res+=f[pl];}return pl; } struct query{int l,r,id;bool operator < (const query oth)const{return r<oth.r;} }p[N]; int ans[N]; int main(){#ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);#endifmi[0]=1;for(int i=1;i<=18;i++) mi[i]=mi[i-1]<<1;n=read();m=read();for(int i=1;i<=n;i++) a[i]=i-read();for(int i=1;i<=m;i++) p[i]=(query){(int)read()+1,n-(int)read(),i};sort(p+1,p+1+m);int pl=1;//for(int i=1;i<=n;i++) printf("%d ",a[i]);//putchar('\n');for(int i=1;i<=n;i++){if(a[i]>=0){int pl=find(a[i]);//printf("i=%d pl=%d\n",i,pl);add(1,1);add(min(pl+1,i+1),-1);}while(pl<=m&&p[pl].r==i){ans[p[pl].id]=ask(p[pl].l);pl++;}}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0; } /* 2 3 7 4 9 9 1 2 8 3 1 4 2 4 */

總結

以上是生活随笔為你收集整理的CF1404C：Fixed Point Removal（离线）（树状数组二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

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