分块1

#include<bits/stdc++.h>
using namespace std;
#define int long long

// 每个块的大小
int B = 300;

// 分块的基本思想：
// 将长度为 n 的数组划分成若干个块，每个块大约有 B 个元素
//
// 例如 B = 3，n = 10：
// 第1块：[1, 2, 3]
// 第2块：[4, 5, 6]
// 第3块：[7, 8, 9]
// 第4块：[10]
//
// 对于每一个位置 x：
// 1. 可以计算 x 属于第几个块
// 2. 可以计算 x 是这个块中的第几个元素
//
// 对于每一个块：
// 1. 可以计算这个块的起点和终点
// 2. 可以维护整个块的信息

// 获取位置 x 所属的块编号
int get_block(int x){
    return (x - 1) / B + 1;
}

// 获取位置 x 在当前块中的下标
// 例如 B = 3，x = 5
// 位置5属于第2块，是第2块中的第2个元素
int get_index(int x){
    return (x - 1) % B + 1;
}

signed main(){
    int n;
    cin >> n;

    // arr[i]：原数组中第 i 个位置的值
    // 注意：这里只保存零散修改产生的变化
    // 整块修改的变化记录在 block_info 中
    vector<int> arr(n + 1 , 0);

    for(int i = 1 ; i <= n ; i ++){
        cin >> arr[i];
    }

    // 选择合适的块大小
    // 本题单次操作的时间复杂度约为 O(n/B + 2B)
    // 当 n/B = 2B 时，理论上可以取得较小的复杂度
    // 因此 B 取 sqrt(n/2) 附近
    B = max(1ll , (long long)sqrt(n / 2.0));

    // block_info[i]：第 i 个块整体增加了多少
    //
    // 相当于给每个块设置一个懒标记
    // 如果整个块都需要加 c，就不必修改块中的每一个元素
    // 只需要 block_info[i] += c
    //
    // 因此：
    // 第 x 个位置的真实值 =
    // arr[x] + block_info[get_block(x)]
    vector<int> block_info(get_block(n) + 1 , 0);

    // 本题一共有 n 次操作
    for(int i = 1 ; i <= n ; i ++){
        int op;
        cin >> op;

        if(op == 0){
            // 操作0：将区间 [l, r] 中的每个元素加上 c
            int l , r , c;
            cin >> l >> r >> c;

            // 获取左右端点所属的块
            int bl = get_block(l);
            int br = get_block(r);

            if(bl == br){
                // 情况1：l 和 r 在同一个块中
                //
                // 此时区间长度不超过 B
                // 直接暴力修改每个元素即可
                // 时间复杂度：O(B)

                for(int i = l ; i <= r ; i ++){
                    arr[i] += c;
                }
            }
            else{
                // 情况2：l 和 r 不在同一个块中
                //
                // 将 [l, r] 分成三个部分：
                //
                // ① 左边不完整的块
                // ② 中间若干个完整的块
                // ③ 右边不完整的块
                //
                // 不完整的块：暴力修改
                // 完整的块：直接修改 block_info

                // ① 修改中间的完整块
                //
                // 从第 bl+1 块到第 br-1 块
                // 每个完整块只需要修改一次懒标记
                // 不需要遍历块中的所有元素
                //
                // 时间复杂度：O(n/B)
                for(int i = bl + 1 ; i <= br - 1 ; i ++){
                    block_info[i] += c;
                }

                // ② 修改左边不完整的块
                //
                // 左边部分为 [l, bl*B]
                // 这一部分最多有 B 个元素
                //
                // 时间复杂度：O(B)
                for(int i = l ; i <= bl * B ; i ++){
                    arr[i] += c;
                }

                // ③ 修改右边不完整的块
                //
                // 右边部分为 [(br-1)*B+1, r]
                // 这一部分最多有 B 个元素
                //
                // 时间复杂度：O(B)
                for(int i = (br - 1) * B + 1 ; i <= r ; i ++){
                    arr[i] += c;
                }

                // 总时间复杂度：
                // O(n/B + 2B)
                //
                // 其中：
                // n/B：需要修改的完整块数量
                // 2B：左右两个零散块中的元素数量
            }
        }
        else{
            // 操作1：查询位置 r 的真实值
            //
            // 虽然输入了 l、r、c
            // 但本题查询的是 a[r]，所以只使用 r
            int l , r , c;
            cin >> l >> r >> c;

            // arr[r]：位置 r 自身记录的值
            // block_info[get_block(r)]：r 所在块的整体增量
            //
            // 两部分加起来才是当前位置的真实值
            cout << arr[r] + block_info[get_block(r)] << endl;

            // 单点查询时间复杂度：O(1)
        }
    }

    // 整体时间复杂度：
    // 单次区间修改 O(n/B + B)
    // 单次查询 O(1)
    //
    // 当 B = O(sqrt(n)) 时：
    // 单次区间修改 O(sqrt(n))
    // n 次操作最坏 O(n*sqrt(n))
}

分块4

#include<bits/stdc++.h>
using namespace std;
#define int long long

int B = 300;

//---------------分块基本函数-----------------

//获取 x 所属的块
int get_block(int x){
    return (x-1)/B+1;
}

//获取 x 在块内的下标
int get_index(int x){
    return (x-1)%B+1;
}

signed main(){
    int n;
    cin >> n;
    vector<int> arr(n + 1 , 0);
    for(int i = 1 ; i <= n ; i ++){
        cin >> arr[i];
    }

    //---------------初始化分块-----------------

    B = sqrt(2 * n);

    //block_info：每个块的真实总和
    vector<int> block_info(get_block(n) + 1 , 0);

    //block_add：每个块整体增加的值（懒标记）
    vector<int> block_add(get_block(n) + 1 , 0);

    //计算每个块的初始总和
    for(int i = 1 ; i <= n ; i ++){
        int bl = get_block(i);
        block_info[bl] += arr[i];
    }

    //---------------处理操作-----------------

    for(int i = 1 ; i <= n ; i ++){
        int opt , l , r , c;
        cin >> opt >> l >> r >> c;

        if(opt == 0){
            //---------------区间加-----------------

            int bl = get_block(l) , br = get_block(r);

            if(bl == br){
                //同一个块：暴力修改
                for(int i = l ; i <= r ; i ++){
                    arr[i] += c;
                    block_info[bl] += c;
                }
            }
            else{
                //---------------左边残缺块-----------------

                for(int i = l ; i <= bl * B ; i ++){
                    arr[i] += c;
                    block_info[bl] += c;
                }

                //---------------右边残缺块-----------------

                for(int i = (br - 1) * B + 1 ; i <= r ; i ++){
                    arr[i] += c;
                    block_info[br] += c;
                }

                //---------------中间完整块-----------------

                //直接修改懒标记和块内总和
                for(int i = bl + 1 ; i <= br - 1 ; i ++){
                    block_add[i] += c;
                    block_info[i] += c * B;
                }
            }
        }
        else{
            //---------------区间求和-----------------

            int bl = get_block(l) , br = get_block(r);

            if(bl == br){
                //同一个块：暴力求和
                int ans = 0;
                for(int i = l ; i <= r ; i ++){
                    ans += arr[i];
                    ans += block_add[bl];
                }

                //---------------处理取模-----------------

                c++;
                //负数取模可能得到负数
                ans %= c;
                ans += c;
                ans %= c;
                cout << ans << endl;
            }
            else{
                int ans = 0;

                //---------------左边残缺块-----------------

                //真实值 = arr[i] + block_add[bl]
                for(int i = l ; i <= bl * B ; i ++){
                    ans += arr[i];
                    ans += block_add[bl];
                }

                //---------------右边残缺块-----------------

                for(int i = (br - 1) * B + 1 ; i <= r ; i ++){
                    ans += arr[i];
                    ans += block_add[br];
                }

                //---------------中间完整块-----------------

                //直接累加整个块的真实总和
                for(int i = bl + 1 ; i <= br - 1 ; i ++){
                    ans += block_info[i];
                }

                //---------------处理取模-----------------

                c++;
                ans %= c;
                ans += c;
                ans %= c;
                cout << ans << endl;
            }
        }
    }
}

Arc 033 C

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

//cnt[x]：数字 x 出现的次数
int cnt[N];

//每个块的大小
int B = 1000;

//---------------获取所属块-----------------

int get_block(int x){
    return (x - 1) / B + 1;
}

int main() {
    int n;
    cin >> n;

    //---------------初始化分块-----------------

    //将 B 个 cnt 数组元素打包成一块
    //block_info[i]：第 i 块内所有数字的出现次数之和
    vector<int> block_info(get_block(N) + 1 , 0);

    //---------------处理操作-----------------

    for(int i = 1 ; i <= n ; i ++){
        int op;
        cin >> op;

        if(op == 1){
            //---------------插入数字-----------------

            int x;
            cin >> x;

            //数字 x 的出现次数 +1
            cnt[x]++;

            //对应块内的数字总数量 +1
            block_info[get_block(x)]++;
        }
        else{
            //---------------查询并删除第 x 小的数字-----------------

            int x;
            cin >> x;

            //now：当前已经统计的数字数量
            int now = 0;

            //---------------第一步：确定答案所在的块-----------------

            //从左到右枚举每一个块
            for(int j = 1 ; j <= get_block(N) ; j ++){//O(N/B)

                //直接加上整个块内的数字数量
                now += block_info[j];

                if(now >= x){
                    //说明第 x 小的数字就在第 j 块中

                    //撤销第 j 块的贡献
                    //此时 now 表示前 j-1 个块中的数字总数量
                    now -= block_info[j];

                    //---------------第二步：在块内寻找答案-----------------

                    //从第 j 块的起点开始逐个枚举数字
                    for(int k = (j - 1) * B + 1 ; k <= min(N - 1 , j * B) ; k ++){//O(B)

                        //累加数字 k 的出现次数
                        now += cnt[k];

                        if(now >= x){
                            //当前数字 k 就是第 x 小的数字

                            //删除一个数字 k
                            cnt[k]--;

                            //输出答案
                            cout << k << endl;

                            //对应块的数字总数量 -1
                            block_info[j]--;

                            break;
                        }
                    }
                    break;
                }
            }
        }
    }

    //---------------时间复杂度-----------------

    //插入一个数字：O(1)
    //查询并删除第 x 小：O(N/B + B)
    //当 B 取 sqrt(N) 级别时，单次查询为 O(sqrt(N))

    return 0;
}

Abc 219 G

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 10;

//col[i]：第 i 个点当前的颜色
vector<int> col(N);

//原图的邻接表
vector<int> adj[N];

int main() {
    int n , m , q;
    cin >> n >> m >> q;

    //---------------建立原图-----------------

    for(int i = 1 ; i <= m ; i ++){
        int u , v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    //每个点的初始颜色为自己的编号
    for(int i = 1 ; i <= n ; i ++){
        col[i] = i;
    }

    //---------------初始化操作分块-----------------

    //每 B 次操作划分为一块
    //平衡 O((n+m)/B) 和 O(B) 两部分复杂度
    int B = sqrt(n + m);

    //op[i]：第 i 次操作选择的点
    vector<int> op(q + 1 , 0);
    for(int i = 1 ; i <= q ; i ++){
        cin >> op[i];
    }

    //---------------按操作分块处理-----------------

    //总复杂度：O(q/B * (n+m+B*B))
    for(int i = 1 ; i <= q ; i += B){

        //当前处理的操作区间：[i, min(q,i+B-1)]

        //g：当前块内所有关键点的编号
        vector<int> g;

        //act[x]：点 x 是否为当前块的关键点
        vector<int> act(n + 1 , 0);

        //ti[x]：关键点 x 最后一次传播的时间
        vector<int> ti(n + 1 , 0);

        //change[x]：关键点 x 最后一次传播的颜色
        vector<int> change(n + 1 , 0);

        //---------------第一步：找出所有关键点-----------------

        //关键点：当前操作块内被选中进行传播的点
        //一个点可能出现多次，但只需要加入 g 一次
        for(int j = i ; j <= min(q , i + B - 1) ; j ++){//O(B)
            if(act[op[j]] == 0){
                g.push_back(op[j]);
                act[op[j]] = 1;
            }
        }

        //---------------第二步：建立关键点之间的图-----------------

        //small：只保留关键点之间的边
        //因为当前块内只有关键点会主动传播颜色
        //所以关键点之间的颜色变化需要实时维护
        vector<int> small[n + 1];

        for(auto c : g){
            for(auto next : adj[c]){
                if(act[next]){
                    small[c].push_back(next);
                }
            }
        }
        //建图总复杂度：O(m)

        //---------------第三步：模拟关键点之间的传播-----------------

        //当前块最多 B 次操作
        //每个关键点最多连接 B 个关键点
        //总复杂度：O(B*B)
        for(int j = i ; j <= min(q , i + B - 1) ; j ++){

            //记录这次操作发生的时间
            ti[op[j]] = j;

            //记录当前点传播出去的颜色
            change[op[j]] = col[op[j]];

            //立即修改相邻关键点的颜色
            //因为这些点可能在后面的操作中继续传播
            for(auto next : small[op[j]]){
                col[next] = col[op[j]];
            }
        }

        //---------------第四步：统一处理非关键点-----------------

        //非关键点在当前操作块中不会主动传播颜色
        //因此不需要在每次操作时立即修改

        //一个非关键点可能被多个关键点修改
        //最终颜色由最后一次传播决定

        for(int j = 1 ; j <= n ; j ++){//O(n+m){
            if(!act[j]){

                //last：最后一次影响点 j 的操作时间
                int last = 0;

                //枚举点 j 的所有邻居
                for(auto next : adj[j]){
                    if(act[next]){

                        //只有关键点才可能在当前块内传播
                        //找到最后一次向 j 传播的关键点
                        if(ti[next] > last){
                            last = ti[next];

                            //使用该次传播时记录的颜色
                            col[j] = change[next];
                        }
                    }
                }
            }
        }
    }

    //---------------输出最终颜色-----------------

    for(int i = 1 ; i <= n ; i ++){
        cout << col[i] << " ";
    }

    return 0;
}

Abc 219 G

#include <bits/stdc++.h>
using namespace std;

// ABC219 G - Propagation
// 根号分治：按照点的度数划分轻点和重点
//
// 轻点：邻居较少，直接暴力传播颜色
// 重点：邻居较多，不直接传播，而是记录懒标记
//
// 时间复杂度：O(n + m + q * sqrt(m + 1))
// 空间复杂度：O(n + m)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    //---------------建立原图-----------------

    //g[u]：点 u 的所有邻居
    //heavy[u]：点 u 的所有重点邻居
    vector<vector<int>> g(n + 1), heavy(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    //---------------根号分治：划分轻点和重点-----------------

    //B：度数的分界线
    //度数 < B：轻点
    //度数 >= B：重点
    int B = max(1, (int)ceil(sqrt(2.0 * m)));

    //isHeavy[u]：判断点 u 是否为重点
    vector<bool> isHeavy(n + 1);

    for (int u = 1; u <= n; ++u) {
        isHeavy[u] = (int)g[u].size() >= B;
    }

    //---------------预处理每个点的重点邻居-----------------

    //因为所有点的度数之和为 2m
    //每个重点的度数至少为 B
    //因此重点的数量最多为 2m/B
    //
    //所以一个点的重点邻居数量也是 O(m/B)

    for (int u = 1; u <= n; ++u) {
        for (int v : g[u]) {
            if (isHeavy[v]) {
                heavy[u].push_back(v);
            }
        }
    }

    //---------------初始化颜色和时间戳-----------------

    //val[u]：点 u 当前记录的颜色
    //tim[u]：点 u 当前颜色最后一次被修改的时间

    vector<int> val(n + 1), tim(n + 1, 0);

    //tag[u]：重点 u 最后一次传播出去的颜色
    //tagTime[u]：重点 u 最后一次传播的时间

    vector<int> tag(n + 1), tagTime(n + 1, 0);

    //初始时，每个点的颜色等于自己的编号
    iota(val.begin(), val.end(), 0);

    //---------------查询点的真实颜色-----------------

    //重点传播颜色时，并不会直接修改邻居
    //因此 val[u] 不一定是点 u 的真实颜色
    //
    //需要检查 u 的所有重点邻居
    //找到最后一次影响 u 的传播操作

    auto pull = [&](int u) {

        //只需要检查重点邻居
        //轻点的传播已经直接修改了 val[u]
        for (int h : heavy[u]) {

            //如果重点 h 的传播时间更新
            //说明它的颜色应该覆盖 u 当前的颜色
            if (tagTime[h] > tim[u]) {
                tim[u] = tagTime[h];
                val[u] = tag[h];
            }
        }

        //最终保留时间戳最大的颜色
        //复杂度：O(m/B)
    };

    //---------------处理每一次传播操作-----------------

    for (int t = 1; t <= q; ++t) {
        int x;
        cin >> x;

        //先获取点 x 当前的真实颜色
        //因为 x 可能被周围的重点修改过
        pull(x);

        //记录本次需要传播出去的颜色
        int value = val[x];

        if (isHeavy[x]) {

            //---------------重点传播：打懒标记-----------------

            //重点邻居太多，不直接修改
            //只记录本次传播的颜色和时间

            tag[x] = value;
            tagTime[x] = t;

            //注意：保存的是传播当时的颜色
            //即使 x 以后变色，也不会影响之前的传播

            //复杂度：O(1)
        }
        else {

            //---------------轻点传播：暴力修改-----------------

            //轻点的度数 < B
            //可以直接修改所有邻居

            for (int y : g[x]) {
                val[y] = value;
                tim[y] = t;
            }

            //复杂度：O(B)
        }
    }

    //---------------统一处理剩余懒标记-----------------

    //有些点可能受到重点传播的影响
    //但是一直没有执行 pull
    //
    //因此最后需要更新所有点的真实颜色

    for (int u = 1; u <= n; ++u) {
        pull(u);
        cout << val[u] << (u == n ? '\n' : ' ');
    }

    //---------------时间复杂度-----------------

    //建图和预处理：O(n + m)
    //
    //单次操作：
    //pull(x)：O(m/B)
    //轻点传播：O(B)
    //重点传播：O(1)
    //
    //单次操作：O(m/B + B)
    //
    //取 B = O(sqrt(m + 1))
    //总复杂度：O(n + m + q * sqrt(m + 1))

    return 0;
}