P12751

前言

建议题目名变成【模板】根号分治。

思路

一眼根号分治。

考虑对于所有 $d_i>\sqrt{n}$，因为总修改点数至多 $\sqrt{n}$，所以暴力修改；

对于所有 $d_i\le \sqrt{n}$，因为 $d_i$ 不同的修改至多 $\sqrt{n}$，所以对于每一种 $d_i$ 差分修改，前缀和合并时跳着合并。

代码

#include<bits/stdc++.h>
using namespace std;
int t[114514][120],ans[114514];
main(){
    int n,m,bl=114;
	cin>>n>>m;
	for(int i=1,a,l,d;i<=m;i++){
		cin>>a>>l>>d;
		if(d>bl)while(l--)ans[a+l*d]++;
		else t[a][d]++,t[a+l*d][d]--;
	}
	for(int d=1;d<=bl;d++){
		for(int i=d;i<=n;i++)t[i][d]+=t[i-d][d];
        for(int i=1;i<=n;i++)ans[i]+=t[i][d];
    }
	for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
	return 0;
}