#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;vector<ll>G[500000+10];lln,m,root;llf[500000+10][20],dep[500000+10],lg[500000+10];voiddfs(llu,llfa){ f[u][0]=fa; dep[u]=dep[fa]+1; for(lli=1;dep[u]-(1<<i)>

Problem-F-Codeforces 题意：一个500000长度的数列，一开始都是0，进行q次操作，操作如下1，输入x,y，令a[x]+=y。2，输入x,y，输出对于sum(a[idx])，idx的条件是idx=x%y。做法：如果我们模拟做，那么第一种操作就是o(1)，第二种操作就是o(n)。我们换种想法，建立一个二维数组b[x][y]，表

卡死人了。数据随机写在上面，就是让你预估一下区间长度不会太长的，数据里最长的不超过\(2000\)。暴力扫\(2000\)个显然过不了\(500000\)的点，但是\(500000\)的点\(m\)为\(1\)且必定询问整个序列。可以分析出，在随机情况下，前缀和最小最大数量是根号个的，平方后是四次根号级