首页 > 其他分享 >分块思想基础莫队

分块思想基础莫队

时间：2023-04-30 17:57:03浏览次数：50  
标签：cnt bel 思想 分块 int sqrt -- 莫队 block

分块

将数组分成sqrt(n)块，每次进行区间操作或者查询的时候，对于完整的块可以通过预处理的信息o1得到，
不完整的块直接暴力跑，所以最坏复杂度是sqrt(n)。
分块模板

const int N = 100010, B = sqrt(N);
int block;
int st[B], ed[B], bel[N];
int sum[B], tag[B];
int a[N], sz[B];
void init(int n) {
    block = sqrt(n + 0.5);
    for (int i = 1; i <= block; i++) {
        st[i] = n / block * (i - 1) + 1; // st[i]表示i号块的第一个元素的下标
        ed[i] = n / block * i;
    }
    ed[block] = n;
    for (int i = 1; i <= block; i++) {
        for (int j = st[i]; j <= ed[i]; j++) {
            bel[j] = i;//编号
            //sum[i] += a[j];
        }
        sz[i] = ed[i] - st[i] + 1; //大小
    }
}

查询和修改操作

int query(int l, int r) {
    int ans = 0;
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i++) {
            ans += a[i] + tag[bel[i]];
        }
        return ans;
    } else {
        for (int i = l; i <= ed[bel[l]]; i++) {
            ans += a[i] + tag[bel[i]];
        }
        for (int i = st[bel[r]]; i <= r; i++) {
            ans += a[i] + tag[bel[i]];
        }
        int L = bel[l] + 1, R = bel[r] - 1;
        for (int i = L; i <= R; i++) {
            ans += sum[i] + sz[i] * tag[i];
        }
        return ans;
    }

}
void modify(int l, int r, int x) {
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i++) {//在一个快
            a[i] += x;
            sum[bel[i]] += x;
        }
    } else {
        for (int i = l; i <= ed[bel[l]]; i++) { //左边
            a[i] += x;
            sum[bel[i]] += x;
        }
        for (int i = st[bel[r]]; i <= r; i++) { //右边
            a[i] += x;
            sum[bel[i]] += x;
        }
        int L = bel[l] + 1, R = bel[r] - 1;
        for (int i = L; i <= R; i++) {
            // sum[i] += sz[i] * x;
            tag[i] += x;
        }
    }
}

P3372 【模板】线段树 1
直接套用模板即可

const int N = 100010, B = sqrt(N);
int block;
int st[B], ed[B], bel[N];
int sum[B], tag[B];
int a[N], sz[B];
void init(int n) {
    block = sqrt(n + 0.5);
    for (int i = 1; i <= block; i++) {
        st[i] = n / block * (i - 1) + 1; // st[i]表示i号块的第一个元素的下标
        ed[i] = n / block * i;
    }
    ed[block] = n;
    for (int i = 1; i <= block; i++) {
        for (int j = st[i]; j <= ed[i]; j++) {
            bel[j] = i;//编号
            sum[i] += a[j];
        }
        sz[i] = ed[i] - st[i] + 1; //大小
    }
}
int query(int l, int r) {
    int ans = 0;
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i++) {
            ans += a[i] + tag[bel[i]];
        }
        return ans;
    } else {
        for (int i = l; i <= ed[bel[l]]; i++) {
            ans += a[i] + tag[bel[i]];
        }
        for (int i = st[bel[r]]; i <= r; i++) {
            ans += a[i] + tag[bel[i]];
        }
        int L = bel[l] + 1, R = bel[r] - 1;
        for (int i = L; i <= R; i++) {
            ans += sum[i] + sz[i] * tag[i];
        }
        return ans;
    }

}
void modify(int l, int r, int x) {
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i++) {//在一个快
            a[i] += x;
            sum[bel[i]] += x;
        }
    } else {
        for (int i = l; i <= ed[bel[l]]; i++) { //左边
            a[i] += x;
            sum[bel[i]] += x;
        }
        for (int i = st[bel[r]]; i <= r; i++) { //右边
            a[i] += x;
            sum[bel[i]] += x;
        }
        int L = bel[l] + 1, R = bel[r] - 1;
        for (int i = L; i <= R; i++) {
            // sum[i] += sz[i] * x;
            tag[i] += x;
        }
    }
}
void solve(int Case) {

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    init(n);
    for (int i = 1; i <= m; i++) {
        int opt, l, r, c;
        cin >> opt >> l >> r ;
        if (opt == 1) {
            cin >> c;
            modify(l, r, c);
        } else {
            cout << query(l, r) << nline;
        }

    }
}

P2801 教主的魔法
区间加操作分块可以轻松完成，对于查询大于等于w的数字，不完整的块直接暴力跑，完整的块可以排序二分求；
首先预处理每个块并且排好序，对于每次修改不完整的块，单独进行一次排序，这样就保证块内始终是有序的；

const int N = 2000100, B = sqrt(N);
int block;
int st[B], ed[B], bel[N];
int sum[B], tag[B];
int a[N], sz[B];
int c[N];
void Sort(int k) {
    int l = st[k], r = ed[k];
    for (int i = l; i <= r; i++) c[i] = a[i];
    sort(c + l, c + r + 1);
}
void init(int n) {
    block = sqrt(n + 0.5);
    for (int i = 1; i <= block; i++) {
        st[i] = n / block * (i - 1) + 1; // st[i]表示i号块的第一个元素的下标
        ed[i] = n / block * i;
    }
    ed[block] = n;
    for (int i = 1; i <= block; i++) {
        for (int j = st[i]; j <= ed[i]; j++) {
            bel[j] = i;//编号
            sum[i] += a[j];
        }
        sz[i] = ed[i] - st[i] + 1; //大小
    }
    for (int i = 1; i <= n; i++) c[i] = a[i];
    for (int i = 1; i <= block; i++) {
        Sort(i);
    }

}
int query(int l, int r, int k) {
    int ans = 0;
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i++) {
            ans += (a[i] + tag[bel[i]] >= k);
        }
        return ans;
    } else {
        for (int i = l; i <= ed[bel[l]]; i++) {
            ans += (a[i] + tag[bel[i]] >= k);
        }
        for (int i = st[bel[r]]; i <= r; i++) {
            ans += (a[i] + tag[bel[i]]) >= k;
        }
        int L = bel[l] + 1, R = bel[r] - 1;
        for (int i = L; i <= R; i++) {
            //
            ans += ed[i] - (lower_bound(c + st[i], c + ed[i] + 1, k - tag[i]) - c) + 1;
        }
        return ans;
    }

}
void modify(int l, int r, int x) {
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i++) {//在一个快
            a[i] += x;
            sum[bel[i]] += x;
        }
        Sort(bel[l]);
    } else {
        for (int i = l; i <= ed[bel[l]]; i++) { //左边
            a[i] += x;
            sum[bel[i]] += x;
        }
        Sort(bel[l]);
        for (int i = st[bel[r]]; i <= r; i++) { //右边
            a[i] += x;
            sum[bel[i]] += x;
        }
        Sort(bel[r]);
        int L = bel[l] + 1, R = bel[r] - 1;
        for (int i = L; i <= R; i++) {
            // sum[i] += sz[i] * x;
            tag[i] += x;
        }
    }
}
void solve(int Case) {

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    init(n);
    for (int i = 1; i <= q; i++) {
        int l, r, w;
        char op[2];
        cin >> op;
        cin >> l >> r >> w;
        if (op[0] == 'M') {
            modify(l, r, w);
        } else {
            cout << query(l, r, w) << nline;
        }
    }
}

莫队

莫队算法具体操作是把查询区间按照左端点分块，块内右端点有序；
这样每次l能够移动的范围是sqrt(n)，因为r是单调的，每个块最多跑n次，一共sqrt(n)个块，所以整体复杂度就是msqrt(n)，m是查询次数
P1494 [国家集训队] 小 Z 的袜子

贡献区间内所有袜子种类x，sum（C(cnt[x],2))/C(len,2),len为长度，单独考虑每增加一个x类袜子，就多出cnt[x]种可能，每减少一个x，就减少cnt[x]种可能。

const int N = 500100;
int a[N];
int block;
struct T {
    int l, r, id;
    bool operator<(const T &t)const {
        if (l / block != t.l / block) return l / block < t.l / block;
        return r < t.r;
    }
} q[N];
using PII = pair<int, int>;
PII ans[N];
int vis[N];
int cnt = 0;
void del(int x) {
    vis[x]--;
    cnt -= vis[x];
}
void add(int x) {
    ++vis[x];
    cnt += vis[x] - 1;
}
// int ans[N];
void solve(int Case) {
    int n, m;
    cin >> n >> m;
    block = sqrt(n + 0.5);
    for (int i = 1; i <= n; i++) cin >> a[i];
    // cin >> m;
    for (int i = 1; i <= m; i++) {
        auto &[l, r, id] = q[i];
        cin >> l >> r;
        id = i;
    }
    sort(q + 1, q + 1 + m);
    int l = 1, r = 1;
    cnt = 0;
    vis[a[1]] = 1;
    for (int i = 1; i <= m; i++) {
        auto &[x, y, id] = q[i];
        while (l < x) del(a[l++]);
        while (l > x) add(a[--l]);
        while (r < y) add(a[++r]);
        while (r > y) del(a[r--]);
        auto&[f, s] = ans[id];

        f = cnt, s = (y - x + 1) * (y - x) / 2;
        int g = __gcd(f, s);
        if (x == y) {
            f = 0, s = 1;
            continue;
        }
        f /= g;
        s /= g;
    }
    for (int i = 1; i <= m; i++) {
        auto &[f, s] = ans[i];
        cout << f << '/' << s << nline;
    }
}

E. XOR and Favorite Number
考虑前缀异或和，s[i]^s[j-1]=k，则说明j~i的异或和等于k，可以统计前缀异或和的个数，然后类似上题

const int N = 2000100;
int a[N], s[N];
int vis[N];
int block;
int ans[N];
struct T {
    int l, r, id;
    bool operator<(const T &t) const {
        if (l / block != t.l / block) return l / block < t.l / block;
        return r < t.r;
    }
} q[N];
int cnt = 0;
int n, m, k;
void del(int x) {
    vis[x]--;
    cnt -= vis[x ^ k];
}
void add(int x) {
    cnt += vis[x ^ k];
    vis[x]++;
}
void solve(int Case) {
    cin >> n >> m >> k;
    block = sqrt(n + 0.5);
    for (int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i - 1] ^ a[i];
    for (int i = 1; i <= m; i++) {
        auto &[l, r, id] = q[i];
        cin >> l >> r;
        id = i;
    }
    sort(q + 1, q + 1 + m);
    int l = 1, r = 0;
    vis[0]++;
    for (int i = 1; i <= m; i++) {
        auto [x, y, id] = q[i];
        while (l < x) del(s[l-1]),l++;
        while (l > x) l--,add(s[l-1]);
        while (r < y) add(s[++r]);
        while (r > y) del(s[r--]);
 
        ans[id] = cnt;
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << nline;
}

P4137 Rmq Problem / mex
判断每个数字是否出现过，这个过程可以通过分块来判断，如果一个块内数字全部出现则直接跳过，否则mex就在这个块内
配合莫队，整体复杂度m*sqrt(n)

const int N = 200010, B = sqrt(N);
int a[N];
int block;
int ans[N];
int f[B];
int sz[B], st[B], ed[B], bel[N];
int cnt[N];
void init(int n) {
    block = sqrt(n + 0.5);
    for (int i = 1; i <= block; i++) {
        st[i] = n / block * (i - 1) + 1; // st[i]表示i号块的第一个元素的下标
        ed[i] = n / block * i;
    }
    ed[block] = n;
    for (int i = 1; i <= block; i++) {
        for (int j = st[i]; j <= ed[i]; j++) {
            bel[j] = i;//编号
        }
        sz[i] = ed[i] - st[i] + 1; //大小
    }
}

struct T {
    int l, r, id;
    bool operator<(const T &t) const {
        if (l / block != t.l / block) return l / block < t.l / block;
        return r < t.r;
    }
} q[N];
int n, m, k;

void del(int x) {
    if (x > n + 1) return;
    cnt[x]--;
    if (!cnt[x]) {
        f[bel[x]]--;
    }
}
void add(int x) {
    if (x > n + 1) return;
    cnt[x]++;
    if (cnt[x] == 1) {
        f[bel[x]]++;
    }
}
int query() {
    for (int i = 1; i <= block; i++) {
        if (f[i] == sz[i]) continue;
        else {
            for (int j = st[i]; j <= ed[i]; j++) {
                if (cnt[j] == 0) return j;
            }
        }
    }
    return n + 2;
}
void solve(int Case) {
    cin >> n >> m;
    block = sqrt(n + 0.5);
    for (int i = 1; i <= n; i++) cin >> a[i], a[i]++;
    init(n+1);
    for (yint i = 1; i <= m; i++) {
        auto &[l, r, id] = q[i];
        cin >> l >> r;
        id = i;
    }
    sort(q + 1, q + 1 + m);
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++) {
        auto [x, y, id] = q[i];
        while (l < x) del(a[l++]);
        while (l > x) add(a[--l]);
        while (r < y) add(a[++r]);
        while (r > y) del(a[r--]);
        ans[id] = query() - 1;
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << nline;
}

本文参考oiwiki
https://oi-wiki.org/ds/decompose/
https://oi-wiki.org/ds/block-array/

标签：cnt,bel,思想,分块,int,sqrt,--,莫队,block
From： https://www.cnblogs.com/koto-k/p/17365540.html

相关文章

  • 莫队
    一种用来处理序列上区间询问问题的算法。来看一下最经典的莫队题。区间不同数给定长为\(n\)的序列\(a\),有\(m\)组询问。每组询问给定一个区间\([l,r]\),求区间内有多少种不同的数。\(n,m\le10^5\)，\(a_i\in[0,10^6]\)我们可以观察到如果我们已知\([l,r]\)的......
  • 分块+莫队算法
    分块复杂度\(O(n\sqrtn)\)主要目的是解决一些区间操作问题把区间拆分成\(\sqrt{n}\)大小的块每次碰到修改的操作，对于散块，直接暴力操作，对于整块，那么用一个\(tag\)进行标记即可也就是说对于一个操作\([l,r]\)来说我们需要进行操作主要分三步：暴力操作头散块，即\([l,......
  • day 57 代码思想录 647. 回文子串 |
    给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。示例1：输入："abc"输出：3解释：三个回文子串:"a","b","c"示例2：输入："aaa"输出：6解释：6个回文子串:"a","a","a","aa&......
  • 关于代码优化-池化思想
    我们都用过数据库连接池，线程池等，这就是池思想的体现，它们解决的问题就是避免重复创建对象或创建连接，可以重复利用，避免不必要的损耗，毕竟创建销毁也会占用时间。池化思想包含但并不局限于以上两种，总的来说池化思想的本质是**预分配与循环使用，**明白这个原理后，我们即使是在做一些业务......
  • GitLab-DevOps思想
    1、什么是DevOps：  DevOps是Development（开发）和Operations（运维）的缩写，是一组过程、方法与系统的统称；强调“应用程序/软件工程”的开发、技术运营和质量保障（QA）人员之间沟通、协作一体化。实现持续集成、持续交付，包括持续部署。2、DevOps的意义：  ......
  • 从一维到十维，延伸至思想的一维到高维
     https://www.bilibili.com/video/BV17s4y1S7E7/?spm_id_from=333.1007.tianma.2-1-4.click&vd_source=e4991eff671e2c8b3ce1f748b6cca451https://www.bilibili.com/video/BV12x411Y7J7/?spm_id_from=autoNext&vd_source=e4991eff671e2c8b3ce1f748b6cca451  二维平面......
  • 扎实打牢数据结构算法根基，从此不怕算法面试系列之010 week02 01-01 最简单的排序算法-
    1、基础排序算法接下类，我们学习另外一类非常基础的算法，即排序算法。排序算法是计算机科学领域研究的非常深入的一类算法，排序这个动作本身也是非常重要的，很多时候面对无需的数据，首先需要做的就是对他们进行排序。排序算法——目的：让数据有序。排序算法——种类：种类也非常多，适......
  • 词嵌入思想简要
    词嵌入（WordEmbedding）是一种将单词映射到低维向量空间中的技术，它通过将每个单词表示为一个向量，来捕捉单词之间的语义和上下文信息。这种技术的思想是基于分布式语义假说（DistributedSemanticsHypothesis）提出的。该假说认为，每个单词都可以通过它周围的上下文来表达其语义信息，也......
  • 随机特征映射基本思想
    随机特征映射基本思想简介随机傅里叶特征映射(RandomFourierFeatureMapping)的基本理论随机核特征映射(RandomKernelFeatureMapping)基本理论随机局部线性嵌入(RandomLocalityPreservingEmbedding)的基本理论随机投影(RandomProjection)的基本理论简介......
  • 伟大思想论文：Cantor–Bernstein-Schröder 定理及其证明简介
    Cantor–Bernstein-Schröder定理及其证明简介1定理简介Cantor–Bernstein-Schröder定理，也称作Schröder–Bernstein定理、Cantor–Bernstein定理，是集合论中的重要定理。它的内容十分简单：如果集合\(A\)到集合\(B\)存在单射，且集合\(B\)到集合\(A\)存在单射，则集合......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99