当前位置：首页 > article >正文

Remainder Problem CF1207F

article 2025/2/27 20:34:24

题目：题目链接

题目大意

题目描述

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

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

输入格式

第一行一个整数 q ，表示操作数。(q⩽500000)
接下来 q 行，每行三个整数 t,x,y 表示一次操作。(t∈{1,2})
若 t=1 则为第一种操作，保证：
1⩽x⩽500000,−1000⩽y⩽1000
若 t=2 则为第二种操作，保证：
1⩽x⩽500000,0⩽y<x
数据保证至少有一个操作 2 。

输出格式

每行对于每个操作 2 输出一个整数表示答案。

测试样例

输入样例

输出样例

4
4
0

题目分析

分析

这个题我们可以进行的两个操作分别是单点修改和区间符合条件的数的求和。其中单点修改不用多说，我们也不用像区间修改那样去优化，我们主要要优化的是区间求和的过程。

对遍历的优化

首先我们如果一个一个遍历去求每个数对x的余数，然后与y比较，再将符合条件的加起来的话，这个过程的复杂度是O(500000)，但是结合到有最多500000次查询，那么复杂度便来到 $O(500000*500000)$ 这样必定会超时。我们可以采用另一种方式，i从y开始遍历，每次让i+=x，这样便能够只访问那些满足条件的元素，节省下大量的时间。

对x值较小的求和的优化

但是向上面这样优化之后还是会超时，我们仔细观察之后会发现，上述操作虽然能够少访问大量的元素，但若是x等于1、2、3之类的较小的数，我们遍历一次要访问的元素量仍然是非常大的。因此，我们不妨开多个数组，在执行操作1时便将一些数求和的结果记录下来（如让a[2][1]记录除以2余1的项的和）。这样我们在查询这些数的和的时候便能够将时间复杂度从近O(500000）降到O(1)。

那么我们要记录多少呢，假设我们从1记录到a了，那么我们在执行操作1的时间复杂度便可以看作O(a*500000)，执行操作2的便可以看作O(500000*500000/(a+1))，均指最坏情况。显然，这两个复杂度都不能够超时。我们再结合一下题中数字规模和限时4000ms，就能够推出 $O(n*\sqrt{n})$ 的复杂度是最合适的，即我们的数组要记录从1到 $\sqrt{500000}$ 的各个余数的和。由于题中时间4000ms较为充裕，我们可以将数组规模从根号n提升到800甚至1000，都不会超时。

PS：这个题数据卡的比较松，其实记录到5或者10之类的就能过，不用到根号n。

代码

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

int q,x,y,p,MAXX=INT_MIN;
int x1[1001][1001]={{0}};//记录各余数情况的总和
int a[500005]={0};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>q;
    while(q--) {
        cin>>p>>x>>y;
        if (p==1) {
            MAXX=max(MAXX,x);
            a[x]+=y;
            for (int i=1;i<=1000;i++) {
                x1[i][x%i]+=y;//记录每个余数的情况
            }
        }
        else {
            if (x<=1000) {
                cout<<x1[x][y]<<'\n';//若有记录直接输出
            }
            else {
                int sum=0;
                for (int i=y;i<=MAXX;i+=x) {//遍历所有除以x余y的情况求和
                    sum+=a[i];
                }
                cout<<sum<<"\n";
            }
        }
    }
}

查看全文

http://www.kler.cn/a/563599.html