题解：P12461 [Ynoi Easy Round 2018] 星野爱

Sliarae · 2025-05-10 10:33:13 · 题解

按 1 \sim n 的顺序枚举所有点 i，并将 i 的邻域 R(i) 中的所有点加入到序列 A 的末尾，这样可以构建出一个长度为 2m 的序列 A。

设 i 的邻域位于序列 A 中 [L_i, R_i] 的位置。则题目中先枚举 i \in [l, r]，再枚举 j \in R(i) 的过程，可以看成直接枚举 j \in A_k (k \in [L_l, R_r])，它构成 A 上的一段区间。

于是题意可以转化成：

• 1 l r v：对于 i \in [l, r]，令 w_{A_i} \gets w_{A_i} + v。
• 2 l r：计算 \sum\limits_{i = l}^{r} w_{A_i}。

将序列 A 以 O(\sqrt m) 为块长分块，离线下来考虑修改对查询的贡献，将贡献分为（整块/散块）对（整块/散块）四种情况。

• 散块对散块，直接暴力即可。

• 整块对（整块/散块），离线枚举每个整块算它的修改对询问的贡献，这样只要维护一个全局的标记，遇到一个询问时，求询问区间与这个整块的交的大小，就是这个标记贡献的次数。

• 散块对整块，这个是类似的，还是离线枚举每个整块，在修改散块时求与这个整块的交的大小，然后将贡献累加到标记上，遇到询问时只需将答案加上这个标记。

时间复杂度 O(q \sqrt m)，空间复杂度 O(n + m + q)。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
using uLL = unsigned long long;

const int N = 2e5 + 5;
const int T = N * 2; 
const int S = 1e3;

int n, m, q, M, len, tot;
int u[T], fst[N], lst[N];
vector<int> e[N];
int o[N], l[N], r[N], v[N];
uLL ans[N];
int bl[T], L[S], R[S];

int main () {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    for (int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }  
    for (int i = 1; i <= n; ++i) {
        fst[i] = M + 1;
        for (auto j : e[i]) {
            u[++M] = j; 
        }
        lst[i] = M;
    }
    len = sqrt(M);
    for (int i = 1; i <= M; ++i) {
        bl[i] = (i - 1) / len + 1; 
    }
    tot = bl[M];
    for (int i = 1; i <= tot; ++i) {
        L[i] = R[i - 1] + 1;
        R[i] = min(L[i] + len - 1, M);
    }
    for (int i = 1, tl, tr; i <= q; ++i) {
        cin >> o[i] >> tl >> tr;
        if (o[i] == 1) cin >> v[i]; 
        l[i] = fst[tl], r[i] = lst[tr];
        if (l[i] > r[i]) continue;
        static uLL arr[T];
        auto add = [&](int l, int r, int v) -> void {
            for (int i = l; i <= r; ++i)
                arr[u[i]] += v; 
        }; 
        auto query = [&](int l, int r) -> uLL {
            uLL res = 0; 
            for (int i = l; i <= r; ++i)
                res += arr[u[i]];
            return res;
        }; 
        if (bl[l[i]] == bl[r[i]]) {
            if (o[i] == 1)
                add(l[i], r[i], v[i]);
            else
                ans[i] += query(l[i], r[i]);
        }
        else {
            if (o[i] == 1) {
                add(l[i], R[bl[l[i]]], v[i]);
                add(L[bl[r[i]]], r[i], v[i]);
            }
            else {
                ans[i] += query(l[i], R[bl[l[i]]]);
                ans[i] += query(L[bl[r[i]]], r[i]);
            }
        }
    }
    for (int t = 1; t <= tot; ++t) {
        static int mp[N];
        for (int i = L[t]; i <= R[t]; ++i)
            ++mp[u[i]];
        static int cnt[T];
        for (int i = 1; i <= M; ++i) 
            cnt[i] = cnt[i - 1] + mp[u[i]];
        uLL tag1 = 0; 
        uLL tag2 = 0; 
        auto range_add = [&](int l, int r, int v) -> void {
            tag1 += 1ll * (cnt[r] - cnt[l - 1]) * v;  
        };
        auto block_add = [&](int v) -> void {
            tag2 += v; 
        }; 
        auto range_query = [&](int l, int r) -> uLL {
            return tag2 * (cnt[r] - cnt[l - 1]); 
        };
        auto block_query = [&]() -> uLL {
            return tag1;
        };  
        for (int i = 1; i <= q; ++i) {
            if (l[i] > r[i]) continue;
            if (o[i] == 1) {
                if (bl[l[i]] == bl[r[i]]) {
                    range_add(l[i], r[i], v[i]);
                }
                else {
                    range_add(l[i], R[bl[l[i]]], v[i]);
                    range_add(L[bl[r[i]]], r[i], v[i]);
                    if (l[i] < L[t] && r[i] > R[t])
                        block_add(v[i]);
                }
            }
            else {
                ans[i] += range_query(l[i], r[i]);
                if (l[i] < L[t] && r[i] > R[t]) {
                    ans[i] += block_query();
                }
            }
        }
        for (int i = L[t]; i <= R[t]; ++i)
            --mp[u[i]];
    }
    for (int i = 1; i <= q; ++i)
        if (o[i] == 2)
            cout << ans[i] << '\n';
    return 0; 
}