分块入门学习笔记

前言

感觉我还是比较喜欢这种几乎不用怎么动脑的暴力数据结构啊
例题
给出一个长为 $n$ 的序列和 $n$ 次操作。
设计一种数据结构，满足区间加法和区间求和。
$1\le n\le 50000$

分析

一开始也是觉得搞个线段树或者树状数组不就行了吗，后面发现分块还可以搞一些其他的操作可惜蒟蒻现在还不会
进入正题
分块，顾名思义就是把一个序列分成若干块来操作，那么我们要如何做呢。
首先，我们把序列分成若干块，每一块有 n \\sqrt{n} n ​ 个数。
对于每一块，我们维护一个 $lazy$ 和 $sum$ 表示懒标记和区间和。
每次修改时，如果覆盖了某一块，那么直接用懒标记标记一下和区间加和一下，如果不在就一个个加。
查询同上。

code

#include <bits/stdc++.h>
#define LL long long
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
using namespace std;
const int N = 100005;
LL n, n1, a[N];
struct note {LL v, lay;int l, r;
} mark[N];
LL read() {LL val = 0, fu = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-')fu = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {val = val * 10 + (ch - '0');ch = getchar();}return val * fu;
}
void change(LL l, LL r, LL val) {int l1 = l / n1 + 1, r1 = r / n1 + 1;if (l1 == r1) {mark[l1].v += val * (r - l + 1);fu(i, l, r)a[i] += val;} else {fu(i, l1 + 1, r1 - 1)mark[i].v += val * (mark[i].r - mark[i].l + 1), mark[i].lay += val;change(l, mark[l1].r, val);change(mark[r1].l, r, val);}
}
LL query(LL l, LL r, LL val) {LL ans = 0;int l1 = l / n1 + 1, r1 = r / n1 + 1;if (l1 == r1) {if (l == mark[l1].l && r == mark[l1].r)return mark[l1].v;fu(i, l, r)ans = ((ans + a[i]) % val + mark[l1].lay) % val;} else {fu(i, l1 + 1, r1 - 1)ans = (ans + mark[i].v) % val;ans = (ans + query (l , mark[l1].r , val)) % val;ans = (ans + query (mark[r1].l , r , val)) % val;}return ans;
}
int main() {// freopen ("a2.in" , "r" , stdin);// freopen ("a.out" , "w" , stdout);int num;n = read();n1 = sqrt(n);mark[1].l = 1;fu(i, 1, n) {a[i] = read();num = (i / n1 + 1);mark[num].v += a[i];if (i % n1 == 0)mark[num].l = i;mark[num].r = i;}LL opt, l, r, c;fu(i, 1, n) {opt = read(), l = read(), r = read(), c = read();if (!opt)change(l, r, c);elseprintf("%lld\\n", query(l, r, c + 1));}
}