C++14(g++5.4) 解法, 执行用时: 966ms, 内存消耗: 2424K, 提交时间: 2019-03-10 00:27:28

#include<bits/stdc++.h>
#define low(x) x&-x
#define ll long long
using namespace std;
const int maxn=1e5+10;
ll c[maxn],a[maxn];
void up(int i,int v,int n)
{
	for(;i<=n;i+=low(i))c[i]+=v;
}
ll qu(int i)
{
	ll res=0;
	for(;i;i-=low(i))res+=c[i];
	return res;
}	
int n,k,x,d,tp,T;
ll gao(int m)
{
	ll res=qu(m);
	int N=min(m,T);
	for(int i=1;i<=N;i++)
	res+=1ll*m/i*a[i];
	return res;
}
int main()
{
	scanf("%d%d",&n,&k);
	T=(int)sqrt(1.0*n*2);
	while(k--)
	{
		scanf("%d%d%d",&tp,&d,&x);
		if(tp==1)
		{
			if(d>=T)
			for(int i=d;i<=n;i+=d)up(i,x,n);
			else a[d]+=x;
		}
		else
		printf("%lld\n",gao(x)-gao(d-1));
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 423ms, 内存消耗: 2360K, 提交时间: 2022-08-05 09:09:26

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int c[N],a[N],n,m;
inline int lowbit(int x)
{
	return x&-x;
}
void add(int x,int y)
{
	for(;x<=n;x+=lowbit(x)) c[x]+=y;
}
int ask(int x)
{
	int ans=0;
	for(;x;x-=lowbit(x)) ans+=c[x];
	return ans;
}
signed main (void)
{
	cin>>n>>m;
	int len=sqrt(n);
	while(m--)
	{
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1)
		{
			if(x<=len) a[x]+=y;
			else for(int i=x;i<=n;i+=x) add(i,y);
		}
		else{
			int ans=ask(y)-ask(x-1);
			for(int i=1;i<=len;i++) ans+=(y/i-(x-1)/i)*a[i];
			cout<<ans<<endl;
		}
	}
}