題目鏈接：點擊查看

題目大意：給出一個長度為 n 的數列 a ，規定當 a[ i ] == i 時，位置 i 可以被刪除掉，后面位置會合并上來，現在需要回答 m 次詢問，每次詢問會問禁用掉后面 x 個數字和后面的 y 個數字后，最多可以刪除掉多少個數字，每個詢問都相互獨立，舉個例子比較好看：

這是樣例下面的樣例解釋，應該不難看懂

題目分析：首先 x 和 y 可以轉換成 l 和 r ，也就是詢問在某段區間 [ l , r ] 中最多可以刪除掉多少個數，其次因為每個位置的元素都會與其位置比較，所以不妨直接做差，將其轉換為與 0 進行比較，也就是將 a[ i?] 用 i - a[ i?] 代替，此時按照正負分三種情況討論：

i - a[ i ] == 0：當前位置可以直接刪除

i - a[ i ] < 0：當前位置永遠不可能被刪除

i - a[ i ] > 0：當前位置之前刪除掉?i - a[ i ] 個數字后，當前位置可以被刪除

注意每次刪除掉位置 i 后，下標 [ i + 1 , n ] 的位置由于會和 [ 1 , i - 1 ] 進行合并，所以 [ i + 1 , n ] 的 i - a[ i ] 會減少一

以上講的是暴力模擬的做法，但顯然不能直接暴力模擬去做，時間復雜度會退化為 n^2logn

接下來考慮遞推，先不考慮左區間的限制，設 f( r ) 為前綴區間 [ 1 , r ] 內最多可以刪除多少個數，遞推的轉移也非常簡單：

如果 i - a[ i ] <?0 或?i - a[ i ] >?f( i - 1 )：f( i ) = f( i - 1 )

否則 f( i ) = f( i - 1 ) + 1

僅對于前綴來說，這個遞推式還是蠻好想的，接下來我們需要用相同的思想擴展到每個前綴區間的后綴來表示所有的子區間，也就是在固定 r 后，將所維護的區間擴展到：s[ i ] = 區間 [ i , r?] 內最多可以刪除多少個數，i ∈ [ 1 , r ] 時答案正常計算，i > r 時 s[ i ] = 0，首先比較明顯的就是，隨著 r 的遞增，s 數組的每個元素相對于之前，迭代后一定是不減的，因為假如 [ l , r ] 內最多可以刪除掉 x 個數，現在任取一個 r2 > r ，那么在區間 [ l , r2 ] 中，完全可以先刪除掉 [ l , r ] 內的數，然后順便刪除掉 [ r + 1 , r2 ] 中的數，所以 s 數組的每個元素迭代后一定是不減的

再觀察一下當 r 確定后，s[ i ] 的單調性，上面那一段說的是 s 中的每個元素（相互獨立）隨著 r 的迭代呈現的趨勢，注意區分，隨著 i 的增長，s[ i ] 所表示的區間長度也隨之減少，簡單來說，任取 l1 < l2 < r ，位于區間 [ l2 , r ] 內的某個元素，可能在區間 [ l2 , r ] 內無法刪除掉，但是在區間 [ l1 , r ] 內就可以刪除掉了，感性理解一下當 r 確定后 s[ i ] 是遞減的

到此總結一下，s[ i ] 代表的是當 r 確定后，[ i , r ] 內最多可以刪除多少個數，上面說的那么復雜，其實就是為了證明以下兩點：

當 r 固定時，s[ i ] 呈非遞增的趨勢

隨著 r 的迭代，s 中的每個元素(視為相互獨立)，迭代后呈非遞減的趨勢

接下來考慮當前加入第 i 個元素后的影響：

如果 a[ i ] < 0 或 i - a[ i ] > s[ 1?]，對應著上面的 “ i - a[ i ] <?0 或?i - a[ i ] >?f( i - 1 ) ”，此時貢獻不變，s 數組也不變

否則對于每個滿足 s[ j ] >= i - a[ i ] 的 j 來說，都是可以順便刪掉第 i 個數的，故貢獻 s[ j ] ++，其余位置不變

結合上面說的，當右端點 r 確定時，s[ i?] 呈非遞增的趨勢，所以我們可以找到最右邊的一個 pos 滿足 s[ pos ] >= i - a[ i ] ，這樣顯然有：s[ 1 ] >= s[ 2 ] >= ... >= s[ pos ] >= i - a[ i ] > s[ pos + 1 ] >= ... >= s[ n ]

根據上面的第二個結論，只需要將 s[ 1 ] ~ s[ pos ] 區間加一即可，至于尋找 pos 位置的過程，因為 s 數組滿足單調性，故可以用二分去快速找到，說到這里，區間修改和單點查詢，可以借助線段樹來維護 s 數組的迭代，外層再套一層循環用來迭代右端點 r 即可，時間復雜度為 nlogn^2，需要先將所有的詢問離線然后進行上述操作，最后統一輸出即可

有點細節就是，為了方便處理，我將 i - a[ i ] < 0 的部分設置為了無窮大，可以少一些特判

2020.9.8更新：

昨晚上 rsb 學長提供了一種非常優秀的思路，可以將時間復雜度降低到 nlogn ，具體就是說，對于每個 i - a[ i ] 來說，如果 i - a[ i ] < 0 顯然是永遠無法刪除的，不會對答案造成貢獻，忽略即可，而對于每個大于等于 0 的 i - a[ i ] 來說，前面必須要刪除掉 i - a[ i ] 個數后才可以將當前位置的數刪掉，所以我們不妨枚舉右端點的 r?- a[ r?]，找到其可行的左區間，也就是其前面必須至少要有 r - a[ r?] 個數才行，找到這個位置記為 l[ r?] 作為其左端點可行的最大位置，其意義就是，如果右端點為 r 時，左端點位于 [ 1 , l[ r ]?] 時，那么 a[ r ] 這個數會對其貢獻加一，位于區間 [ l[ r ] + 1 , n ] 的話就不做貢獻

再說一下確定 r - a[ r ] 后如何找到 l[ r ] ，因為前面需要有 r?- a[ r?] 個數，設當前有 cnt 個數，也就是上文中的 cnt = f( r - 1 )，這樣我們只需要在 f( r - 1 ) 內找到區間中第 r - a[ r ] 大的數即可，注意這里要求的是第?r - a[ r ] 大而不是第 r - a[ r ] 小

同樣用線段樹維護一下就好

代碼：

二分+線段樹

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=3e5+100;int a[N],ans[N];vector<pair<int,int>>q[N];struct Node {int l,r,len;LL sum,lazy; }tree[N<<2];void pushup(int k) {tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }void pushdown(int k) {if(tree[k].lazy){LL lz=tree[k].lazy;tree[k].lazy=0;tree[k<<1].sum+=tree[k<<1].len*lz;tree[k<<1|1].sum+=tree[k<<1|1].len*lz;tree[k<<1].lazy+=lz;tree[k<<1|1].lazy+=lz;} }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].len=r-l+1;tree[k].sum=tree[k].lazy=0;if(l==r)return;int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void update(int k,int l,int r) {if(l>r)return;if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].sum+=tree[k].len;tree[k].lazy++;return;}pushdown(k);update(k<<1,l,r);update(k<<1|1,l,r);pushup(k); }LL query(int k,int pos) {if(tree[k].l==tree[k].r)return tree[k].sum;pushdown(k);int mid=tree[k].l+tree[k].r>>1;if(pos<=mid)return query(k<<1,pos);elsereturn query(k<<1|1,pos); }int get_pos(int i) {int l=1,r=i,ans=-1;while(l<=r){int mid=l+r>>1;if(query(1,mid)>=a[i]){ans=mid;l=mid+1;}elser=mid-1;}return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",a+i);a[i]=i-a[i];if(a[i]<0)a[i]=inf;}for(int i=1;i<=m;i++){int l,r;scanf("%d%d",&l,&r);l++;r=n-r;q[r].emplace_back(l,i);}build(1,1,n);for(int i=1;i<=n;i++)//枚舉右端點然后迭代{int pos=get_pos(i);//找到最大的l滿足s[pos]>=a[i]update(1,1,pos);for(int j=0;j<q[i].size();j++)ans[q[i][j].second]=query(1,q[i][j].first);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0; }

線段樹

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=3e5+100;int a[N],ans[N];vector<pair<int,int>>pos[N];struct Node {int l,r;int sum; }tree[N<<2];void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].sum=0;if(l==r)return;int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r); }void update(int k,int pos) {if(tree[k].l==tree[k].r){tree[k].sum++;return;}int mid=tree[k].l+tree[k].r>>1;if(pos<=mid)update(k<<1,pos);elseupdate(k<<1|1,pos);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }int query_k(int k,int x)//區間第x大 {if(tree[k].l==tree[k].r)return tree[k].l;if(tree[k<<1|1].sum>=x)return query_k(k<<1|1,x);elsereturn query_k(k<<1,x-tree[k<<1|1].sum); }int query(int k,int l,int r)//區間和 {if(tree[k].l>r||tree[k].r<l)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].sum;return query(k<<1,l,r)+query(k<<1|1,l,r); }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",a+i);a[i]=i-a[i];if(a[i]<0)a[i]=inf;}for(int i=1;i<=m;i++){int l,r;scanf("%d%d",&l,&r);l++;r=n-r;pos[r].emplace_back(l,i);}build(1,1,n);int num=0;for(int i=1;i<=n;i++){if(a[i]==0){update(1,i);num++;}else if(num>=a[i]){update(1,query_k(1,a[i]));num++;}for(pair<int,int>t:pos[i])ans[t.second]=query(1,t.first,n);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1405E Fixed Point Removal(线段树+思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

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