题解：AT_past202107_l たくさんの最小値

· · 题解

没有分块题解，来交一发。

一道分块板子。

题目中有两种操作，第一种单点修改，第二种区间查询有多少个值为最小值。

我们考虑分块暴力维护区间最小值。

对于单点修改，我们在更改完 a_{x_i} 之后暴力扫一遍 x_i 所在块内，更新块内最小值。

#include<bits/stdc++.h>
#define pb push_back
constexpr int N = 2e5 + 5;
constexpr int INF = 1e9 + 7;

using std :: vector;
using std :: min;
using std :: cerr;

inline int read(){
    char ch = getchar();
    int x = 0;
    bool f = 0;

    while(!isdigit(ch)) f = (ch == '-') , ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48) , ch = getchar();

    return f ? -x : x;
}

inline void write(int x){
    int w[101] , top = 0;

    if(!x) putchar('0');
    if(x < 0) putchar('-') , x = -x;
    while(x)
        w[++top] = x % 10 , x /= 10;
    while(top)
        putchar(w[top] ^ 48) , top --;
    putchar(' ');
}

int n , q , minn[N] , bl[N] , block , a[N] , ans[N];

vector<int > vec[N];//vec 数组维护每个块内值为最小值的 x[i]

inline void Modify(int p , int x){//单点修改
    a[p] = x; vec[bl[p]].clear(); minn[bl[p]] = INF;
    for(int i = (bl[p] - 1) * block + 1;i <= min(n , bl[p] * block);++i){
        if(a[i] < minn[bl[i]]){
            minn[bl[i]] = a[i];
            vec[bl[i]].clear();
            vec[bl[i]].pb(i);
        }

        else if(a[i] == minn[bl[i]]) vec[bl[i]].pb(i);
    }

    return;
}

/*
由于修改可能会影响到块内最小值（例如将最小值更改为更大的数），
所以我们整体扫一遍来更新块内的最小值及为这个值的数的下标。
*/

inline void Query(int l , int r){//区间查询
    int mn = INF , sz = 0;

    for(int i = l;i <= min(r , bl[l] * block);++i) {
        if(a[i] < mn){
            mn = a[i];
            sz = 1;
            ans[1] = i;
        }

        else if(a[i] == mn) ans[++sz] = i;
    }

    if(bl[l] != bl[r]) {
        for(int i = (bl[r] - 1) * block + 1;i <= r;++i){
            if(a[i] < mn){
                mn = a[i];
                sz = 1;
                ans[1] = i;
            }

            else if(a[i] == mn) ans[++sz] = i;
        }
    }

    for(int i = bl[l] + 1;i < bl[r];++i) {
        if(minn[i] < mn){
            mn = minn[i];
            sz = 0;
            for(int j : vec[i]) ans[++sz] = j;
        }

        else if(minn[i] == mn) for(int j : vec[i]) ans[++sz] = j;
    }

    write(sz); std :: sort(ans + 1 , ans + 1 + sz);//要按照递增输出。

    for(int i = 1;i <= sz;++i) write(ans[i]);

    putchar(10);
    return;
}//查询时，遇到更小值就要将 ans 清空，并且更新 mn。

int main(){
    n = read() , q = read();

    block = std :: sqrt(n);

    for(int i = 1;i <= block + 1;++i) minn[i] = INF;

    for(int i = 1;i <= n;++i){
        a[i] = read();
        bl[i] = (i - 1) / block + 1;
        if(a[i] < minn[bl[i]]){
            minn[bl[i]] = a[i];
            vec[bl[i]].clear();
            vec[bl[i]].pb(i);
        }

        else if(a[i] == minn[bl[i]]) vec[bl[i]].pb(i);
    }

    for(int i = 1;i <= q;++i){
        int opt = read();
        if(opt == 1){
            int p = read() , x = read();
            Modify(p , x);
        }
        else {
            int l = read() , r = read();
            Query(l , r);
        }
    }
    return 0;
}

/*
因为输出 j 的总个数不超过 2e5，
询问扫块内是 sqrt(n) 的，
但是答案只会遍历 2e5 次，也就是最多输出 2e5 个。
那么实际总体复杂度是 O(q sqrt(n) + 2e5)
也就是 O(q sqrt(n)) 的
读入输出记得优化
*/

时间复杂度为 O(Q \sqrt{N})。