CF1900F Local Deletions 题解

ckain · 2023-11-29 10:41:02 · 题解

注意到对于一个排列进行 1 或 2 操作之后，其相邻的两个位置至少有一个会被去掉．故进行一次操作后排列长度不超过原来的 1/2，求 f(P) 的过程中最多只能进行 \log_2|P| 次操作．

不妨先将整个排列求一遍 f，并记下每层保留了哪些位置．设 Pos_{i} 表示第 i 层保留下来的位置集合．考虑区间询问 [l,r]，设 Pos'_i 表示询问区间单独求 f 第 i 层保留的位置集合．在第 0 层（没有操作）时，显然有 Pos'_0=[l,r], Pos_0=[1, n]．但到第 1 层时，假如有 a_{l-1}<a_l<a_{l+1} 则存在 Pos'_1\in l,Pos\notin l．但这种情况只会在端点处发生．故在第 i 层记录 l,r,lp,rp 表示 Pos'_i 可以描述为 (Pos_i\cap [l,r])\cup\{lp,rp\}．然后我们按层数从下往上讨论即可．

时间复杂度为 O(n+q\log^2n)，空间复杂度为 O(n)．

code:

#include<bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
using namespace std;

inline int rd(){
    int s=0, f=1; char c=getchar();
    while(!isdigit(c)) f^=(c=='-'), c=getchar();
    while(isdigit(c)) s=s*10+c-'0', c=getchar();
    return f? s:-s;
}

void wt(int x, char c=0){
    if(x<0) return putchar('-'), wt(-x, c);
    if(x>9) wt(x/10); putchar(x%10+'0');
    if(c) putchar(c);
}

const int N=1e5+5;

int n, q, a[N], dep;
vector<int> id[31];

inline int calc(int l, int r){
    int lp=-1, rp=-1;

    auto c=[=](vector<int> v, bool col)->int{
        while(v.size()>1){
            vector<int> tmp;
            for(int i=0; i<v.size(); i++) if((i==0 || (v[i]<v[i-1])^col) && (i==v.size()-1 || (v[i]<v[i+1])^col))
                tmp.push_back(v[i]);
            swap(tmp, v), col^=1;
        }
        return *v.begin();
    };

#define Lower(x, y) lower_bound(x.begin(), x.end(), (y))
#define Upper(x, y) upper_bound(x.begin(), x.end(), (y))
#define Exist(x, y) (Lower(x, y)!=Lower(x, y+1))

    for(int i=0; i<=dep; i++){
        int x=Lower(id[i], l)-id[i].begin(), y=Upper(id[i], r)-1-id[i].begin(), xp, yp;
        if(y-x+1<=1){
            vector<int> las;
            if(~lp) las.push_back(a[lp]);
            if(y>=x) las.push_back(a[id[i][x]]);
            if(~rp) las.push_back(a[rp]);
            return c(las, i&1);
        }
        xp=id[i][x];
        yp=id[i][y];
        if(~lp){
            if((i&1) && a[lp]>a[xp] || (i&1^1) && a[lp]<a[xp]) l=xp+1;
            else{
                lp=-1;
                goto nxtL;
            }
        }
        else{
            nxtL:;
            if(!Exist(id[i+1], xp) && (a[xp]<a[id[i][x+1]])^(i&1)) lp=xp, l=xp+1;
        }
        if(~rp){
            if((i&1) && a[rp]>a[yp] || (i&1^1) && a[rp]<a[yp]) r=yp-1;
            else{
                rp=-1;
                goto nxtR;
            }
        }
        else{
            nxtR:;
            if(!Exist(id[i+1], yp) && (a[yp]<a[id[i][y-1]])^(i&1)) rp=yp, r=yp-1;
        }
    }
}

signed main(){
    n=rd(), q=rd();
    for(int i=1; i<=n; i++) a[i]=rd();

    id[0].resize(n);
    for(int i=0; i<n; i++) id[0][i]=i+1;
    while(id[dep].size()>1){
        for(int i=0; i<id[dep].size(); i++){
            if((!i || (a[id[dep][i]]<a[id[dep][i-1]])^(dep&1)) && (i==(int)id[dep].size()-1 || (a[id[dep][i]]<a[id[dep][i+1]])^(dep&1)))
                id[dep+1].push_back(id[dep][i]);
        }
        dep++;
    }

    for(int i=1; i<=q; i++){
        int l=rd(), r=rd();
        wt(calc(l, r), '\n');
    }
    return 0;
}