Wannafly Camp 2020 Day 1I K小数查询

给你一个长度为\(n\)序列\(A\)，有\(m\)个操作，操作分为两种：

输入\(x,y,c\)，表示对\(i\in[x,y]\)，令\(A_{i}=min(A_{i},c)\)
输入\(x,y,k\)，表示询问区间 \([x,y]\) 中的第\(k\)小数

Solution

考虑分块，块内排序，同时记录这一块被整体取过的 \(min\) 的最小值

对于修改，对不完整的块，我们直接暴力在原序列上修改然后重建块，标记不动

对完整的块，只修改标记

这样修改的时间复杂度为 \(O(k \log k)\)，其中 \(k\) 为块大小

对于询问，我们二分答案，考虑检验，在每个完整的块上统计需要检查标记，如果标记比当前枚举的值小则直接计数，否则在块上再次二分；对于不完整的块，检查标记并在序列上暴力查询即可。查询时间复杂度的宽界为 \(O(\frac{n}{k} \log k \log V)\)

求解根号平衡，\(k = \frac{n}{k} \log V\)，得 \(k = \sqrt{n \log V}\)，考虑到 \(V \leq 10^9\)，取 \(k=\sqrt{30n}\) ，实际上由于常数问题，\(k\)取 \(\sqrt{3n}\) 即可

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

const int inf = 1e+9+7;

vector <int> b[N];

int n, m, a[N*N], bel[N*N], bl[N], br[N], tag[N], K, tot;

void build() {

    K = sqrt(3*n);

    for(int i=1;i<=n;i++) bel[i] = i/K+1;

    for(int i=1;i<=n;i++) br[bel[i]]=i;

    for(int i=n;i>=1;i--) bl[bel[i]]=i;

    for(int i=1;i<=n;i++) b[bel[i]].push_back(a[i]);

    for(int i=1;i<=n;i++) tot = max(tot,bel[i]);

    for(int i=1;i<=tot;i++) tag[i] = inf;

    for(int i=1;i<=tot;i++) sort(b[i].begin(), b[i].end());

}

void modify_part(int l,int r,int x) {

    int id = bel[l];

    for(int i=l;i<=r;i++) a[i] = min(a[i],x);

    b[id].clear();

    for(int i=bl[id];i<=br[id];i++) b[id].push_back(a[i]);

    sort(b[id].begin(), b[id].end());

}

void modify(int l,int r,int x) {

    for(int i=bel[l]+1;i<bel[r];i++) tag[i] = min(tag[i],x);

    if(bel[l] == bel[r]) { // !!

        modify_part(l, r, x);

    }

    else {

        modify_part(l, br[bel[l]], x);

        modify_part(bl[bel[r]], r, x);

    }

}

int check_part(int l,int r,int x) {

    if(tag[bel[l]]<=x) return r-l+1;

    int ans = 0;

    for(int i=l;i<=r;i++) ans += a[i]<=x?1:0;

    return ans;

}

int check_block(int i,int x) {

    if(tag[i]<=x) return br[i]-bl[i]+1;

    return upper_bound(b[i].begin(),b[i].end(),x) - b[i].begin();

}

int check(int l,int r,int x) {

    int ans = 0;

    for(int i=bel[l]+1;i<bel[r];i++) ans += check_block(i,x);

    if(bel[l]==bel[r]) { // !!

        ans = check_part(l, r, x);

    }

    else {

        ans += check_part(l, br[bel[l]], x);

        ans += check_part(bl[bel[r]], r, x);

    }

    return ans;

}

int query(int ql,int qr,int k) {

    int l=1, r=1e9+1;

    while(l<r) {

        int mid = (l+r)/2;

        if(check(ql,qr,mid) < k) l=mid+1;

        else r=mid;

    }

    return l;

}

int main() {

    ios::sync_with_stdio(false);

    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>a[i];

    build();

    for(int i=1;i<=m;i++) {

        int t1,t2,t3,t4;

        cin>>t1>>t2>>t3>>t4;

        if(t1==1) {

            modify(t2,t3,t4);

        }

        if(t1==2) {

            cout<<query(t2,t3,t4)<<endl;

        }

    }

}

巴特西

Wannafly Camp 2020 Day 1I K小数查询 - 分块

Solution

最新文章

热门文章