题意

• 对于长为n的全0序列，完成m次如下两种操作
  1. 输入x y，将所有1-base下标为x的倍数的元素加上y
  2. 输入x y，输出x到y区间和

思路

• 对于操作1，如果暴力做，每次的复杂度会是
• 分析x
  • 如果x很大，那么x的倍数就不会很多，暴力的复杂度是可以接受的
  • 如果x很小，通过数学可以快速得到需要增加的元素的个数，开一个桶，记录每个x被加的y的总和，最后统一计算贡献(这个方法在x大的时候设计开不下数组的问题)
• x的分界定多大
  • 采用上面的方法后，修改的复杂度变为 ，查询的复杂度变为 ，由均值不等式得分界定在 即可

代码

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

int c[202020],flg[1010];
int n,m;

int lowbit(int x){ return x&(-x); }
void add (int x,int val){
    while(x<=n){
        c[x]+=val;
        x+=lowbit(x);
    }
}
int cal(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

signed main(){
    cin >> n >> m ;
    while(lowbit(n)!=n) n+=lowbit(n);

    for(int i=1;i<=m;i++){
        int op,x,y;
        cin >> op >> x >> y;
        if(op==1){
            if(x*x<=n){
                flg[x]+=y;
            }else{
                for(int j=x;j<=n;j+=x){
                    add(j,y);
                }
            }
        }else{
            int ans=cal(y)-cal(x-1);
            for(int j=1;j*j<=n;j++){
                ans+=((y/j)-((x-1)/j))*flg[j];
            }
            cout << ans << endl;
        }
    }
}