您的位置: 首页  >  IT文章  >  牛客小白月赛12 F 华华开始学信息学 （分块+树状数组）

牛客小白月赛12 F 华华开始学信息学 （分块+树状数组）

分类: IT文章 • 2025-01-11 17:21:37

链接：https://ac.nowcoder.com/acm/contest/392/F
来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

因为上次在月月面前丢人了，所以华华决定开始学信息学。十分钟后，他就开始学树状数组了。这是一道树状数组的入门题：
给定一个长度为N的序列A，所有元素初值为0。接下来有M次操作或询问：
操作：输入格式：1 D K，将∑i=LRAi。
华华很快就学会了树状数组并通过了这道题。月月也很喜欢树状数组，于是给华华出了一道进阶题：
给定一个长度为N的序列A，所有元素初值为0。接下来有M次操作或询问：
操作：输入格式：1 D K，对于所有满足∑i=LRAi。
华华是个newbie，怎么可能会这样的题？不过你应该会吧。

输入描述:

第一行两个正整数N、M表示序列的长度和操作询问的总次数。
接下来M行每行三个正整数，表示一个操作或询问。

输出描述:

对于每个询问，输出一个非负整数表示答案。
示例1

输入

复制 
10 6
1 1 1
2 4 6
1 3 2
2 5 7
1 6 10
2 1 10

输出

复制 
3
5
26

备注:

而当遍历到3的倍数时，因为lazy[3]=0所以也会跳过，这样我们便得出了结果。

代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6;
int n,m;
ll sum[maxn],lazy[maxn];
int lowbit(int x){return x&(-x);}
void add(int x,ll val){
    for(int i=x;i<=n;i+=lowbit(i))
        sum[i]+=val;
}
ll ask(int x){
    ll res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=sum[i];
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    int block=sqrt(n);
    while(m--){
        int id,x,y;
        scanf("%d%d%d",&id,&x,&y);
        if(id==1){
            if(x>block)
                for(int i=x;i<=n;i+=x)add(i,y);  //想较大，暴力更新下标为x的倍数的值
            else lazy[x]+=y;  //x值较小，用数组标记x的倍数这个块
        }
        else{
            ll ans=ask(y)-ask(x-1);
            for(int i=1;i<=block;i++)
                if(lazy[i])  //如果这个块有标记值，加上该标记值
                    ans+=(y/i-(x-1)/i)*lazy[i];
            printf("%lld
",ans);
        }
    }
    return 0;
}

相关推荐