CF 1405E Fixed Point Removal

CF 1405E Fixed Point Removal

Meaning:

Given the sequence \ (A \) with length \ (n \), the number of \ (A_i = i \) (i.e. the value is equal to its subscript) can be deleted in each operation, and then the remaining arrays are spliced together to ask how many can be deleted at most

\(q \) independent inquiries. Set the number of the first \ (x \) and the number of the last \ (y \) to \ (n+1 \) each time to solve the above problems

Solution:

Do not consider setting the number of first \ (x \) and last \ (y \) to \ (n+1 \)

First of all, we can think of subtracting the subscript from the value of all numbers and defining \ (B_i = A_i - i \), so the position of \ (B_i=0 \) can be deleted from the beginning. After deleting the \ (I \) number, the subscript of the previous number does not change, and the subscript of the subsequent number is reduced by \ (1 \), that is, for all \ (J > I \), the \ (B_j \) becomes \ (B_j+1 \), and there may be a new \ (B_j=0 \)

According to the above facts, these values of \ (b_i > 0 \) can never be deleted at the beginning. In order to delete the largest number, always select the value of the rightmost \ (B_i=0 \) to delete each time (if there is a subscript \ (i,j \) and \ (I < J, b_i = b_j = 0 \), if you delete \ (I \), then \ (J \) cannot be deleted)

Now there is a corollary: for a certain position \ (I \), if \ (B_i < = 0 \), at least the number of \ (- B_i \) before it can be deleted, and this number can also be deleted

Then for each position \ (I \), if \ (B_i\le0 \) is satisfied, there is a left boundary \ (l \). As long as the \ (l \) element can be deleted, the \ (I \) element can also be deleted

If the left boundary \ (L \) needs to meet the requirement that only the elements in the \ ([l,i) \) interval are considered, more than or equal to \ (- B_i \) elements can be deleted. If \ (B_i=0 \) is obviously \ (l=i \)

Then, for each \ (i \) with a left boundary, add \ (1 \) to the position of \ (l \), and the value of each position indicates how many numbers can be deleted when this point is the left boundary. The method of finding \ (l \) can calculate the sum of intervals after bisection, or bisection directly on the line segment tree. The complexity of the former \ (O(\log^2n) \) and the complexity of the latter \ (O(\log n) \)

Consider sorting the queries from small to large according to the right boundary (i.e. \ (Y \) from large to small), traversing each query, updating it to the position of \ (i=n-y \), and then calculating the interval sum of \ ([x+1,n-y] \)

Sorting is to prevent currently illegal points from contributing to the left boundary

view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "\n"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define scs(s) scanf("%s",s)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x)  cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 3e5+7;
int n, q, A[MAXN];
pair<pii,int> Q[MAXN];
struct SegmentTree{
    int sum[MAXN<<2], l[MAXN<<2], r[MAXN<<2];
    #define ls(rt) rt << 1
    #define rs(rt) rt << 1 | 1
    void build(int L, int R, int rt = 1){
        l[rt] = L; r[rt] = R;
        sum[rt] = 0;
        if(l[rt] + 1 == r[rt]) return;
        int mid = (L + R) >> 1;
        build(L,mid,ls(rt)); build(mid,R,rs(rt));
    }
    void modify(int pos, int x, int rt = 1){
        sum[rt] += x;
        if(l[rt] + 1 == r[rt]) return;
        int mid = (l[rt] + r[rt]) >> 1;
        if(pos<mid) modify(pos,x,ls(rt));
        else modify(pos,x,rs(rt));
    }
    int qsum(int L, int R, int rt = 1){
        if(L>=r[rt] or l[rt]>=R) return 0;
        if(L<=l[rt] and r[rt]<=R) return sum[rt];
        return qsum(L,R,ls(rt)) + qsum(L,R,rs(rt));
    }
    int qpos(int x, int rt = 1){
        if(l[rt] + 1 == r[rt]) return l[rt];
        if(sum[rs(rt)]>=x) return qpos(x,rs(rt));
        else return qpos(x-sum[rs(rt)],ls(rt));
    }
}ST;
int ret[MAXN];
void solve(){
    sci(n); sci(q);
    for(int i = 1; i <= n; i++) sci(A[i]), A[i] -= i;
    for(int i = 1; i <= q; i++){
        sci(Q[i].first.first); sci(Q[i].first.second);
        Q[i].second = i;
    }
    sort(Q+1,Q+1+q,[&](pair<pii,int> &a, pair<pii,int> &b){ return a.first.second > b.first.second; });
    int cur = 1, tot = 0;
    ST.build(0,n+1);
    for(int i = 1; i <= q; i++){
        while(cur<=n-Q[i].first.second){
            if(A[cur]==0) ST.modify(cur,1), tot++;
            else if(A[cur]<0 and -A[cur]<=tot) ST.modify(ST.qpos(-A[cur]),1), tot++;
            cur++;
        }
        ret[Q[i].second] = ST.qsum(Q[i].first.first+1,cur);
    }
    for(int i = 1; i <= q; i++) cout << ret[i] << endl;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("Local.in","r",stdin);
    freopen("ans.out","w",stdout);
    #endif
    solve();
    return 0;
}

Tags: data structure Binary Search CodeForces

Posted by bakigkgz on Thu, 19 May 2022 08:38:13 +0300