CF-1207F

分块题 可以说是原题了

哈希冲突
分块 按模数分块 超过 s q r t （ n ） sqrt（n） sqrt（n） 的暴力找 小于的 我们也在 n ∗ s q r t ( n ) n*sqrt(n) n∗sqrt(n) 预处理了
之后单点修改 也是sqrt(n)的复杂度

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0);
//#define int long long
using namespace std;
typedef long long ll;
const int maxn = 1000 + 10;
const int mod = 998244353;

int n, m;
int ans[maxn][maxn];
int a[(signed(2e5 + 10))];

signed main() {
// fastio;
	scanf("%d %d", &n, &m);
	int siz = sqrt(n);
	for(int i = 1; i <= n; i ++) {
		scanf("%d", a + i);
		for(int j = 1; j <= siz; j ++) ans[j][i % j] += a[i];
	}
	while(m --) {
		char op[3];
		int x, y;
		scanf("%s %d %d", op, &x, &y);
		if(op[0] == 'A') {
			if(x * x <= n) printf("%d\n",ans[x][y]);
			else {
				int res = 0;
				for(int i = y; i <= n; i += x) res += a[i];
				printf("%d\n", res);
			}
		} else {
			for(int i = 1; i <= siz; i ++) 
				ans[i][x % i] += y - a[x];
			a[x] = y;
		}
	}

	return 0;
}

CF-1207F

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0);
//#define int long long
using namespace std;
typedef long long ll;
const int maxn = 1000 + 10;
const int N = 5e5 + 5;
const int mod = 998244353;
 
int n, m;
ll ans[maxn][maxn];
int a[N];
 
signed main() {
// fastio;
	scanf("%d", &m);
	int siz = 710;
	while(m --) {
		int op, x, y;
		scanf("%d %d %d", &op, &x, &y);
		if(op == 2) {
			if(x <= siz) printf("%lld\n",ans[x][y]);
			else {
				ll res = 0;
				for(int i = y; i < N ; i += x) res += a[i];
				printf("%lld\n", res);
			}
		} else {
			for(int i = 1; i <= siz; i ++) 
				ans[i][x % i] += y;
			a[x] += y;
		}
	}
	return 0;
}

莫队

小B的询问
按询问排序之后 算是一般意义上的暴力了

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 50000 + 10;
const int mod = 998244353;

int n, m;
struct node {
	int l, r, id, d;
	bool operator < (const node &x) const {
		return id < x.id || (id == x.id && r < x.r);
	}
} a[maxn];
int b[maxn], t[maxn], ans[maxn];

signed main() {
	fastio;
	int n, m, k;
	cin >> n >> m >> k;
	int len = sqrt(n);
	for(int i = 1; i <= n; i ++) cin >> b[i];
	for(int i = 1; i <= m; i ++) {
		cin >> a[i].l >> a[i].r;
		a[i].id = (a[i].l + len - 1) / len;
		a[i].d = i;
	}
	sort(a + 1, a + 1 + m);
	int l = a[1].l, r = a[1].l - 1;
	ll tmp = 0;
	for(int i = 1; i <= m; i ++) {
		while(l > a[i].l) l--, tmp += 2 * t[b[l]] + 1, t[b[l]]++;
		while(r < a[i].r) r++, tmp += 2 * t[b[r]] + 1, t[b[r]]++;
		while(l < a[i].l) t[b[l]]--, tmp -= 2 * t[b[l]] + 1,  l++;
		while(r > a[i].r) t[b[r]]--, tmp -= 2 * t[b[r]] + 1,  r--;
		ans[a[i].d]=tmp;
	}
	for(int i = 1; i <= m; i ++)
		cout << ans[i] << endl;
	return 0;
}

P1494 [国家集训队]小Z的袜子

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
#define int long long
typedef long long ll;
const int maxn = 100005;

struct node {
    int l, r, id;
    int len;
}qes[maxn];

int n, m, k, a[maxn], ans[maxn], sum, s[maxn], pos[maxn];
int l = 1, r, siz;
int l1[maxn], r1[maxn];

bool cmp(const node &a, const node &b) {
    if(pos[a.l] < pos[b.l]) return 1;
    if(pos[a.l] > pos[b.l]) return 0;
    return a.r > b.r;
}

signed main(){
   // fastio;
    cin >> n >> m;
    siz = sqrt(n);
    for(int i = 1; i <= n; i ++)
        cin >> a[i], pos[i] = (i - 1)/siz + 1;
    for(int i = 1; i <= m; i ++)
        cin >> qes[i].l >> qes[i].r, qes[i].id = i, \
        l1[i] = qes[i].l, r1[i] = qes[i].r;
    sort(qes + 1, qes + 1 + m, cmp);
    for(int i = 1; i <= m; i ++) {
        while(l < qes[i].l) {
            sum -= s[a[l]] * (s[a[l]] - 1) / 2;
            s[a[l]]--, sum += s[a[l]] * (s[a[l]] - 1) / 2;
            l ++;
        }
        while(l > qes[i].l) {
            l --;
            sum -= s[a[l]] * (s[a[l]] - 1) / 2;
            s[a[l]]++, sum += s[a[l]] * (s[a[l]] - 1) / 2;
        }
        while(r < qes[i].r) {
            r ++;
            sum -= s[a[r]] * (s[a[r]] - 1) / 2;
            s[a[r]]++, sum += s[a[r]] * (s[a[r]] - 1) / 2;
        }
        while(r > qes[i].r) {
            sum -= s[a[r]] * (s[a[r]] - 1) / 2;
            s[a[r]]--, sum += s[a[r]] * (s[a[r]] - 1) / 2;
            r --;
        }
        ans[qes[i].id] = sum;
    }
    for(int i = 1, x; i <= m; i ++) {
        x = __gcd(ans[i], (r1[i] - l1[i] + 1) * (r1[i] - l1[i]) / 2);
        if(l1[i] == r1[i]) printf("0/1\n");
        else printf("%lld/%lld\n",ans[i]/x, (r1[i] - l1[i] + 1) * (r1[i] - l1[i]) / 2 / x);
    }
    return 0;
}