1.数列分块入门 1

😊 | Powered By HeartFireY | 分块例题 [#6277. 数列分块入门 1 - 题目 - LibreOJ (loj.ac)](https://loj.ac/p/6277)

首先将输入的序列分块，分为 n \sqrt{n} n ​个块，对于区间加的操作，我们对于区间内的元素分类操作：

• 对于区间内的整块，我们单独设置一个块标记；
• 对于区间内的不完整块，我们直接暴力单点加。

每 m m m个元素分为一块，共有 n / m n/m n/m块，每次区间加的操作会涉及 O ( n / m ) O(n/m) O(n/m)个整块，以及区间两侧两个不完整的块中至多 2 m 2m 2m个元素。由于我们取 m = n m = \sqrt{n} m=n ​，因此复杂度 O ( n m ) + O ( m ) = O ( n ) O(\frac{n}{m}) + O(m) = O(\sqrt{n}) O(mn​)+O(m)=O(n ​)。

AC Code

#include 
#define ll long long
#define int long long
using namespace std;

const int N = 5e4 + 10;
int id[N], blo;
ll a[N], tag[N];

void add(int l, int r, int c){
    for(int i = l; i  a[i];
    for(int i = 1; i  op >> l >> r >> v;
        if(op == 0) add(l, r, v);
        if(op == 1) cout