华华开始学信息学（思维 + 分块 + 树状数组）

题目链接

不会…好妙的思维啊，之前没写过这种的，分块一生之敌！！！

分析

参考题解

（讲的很清楚了！）

这里分完块后，r/i表示的就是[1,r]中i的倍数的个数；

(r/i - (l-1)/i)表示[l,r]中i的倍数的个数；

代码

ll lazy[maxn];
ll tr[maxn];
int n,m;

void update(int x,int v)
{
	while(x <= n)
	{
		tr[x] += v;
		x += lowbit(x);
	}
}

ll query(int x)
{
	ll ans = 0;
	while(x)
	{
		ans += tr[x];
		x -= lowbit(x);
	}
	return ans;
}

int main()
{
	iire(n,m);
	
	int bl = sqrt(n);
	
	while(m--)
	{
		int op,x,y;
		
		ire(op);
		iire(x,y);
		
		if(op == 1)
		{
			if(x <= bl) lazy[x] += y;
			else
			{
				for(int i=x;i<=n;i+=x) update(i,y);
			}
		}
		else
		{
			ll ans = query(y) - query(x-1);
			
			for(int i=1;i<=bl;i++)
				ans += ((y/i - (x-1)/i) * lazy[i]);
			
			cout<<ans<<endl;
		}
	}
	
	return 0;
}