很久没有更新博客了，想着暑假学习点东西。

简介

首先是对分块的简介，分块又叫优雅的暴力，就是将一些暴力容易超时的题，给他简化。
具体的解法就是对一个大区间，将他分成多个小的区间，普遍是的大小的区间 ~~如果是过不了，可以试试会有奇效说不定~~
然后对于每个区间根据题目要求去维护一些东西，这个就需要靠多刷题掌握了。
当我们要查询的时候，就可以直接暴力查询开头和结尾的区间，中间完全包括的区间就可以通过维护的变量直接得出结果。
然后入门题目推荐就是hzwer的数列分块入门九题。

数列分块入门 1

题意

给出一个长为的数列，以及个操作，操作涉及区间加法，单点查值。

思路

首先看到这个区间加法，和单点查值我们能想到什么，暴力遍历区间加，然后O(1)查询，可是复杂度不允许,也太low了，怎么也要搞个线段树吧，但是线段树又太难写了。
这里讲分块的思路，首先将数列分成大小为的多个区间 (最后一个区间不一定是)
然后每个区间维护一个区间加值，当给定区间加法时，我们需要先暴力将头和尾不完整的区间直接加法 复杂度为,然后对于区间完整包括的，直接将加的值加里就行.
查询的话就是直接当前值加上当前值所在的区间的

代码

#include <bits/stdc++.h>
using namespace std;
int num[50005];
int sa[50005];
int n, m;
int k;
int li(int x) { return (x - 1) / k + 1; }
void does(int l, int r, int x) {
    int cl = li(l);
    int cr = li(r);
    if (cr == cl) {
        for (int i = l; i <= r; i++) num[i] += x;
        return;
    }
    for (int i = l; i <= cl * k; i++) num[i] += x;
    for (int i = cl + 1; i < cr; i++) sa[i] += x;
    for (int i = (cr - 1) * k + 1; i <= r; i++) num[i] += x;
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> num[i];
    k = sqrt(n);
    for (int i = 0; i < n; i++) {
        int opt, a, b, c;
        cin >> opt >> a >> b >> c;
        if (opt == 1) {
            cout << num[b] + sa[li(b)] << endl;
        } else {
            does(a, b, c);
        }
    }
    return 0;
}

数列分块入门2

题意

给出一个长为的数列，以及个操作，操作涉及区间加法，询问区间内小于某个值的元素个数。

思路

是上一题的强化版，思路也是一样。
对于区间加法同样维护一个区间sum，区间加法和上题一样，
然后询问区间内小于某个值的个数。
即对于每个划分的区间排序一下二分搞一搞就行。
同开头和结尾不完整的直接暴力就行。
当然这里还有一个问题就是，当对开头结尾暴力加法的时候，也能会使得排序出错，所以需要对区间加法的开头和结尾进行重排。

代码

#include <bits/stdc++.h>
using namespace std;
int num[50005];
vector<int> num1[50005];
int poi[50005];
int sa[50005];
int n, m;
int k;
void reset(int x)  //用来不构成一整块的排序
{
    num1[x].clear();
    for (int i = (x - 1) * k + 1; i <= min(x * k, n); i++) num1[x].push_back(num[i]);
    sort(num1[x].begin(), num1[x].end());
}
void does(int l, int r, int x) {
    int cl = poi[l];
    int cr = poi[r];
    if (cr == cl) {
        for (int i = l; i <= r; i++) num[i] += x;
        reset(cl);
        return;
    }
    for (int i = l; i <= cl * k; i++) num[i] += x;
    reset(cl);
    for (int i = cl + 1; i < cr; i++) sa[i] += x;
    for (int i = (cr - 1) * k + 1; i <= r; i++) num[i] += x;
    reset(cr);
    return;
}
int query(int l, int r, long long x) {
    int cl = poi[l];
    int cr = poi[r];
    int ans = 0;
    if (cr == cl) {
        for (int i = l; i <= r; i++)
            if (num[i] + sa[cr] < x)
                ans++;
        return ans;
    }
    for (int i = l; i <= cl * k; i++)
        if (num[i] + sa[cl] < x)
            ans++;
    for (int i = cl + 1; i < cr; i++)
        ans += lower_bound(num1[i].begin(), num1[i].end(), (long long)x - sa[i]) - num1[i].begin();
    for (int i = (cr - 1) * k + 1; i <= r; i++)
        if (num[i] + sa[cr] < x)
            ans++;
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    k = sqrt(n);
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
        poi[i] = (i - 1) / k + 1;
        num1[poi[i]].push_back(num[i]);
    }
    for (int i = 1; i <= poi[n]; i++) {
        sort(num1[i].begin(), num1[i].end());
    }
    for (int i = 0; i < n; i++) {
        int opt, a, b;
        long long c;
        cin >> opt >> a >> b >> c;
        if (opt == 0) {
            does(a, b, c);
        } else {
            cout << query(a, b, c * c) << endl;
        }
    }
    return 0;
}

数列分块入门3

题意

给出一个长为的数列，以及个操作，操作涉及区间加法，询问区间内小于某个值的前驱。（比其小的最大元素）
同理也是上一题的优化版，同样是区间加法，加上区间排序。
这里只有一个点有所不同，就是在查询的时候去找一个值比小即可。
对于开头结尾不完整的区间，我们就可以暴力找一个前驱，记住要加上区间变量，然后对于完整的区间我们只需要二分直接找前驱，并输出这些前驱中最大的那一个就行。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int a[maxn], sa[maxn], pos[maxn];
vector<int> num[maxn];
int n, m;
int k;
void reset(int x) {
    num[x].clear();
    for (int i = (x - 1) * k + 1; i <= min(x * k, n); i++) num[x].push_back(a[i]);
    sort(num[x].begin(), num[x].end());
    return;
}
void does(int l, int r, int x) {
    int cl = pos[l];
    int cr = pos[r];
    for (int i = l; i <= min(cl * k, r); i++) a[i] += x;
    reset(cl);
    if (cl != cr) {
        for (int i = (cr - 1) * k + 1; i <= r; i++) a[i] += x;
        reset(cr);
    }
    for (int i = cl + 1; i < cr; i++) {
        sa[i] += x;
    }
}
void query(int l, int r, int x) {
    int cl = pos[l];
    int cr = pos[r];
    int ans = -1;
    for (int i = l; i <= min(cl * k, r); i++)
        if (a[i] + sa[cl] < x)
            ans = max(ans, a[i] + sa[cl]);
    if (cl != cr) {
        for (int i = (cr - 1) * k + 1; i <= r; i++)
            if (a[i] + sa[cr] < x)
                ans = max(ans, a[i] + sa[cr]);
    }
    for (int i = cl + 1; i < cr; i++) {
        int t = lower_bound(num[i].begin(), num[i].end(), x - sa[i]) - num[i].begin();
        if (t == 0)
            continue;
        ans = max(ans, num[i][t - 1] + sa[i]);
    }
    cout << ans << endl;
}
int main() {
    cin >> n;
    k = 0.5 * sqrt(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[i] = (i - 1) / k + 1;
        num[pos[i]].push_back(a[i]);
    }
    for (int i = 1; i <= pos[n]; i++) sort(num[i].begin(), num[i].end());
    int opt, l, r, x;
    for (int i = 1; i <= n; i++) {
        cin >> opt >> l >> r >> x;
        if (opt == 0) {
            does(l, r, x);
        } else
            query(l, r, x);
    }
    return 0;
}

数列分块入门 4

题意

给出一个长为的数列，以及个操作，操作涉及区间加法，区间求和(这里还需要取模)。

这里就是第一题的优化版，即对于每个区间维护两个变量，一个数是区间和，一个数区间加。

区间加法的时候，和第一题不同的时候，就是对不完整区间加法时需要将同步改变下区间和。
区级求和的时候，则对不完整区间，加本值和区间加就行，对完整区间，加区间加和区间和就行。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int mod=1e9+7;
const int maxn = 1e5 + 5;
ll a[maxn];
ll sum[maxn], p[maxn];
int n, m;
int k;
void does(int l, int r, int c) {
    int cl = (l - 1) / k + 1;
    int cr = (r - 1) / k + 1;
    for (int i = l; i <= min(cl * k, r); i++) {
        a[i] = a[i] + c;
        sum[cl] = sum[cl] + c;
    }
    if (cl != cr) {
        for (int i = (cr - 1) * k + 1; i <= r; i++) {
            a[i] = a[i] + c;
            sum[cr] = sum[cr] + c;
        }
    }
    for (int i = cl + 1; i < cr; i++) p[i] += c;
}
void query(int l, int r, int x) {
    int cl = (l - 1) / k + 1;
    int cr = (r - 1) / k + 1;
    ll ans = 0;
    int mod = x + 1;
    for (int i = l; i <= min(cl * k, r); i++) {
        ans = (ans + a[i] + p[cl]) % mod;
        ans %= mod;
    }
    if (cl != cr) {
        for (int i = (cr - 1) * k + 1; i <= r; i++) {
            ans = (ans + a[i] + p[cr]) % mod;
            ans %= mod;
        }
    }
    for (int i = cl + 1; i < cr; i++) ans = (ans + p[i] * k % mod + sum[i]) % mod, ans %= mod;
    cout << ans << endl;
}
int main() {
    cin >> n;
    k = sqrt(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[(i - 1) / k + 1] += a[i];
    }
    int opt, l, r, c;
    for (int i = 1; i <= n; i++) {
        cin >> opt >> l >> r >> c;
        if (opt == 0)
            does(l, r, c);
        else
            query(l, r, c);
    }
    return 0;
}

数列分块入门 5

题意

给出一个长为的数列，以及个操作，操作涉及区间开方，区间求和。

这里开始就是进阶的应用了，这题就是不好维护变量了，因为区间开方和求和并没有什么必然的联系，但是这里有一个点可以利用，就是当一个值开方多次后就变成了1。
这样每个元素至多被开方不超过4次，显然复杂度没有问题。
所以我们只需要维护这个区间是否全为1就行，如果不为1就暴力循环开方即可。

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[100005], b[100005], sum[100005];
int n, m;
int k;
void does(int l, int r) {
    int cl = (l - 1) / k + 1;
    int cr = (r - 1) / k + 1;
    for (int i = l; i <= min(cl * k, r); i++) {
        if (a[i] != 1 && sqrt(a[i]) == 1)
            sum[cl]++;
        a[i] = sqrt(a[i]);
        if (a[i] == 1)
            b[i]++;
        if (b[i] == 1)
            sum[cr]++;
    }
    if (cl != cr) {
        for (int i = (cr - 1) * k + 1; i <= r; i++) {
            a[i] = sqrt(a[i]);
            if (a[i] == 1)
                b[i]++;
            if (b[i] == 1)
                sum[cr]++;
        }
    }
    for (int i = cl + 1; i < cr; i++) {
        if (sum[i] == k)
            continue;
        for (int j = (i - 1) * k + 1; j <= i * k; j++) {
            a[j] = sqrt(a[j]);
            if (a[j] == 1)
                b[j]++;
            if (b[j] == 1)
                sum[i]++;
        }
    }
}
void query(int l, int r) {
    int ans = 0;
    int cl = (l - 1) / k + 1;
    int cr = (r - 1) / k + 1;
    for (int i = l; i <= min(cl * k, r); i++) {
        ans += a[i];
    }
    if (cl != cr) {
        for (int i = (cr - 1) * k + 1; i <= r; i++) ans += a[i];
    }
    for (int i = cl + 1; i < cr; i++) {
        if (sum[i] == k)
            ans += k;
        else {
            for (int j = (i - 1) * k + 1; j <= i * k; j++) ans += a[j];
        }
    }
    cout << ans << endl;
    return;
}
int main() {
    cin >> n;
    k = sqrt(n);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int opt, l, r, c;
    for (int i = 1; i <= n; i++) {
        cin >> opt >> l >> r >> c;
        if (opt == 0)
            does(l, r);
        else
            query(l, r);
    }
    return 0;
}

数列分块入门 6

题意

给出一个长为的数列，以及个操作，操作涉及单点插入，单点询问，数据随机生成。

对于每个区间都用个去存,然后插入就是相当于是插入复杂度我不知道，但是肯定挺低的
当然如果对一个区间插入过多的话，询问还是会,所以当插入过多的时候我们需要对区间一分为二，或者是重构一下数列分块。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, m, k;
int a[maxn], b[maxn << 1];
vector<int> q[100005];
pair<int, int> find_(int x) {
    pair<int, int> ans;
    int i = 1;
    while (x) {
        if (x > q[i].size())
            x -= q[i++].size();
        else {
            ans.second = x - 1;
            break;
        }
    }
    ans.first = i;
    return ans;
}
void query(int r) {
    pair<int, int> ans = find_(r);
    cout << q[ans.first][ans.second] << endl;
    return;
}
void insert_(int l, int r) {
    pair<int, int> ans = find_(l);
    q[ans.first].insert(q[ans.first].begin() + ans.second, r);
    return;
}
void rebuild() {
    int s = 1;
    for (int i = 1; i <= (n - 1) / k + 1; i++) {
        for (int j = 0; j < q[i].size(); j++) b[s++] = q[i][j];
        q[i].clear();
    }
    k = sqrt(s);
    for (int i = 1; i <= s; i++) {
        q[(i - 1) / k + 1].push_back(b[i]);
    }
    /*
    for(int i=1;i<=3;i++){
        for(int j=0;j<q[i].size();j++){
            cout<<q[i][j]<<' ';
        }
        cout<<endl;
    }
    */
    return;
}
int main() {
    cin >> n;
    k = sqrt(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        q[(i - 1) / k + 1].push_back(a[i]);
    }
    int cnt = 0;
    int opt, l, r, c;
    for (int i = 1; i <= n; i++) {
        cin >> opt >> l >> r >> c;
        if (opt == 0)
            insert_(l, r), cnt++;
        else
            query(r);
        if (cnt == k) {
            rebuild();
            cnt = 0;
        }
    }
    return 0;
}

数列分块入门 7

题意

给出一个长为的数列，以及个操作，操作涉及区间乘法，区间加法，单点查询(询问取模10007)。

这里需要维护两个值就是区间乘和区间加，这里我们对于对不完整区间进行加法和乘法的时候就应该先将该区间的乘法和加法进行计算，然后再算区间加和乘，这样才能不将后面该算的一些乘法加法和前面的混在一起，当然对于完整区间就直接统计一下区间乘和区间加就行了，这里主要先乘后加然后取模。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 10007;
int n, m;
ll a[1000005], sum[100005], chen[100005];
int k;
void add(int l, int r, int c) {
    int cl = (l - 1) / k + 1;
    int cr = (r - 1) / k + 1;
    for (int i = (cl - 1) * k + 1; i <= cl * k; i++) {
        a[i] = (a[i] * chen[cl] % mod + sum[cl] + mod) % mod;
        if (i >= l && i <= r)
            a[i] = (a[i] + c + mod) % mod;
    }
    sum[cl] = 0;
    chen[cl] = 1;
    if (cl != cr) {
        for (int i = (cr - 1) * k + 1; i <= cr * k; i++) {
            a[i] = (a[i] * chen[cr] % mod + sum[cr] + mod) % mod;
            if (i <= r)
                a[i] = (a[i] + c + mod) % mod;
        }
        sum[cr] = 0;
        chen[cr] = 1;
    }
    for (int i = cl + 1; i < cr; i++) sum[i] = (sum[i] + c + mod) % mod;
}
void does(int l, int r, int c) {
    int cl = (l - 1) / k + 1;
    int cr = (r - 1) / k + 1;
    for (int i = (cl - 1) * k + 1; i <= cl * k; i++) {
        a[i] = (a[i] * chen[cl] % mod + sum[cl] + mod) % mod;
        if (i >= l && i <= r)
            a[i] = (a[i] * c % mod + mod) % mod;
    }
    sum[cl] = 0;
    chen[cl] = 1;
    if (cl != cr) {
        for (int i = (cr - 1) * k + 1; i <= cr * k; i++) {
            a[i] = (a[i] * chen[cr] % mod + sum[cr] + mod) % mod;
            if (i <= r)
                a[i] = (a[i] * c % mod + mod) % mod;
        }
        sum[cr] = 0;
        chen[cr] = 1;
    }
    for (int i = cl + 1; i < cr; i++) {
        sum[i] = (sum[i] * c % mod + mod) % mod;
        chen[i] = (chen[i] * c % mod + mod) % mod;
    }
}
void query(int r) {
    int cr = (r - 1) / k + 1;
    ll ans = (a[r] * chen[cr] % mod + sum[cr]) % mod;
    cout << ans << endl;
    return;
}
int main() {
    cin >> n;
    k = sqrt(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= mod;
        chen[(i - 1) / k + 1] = 1;
    }
    int opt, l, r, c;
    for (int i = 1; i <= n; i++) {
        cin >> opt >> l >> r >> c;
        c %= mod;
        if (opt == 0)
            add(l, r, c);
        else if (opt == 1)
            does(l, r, c);
        else
            query(r);
    }
    return 0;
}
/*
19
8 9 1 6 7 6 7 1 2 3 4 1 5 3 7 4 1 7 8
1 2 3 7
0 1 6 1
1 2 5 7
1 7 10 1
0 7 10 6
1 2 4 3
2 2 3 9
2 1 2 5
0 2 14 0
0 15 16 0
1 1 14 6
1 9 18 7
0 2 7 4
2 3 8 0
0 10 12 8
2 4 15 8
1 3 10 7
1 1 2 9
1 2 16 1
*/

数列分块入门 8

题意

给出一个长为的数列，以及个操作，操作涉及区间询问等于一个数的元素，并将这个区间的所有元素改为。

这里我们需要对每个区间先维护一个变量，即如果区间内元素有多种，则设为-1，如果只有一种就则设置为这种元素的值

这里我们需要分三种情况
一. 当区间变量为-1时，暴力查询，暴力修改
二. 当变量为查询的值时， 不需要修改，直接加上区间长度
三. 当变量即不为-1 也不为 查询值时，也需要暴力修改查询

当然在一和三之后，我们需要暴力判断是否这个区间变量需要修改
而且在三时，我们需要先将本值修改为区间变量

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 10007;
int n, m;
ll a[1000005], b[100005];
int k;
void query(int l, int r, int c) {
    int cl = (l - 1) / k + 1;
    int cr = (r - 1) / k + 1;
    int ans = 0;
    if (b[cl] == -1) {
        for (int i = l; i <= min(cl * k, r); i++) {
            if (a[i] == c)
                ans++;
            else
                a[i] = c;
        }
        int flag = 0;
        for (int i = (cl - 1) * k + 1; i <= cl * k; i++)
            if (a[i] != c) {
                flag = 1;
                break;
            }
        if (!flag)
            b[cl] = c;
    } else if (b[cl] == c)
        ans += min(cl * k, r) - l + 1;
    else {
        for (int i = (cl - 1) * k + 1; i <= cl * k; i++) a[i] = b[cl];
        if (l == (cl - 1) * k + 1 && r >= cl * k)
            b[cl] = c;
        else {
            for (int i = l; i <= min(cl * k, r); i++) a[i] = c;
            b[cl] = -1;
        }
    }
    if (cl != cr) {
        if (b[cr] == -1) {
            for (int i = (cr - 1) * k + 1; i <= r; i++) {
                if (a[i] == c)
                    ans++;
                else
                    a[i] = c;
            }
            int flag = 0;
            for (int i = (cr - 1) * k + 1; i <= min(cr * k, n); i++)
                if (a[i] != c) {
                    flag = 1;
                    break;
                }
            if (!flag)
                b[cr] = c;
        } else if (b[cr] == c)
            ans += r - (cr - 1) * k;
        else {
            for (int i = (cr - 1) * k + 1; i <= cr * k; i++) a[i] = b[cr];
            if (r == n || r == cr * k)
                b[cr] = c;
            else {
                for (int i = (cr - 1) * k + 1; i <= r; i++) a[i] = c;
                b[cr] = -1;
            }
        }
    }
    for (int i = cl + 1; i < cr; i++) {
        if (b[i] == -1) {
            for (int j = (i - 1) * k + 1; j <= i * k; j++) {
                if (a[j] == c)
                    ans++;
                else
                    a[j] = c;
            }
            int flag = 0;
            for (int j = (i - 1) * k + 1; j <= i * k; j++)
                if (a[j] != c) {
                    flag = 1;
                    break;
                }
            if (flag)
                b[i] = -1;
            else
                b[i] = c;
        } else if (b[i] == c)
            ans += k;
        else {
            // for(int j=(i-1)*k+1;j<=i*k;j++) a[j]=c;
            b[i] = c;
        }
    }
    cout << ans << endl;
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    memset(b, -1, sizeof(b));
    k = 0.5 * sqrt(n);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l, r, c;
    for (int i = 1; i <= n; i++) {
        cin >> l >> r >> c;
        query(l, r, c);
    }
    return 0;
}