Codeforces 1207F Remainder Problem

题目#

题目链接

分析#

以前从来没有做过这种问法的题目，觉得很有意思。

本来想的是可不可以把操作转化一下改到线段树上去，结果没有想到，好像也真的不行。

然后就灵光一闪发现当询问的 $x$ ，比较大的时候暴力查询也是跑的飞快，于是就开始想大数据暴力查询。

小数据可以发现直接维护一个二维数组 $sum[x][y]$ 表示答案。

然后大小的分隔本来以为就是 $sqrt(5 \cdot 10^5)$ ，但其实并不是，因为这道题目并不是传统意义上的分块。

而是一种用空间换时间的方法，当 $x$ 比较大的时候我们很难去更新 $sum[x][y]$ ，也开不了那么大的空间。

思考一下，假如分割点是 $p$ ，那么对于更新操作来说，因为我们需要更新所有的 $sum[x][y]$ 以便查询小数据。

所以更新的复杂度就是： $O(p)$ 。

对于查询操作来说：如果查询的 $x \leq p$ ，那么我们可以直接输出答案也就是 $O(1)$ 。

如果查询的 $x > p$ ，那么我们可以暴力查询，复杂度是： $O(\frac{5\cdot 10^5}{x})$ 。具体复杂度是： $\Omega(\frac{5\cdot 10^5}{p}) - O(1)$ 。

分析一下 $p$ 取 300~1000 都是可以的。

代码#

1
#include <bits/stdc++.h>
2
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
3
#define per(i, a, b) for(int i = (a); i >= (b); --i)
4
using namespace std;
5

6
typedef long long ll;
7
const int mod = 1e9+7;
8
const int MAXN = 5e5 + 7;
9

10
int a[MAXN];
11
int sum[1001][1001];
12
int main(int argc, char const *argv[])
13
{
14
  int q;
15
  scanf("%d", &q);
16
  int op, x, y;
17
  while(q--){
18
    scanf("%d %d %d", &op, &x, &y);
19
    if(op == 1){
20
      a[x] += y;
21
      for(int i = 1; i <= 1000; ++i){
22
        sum[i][x%i] += y;
23
      }
24
    } else {
25
      if(x <= 1000){
26
        printf("%d\n", sum[x][y]);
27
      } else {
28
        int res = 0;
29
        while(y <= 500000){
30
          res += a[y];
31
          y += x;
32
        }
33
        printf("%d\n", res);
34
      }
35
    }
36
  }
37
  return 0;
38
}