[CF1207F] Remainder Problem - 根号分治

[CF1207F] Remainder Problem - 根号分治

Description

给你一个长度为 \(500000\) 的序列，初值为 \(0\) ，你要完成 \(q\) 次操作，操作有如下两种：

1. 1 x y : 将下标为 \(x\) 的位置的值加上 \(y\)
2. 2 x y : 询问所有下标模 \(x\) 的结果为 \(y\) 的位置的值之和

Solution

根号分治，设 \(b=\sqrt{500000}\)，那么我们对所有 \(r \le b\) 维护 \(sum[r][i]\) 表示下标模 \(r\) 等于 \(i\) 的所有位置的答案和

每次修改时，假设这个位置的新值是 x，那么我们需要对所有 \(r \le b\)，在 \(sum[r][x\%r]\) 的位置修改，同时修改旧位置

询问时，如果 \(x \le b\) 那么直接调出结果，否则暴力查询原始序列

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

#define int long long

const int n = 500000;
const int b = 400;

int sum[b + 2][b + 2];

signed main()
{
    ios::sync_with_stdio(false);

    int q;
    cin >> q;

    vector<int> a(n + 2);

    auto modify = [&](int x, int y) {for(int i=1;i<=b;i++) sum[i][x%i]+=y; };

    for (int i = 1; i <= q; i++)
    {
        int op, x, y;
        cin >> op >> x >> y;

        if (op == 1)
        {
            // a[x]+=y
            modify(x, -a[x]);
            a[x] += y;
            modify(x, a[x]);
        }
        else
        {
            if (x <= b)
            {
                cout << sum[x][y] << endl;
            }
            else
            {
                int ans = 0;
                for (int i = y; i <= n; i += x)
                    ans += a[i];
                cout << ans << endl;
            }
        }
    }
}

[CF1207F] Remainder Problem - 根号分治

原文：https://www.cnblogs.com/mollnn/p/14352372.html