kuangbin 莫隊專題

這幾天把框斌的莫隊都刷完了， 還是有不少收獲的， 之前不會證明莫對的時間復雜度， 現在也能口胡證明了。

莫隊和其它數據結構不一樣，會了之后就很簡單。只要是關于區間o(1)算出貢獻都能用莫隊解決。

具體看下面的題目吧！

Sona

題解：求區間每個數出現的次數的立方和

題解：剛學莫隊的時候肯定知道求區間不同顏色的個數， 但是如何求不同顏色的個數的立方和了。

這里有個和巧妙的做法就是， 用vis數組記錄當前顏色出現的個數， 當出現顏色時， 先減去之前的個數

立方和在加上現在顏色的立法和， 這樣不斷跟新最后一次一定是這個區間 這個顏色出現的總次數了。

?

#include<iostream> #include<vector> #include<algorithm> #include<math.h> using namespace std; const int N = 1e5 + 7; struct query {int l, r, pos; }q[N];typedef long long ll; ll n, a[N], vis[N], res = 0, m, ans[N]; int block[N];vector<ll> g;bool cmp(query x, query y) {if (block[x.l] == block[y.l]) {return x.r < y.r;}return block[x.l] < block[y.l]; }int get_id(ll x) {return lower_bound(g.begin(), g.end(), x) - g.begin() + 1; }void add(int pos) {res -= vis[a[pos]] * vis[a[pos]] * vis[a[pos]];vis[a[pos]]++;res += vis[a[pos]] * vis[a[pos]] * vis[a[pos]]; }void del(int pos) {res -= vis[a[pos]] * vis[a[pos]] * vis[a[pos]];vis[a[pos]]--;res += vis[a[pos]] * vis[a[pos]] * vis[a[pos]]; }int main() {while(~scanf("%lld", &n)){g.clear();res = 0;for (int i = 0; i <= n + 10; i++) {vis[i] = 0;}int b = sqrt(n*1.0);for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]);g.push_back(a[i]);block[i] = i / b;}sort(g.begin(), g.end());g.erase(unique(g.begin(), g.end()), g.end());for (int i = 1; i <= n; i++) {a[i] = get_id(a[i]);}scanf("%lld", &m);for (int i = 1; i <= m; i++) {scanf("%d %d", &q[i].l, &q[i].r);if (q[i].l > q[i].r) swap(q[i].l, q[i].r);q[i].pos = i;}sort(q + 1, q + m + 1, cmp);int l = 1, r = 0;for (int i = 1; i <= m; i++) {while (l < q[i].l) {del(l++);}while (l > q[i].l) {add(--l);}while (r < q[i].r) {add(++r);}while (r > q[i].r) {del(r--);}ans[q[i].pos] = res;}for (int i = 1; i <= m; i++) {printf("%lld\n", ans[i]);}}}

Little Elephant and Array

題意：問區間有多少個數出現的次數是這個數本身

題解：假設這個數字為x, 用vis數組記錄每個數出現的個數， 如果剛好等于x那么答案加1如果剛好等于x + 1那么說明之前那個貢獻就刪掉 答案就減1.

代碼

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 7; struct query {int l, r, pos; }q[N];vector<ll> g; int n, m, block[N]; ll a[N], ans[N], res = 0, vis[N];void add(int pos) {if (a[pos] > n) return;vis[a[pos]]++;if (vis[a[pos]] == a[pos]) {res++;} else if (vis[a[pos]] == a[pos] + 1) {res--;} }void del(int pos) {if (a[pos] > n) return; vis[a[pos]]--;if (vis[a[pos]] == a[pos]) {res++;} else if (vis[a[pos]] == a[pos] - 1) {res--;} }bool cmp(query x, query y) {if (block[x.l] == block[y.l]) {return x.r < y.r;}return block[x.l] < block[y.l]; }int main() {scanf("%d %d", &n, &m);int b = sqrt(n);for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]);block[i] = i / b;}for (int i = 1; i <= m; i++) {scanf("%d %d", &q[i].l, &q[i].r);q[i].pos = i;}sort(q + 1, q + m + 1, cmp);int l = 1, r = 0;for (int i = 1; i <= m; i++) {while (l < q[i].l) {del(l++);}while (l > q[i].l) {add(--l);}while (r < q[i].r) {add(++r);}while (r > q[i].r) {del(r--);}ans[q[i].pos] = res;}for (int i = 1; i <= m; i++) {printf("%lld\n", ans[i]);} }

Machine Learning

題意：給你n個數，讓你求區間mex(0不算)和單點修改

題解：帶修莫隊板子題吧， 帶修莫隊和普通莫隊差不多多了一維時間， 每次暴力的時進行暴力修改， 然后要注意的是帶修莫隊分塊是\(n^{0.6666666}\)

代碼：

#include<bits/stdc++.h> using namespace std;const int N = 1e6 + 7;struct query {int l, r, t, id; }q[N];struct option {int pos, v; }p[N], back[N];int block[N], ans[N], vis[N], maxn[N], n, m, a[N],A[N];bool cmp (query x, query y) {if (block[x.l] == block[y.l]) {if (block[x.r] == block[y.r]) {return x.t < y.t;}return x.r < y.r;}return x.l < y.l; } vector<int> g;int get_id(int x) {return lower_bound(g.begin(), g.end(), x) - g.begin() + 1; }void update(int pos, int value) {a[pos] = value; }void add(int pos) {maxn[vis[a[pos]]]--;vis[a[pos]]++;maxn[vis[a[pos]]]++; }void del(int pos) {maxn[vis[a[pos]]]--;vis[a[pos]]--;maxn[vis[a[pos]]]++; }int main() {scanf("%d %d", &n, &m);int b = pow(n, 0.666666);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);A[i] = a[i];g.push_back(a[i]);block[i] = i / b;}int total = 0;int cnt = 1;for (int i = 1; i <= m; i++) {int op; scanf("%d", &op);if (op == 1) {scanf("%d %d", &q[cnt].l, &q[cnt].r);q[cnt].id = i;q[cnt].t = total;cnt++;} else {total++;scanf("%d %d", &p[total].pos, &p[total].v);back[total].v = A[p[total].pos];back[total].pos = p[total].pos;A[p[total].pos] = p[total].v;g.push_back(p[total].v);}}sort(g.begin(), g.end());g.erase(unique(g.begin(), g.end()), g.end());for (int i = 1; i <= n; i++) {a[i] = get_id(a[i]);}for (int i = 1; i <= total; i++) {p[i].v = get_id(p[i].v);back[i].v = get_id(back[i].v);}sort(q + 1, q + cnt, cmp);int l = 1, r = 0, now = 0;for (int i = 1; i < cnt; i++) {while (now < q[i].t) {now++;if (p[now].pos >= l && p[now].pos <= r) {maxn[vis[a[p[now].pos]]]--;vis[a[p[now].pos]]--;maxn[vis[a[p[now].pos]]]++;maxn[vis[p[now].v]]--;vis[p[now].v]++;maxn[vis[p[now].v]]++;}update(p[now].pos, p[now].v);}while (now > q[i].t) {if (l <= back[now].pos && r >= back[now].pos) {maxn[vis[a[back[now].pos]]]--;vis[a[back[now].pos]]--;maxn[vis[a[back[now].pos]]]++;maxn[vis[back[now].v]]--;vis[back[now].v]++;maxn[vis[back[now].v]]++;}update(back[now].pos, back[now].v);now--;}while (r < q[i].r) {add(++r);}while (l < q[i].l) {del(l++);}while (l > q[i].l) {add(--l);}while (r > q[i].r) {del(r--);}for (int j = 1; j <= 10000; j++) {if (maxn[j] == 0) {ans[q[i].id] = j;break;}}}for (int i = 1; i <= m; i++) {if (ans[i]) {printf("%d\n", ans[i]);}} }

Can you answer these queries II[https://vjudge.net/problem/SPOJ-GSS2]

題意：求區間最大連續子串的和， 重復的數字只算一次。

題解：這題不知道莫隊咋求解， 網上貌似沒用莫隊的解法， 基本上都是用線段樹解決這題的

線段樹操作這題第一步是離線， 將所有操作按照r進行從小到大排序。

為啥要按照r從小到大排序？

先想一下如何暴力求解？

如果給你一個區間讓你求最大子串和， 很多少人想的時\(n ^ {2}\)暴力， 其實只需要 O(n)暴力就可以解決

for (int i = l; i <= r; i++) {sum += a[i];ans = max(ans, sum);sum = max(0, sum); }

那能不能用線段樹o(n) * log(n)維護所有區間答案呢?

答案是可以的。

假設線段現在插入的是第i個數那么

第一個節點維護的信息是

\(a[1] + a[2] + a[3]+......+a[i]\)

第二個節點維護的信息是

\(a[2] + a[3] + a[4] + ......+ a[i]\)

第三個節點維護的信息是

\(a[3] + a[4] + ...... + a[i]\)

第i個節點維護的信息是

\(a[i]\)

那么插入到第i + 1個信息也是相當于區間1到i + 1加上a[i + 1]

線段樹每個節點還有在維護一個 從當前節點開始到i的所有子串的最大值

如果線段樹更新到第i個節點

那么 詢問操作中 r == i的答案一定在 l 到r中的最大值。

因為線段樹每個節點維護了從當前節點開始到i的所有子串的最大值。所以答案肯定在這個區間里面。

這就是之前為啥詢問要按照r從小到大排序。

難點還是線段樹的懶標記更新

去重的話自己仔細想一下應該可以想出來。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 7;struct segment {ll sum, maxn; }tree[4 * N];#define m (l + r) / 2 #define lson 2 * node #define rson 2 * node + 1ll a[N], ans[N]; int flag[4 * N], fmaxn[4 * N];void push_down(int node) {if (fmaxn[node]) {tree[lson].maxn = max(tree[lson].maxn, fmaxn[node] + tree[lson].sum);tree[rson].maxn = max(tree[rson].maxn, tree[rson].sum + fmaxn[node]);fmaxn[lson] = max(fmaxn[lson], fmaxn[node] + flag[lson]);fmaxn[rson] = max(fmaxn[rson], fmaxn[node] + flag[rson]);fmaxn[node] = 0;}if (flag[node]) {tree[lson].sum += flag[node];tree[rson].sum += flag[node];flag[lson] += flag[node];flag[rson] += flag[node];flag[node] = 0;}}void update(ll v, int ql, int qr, int l, int r, int node) {if (ql <= l && qr >= r) {tree[node].sum += v;tree[node].maxn = max(tree[node].maxn, tree[node].sum);flag[node] += v;fmaxn[node] = max(fmaxn[node], flag[node]);return;}push_down(node);if (ql <= m) update(v, ql, qr, l, m, lson);if (qr > m) update(v, ql, qr, m + 1, r, rson);tree[node].sum = max(tree[lson].sum, tree[rson].sum);tree[node].maxn = max(tree[lson].maxn, tree[rson].maxn); }ll query(int ql, int qr, int l, int r, int node) {if (ql <= l && qr >= r) {return tree[node].maxn;}ll ans = INT_MIN;push_down(node);if (ql <= m) ans = max(ans, query(ql, qr, l, m, lson));if (qr > m) ans = max(ans, query(ql, qr, m + 1, r, rson));return ans; }map<int , int>vis;int pos[N];struct qu{int l, r, id; }p[N];int main() {int n, q;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]);pos[i] = vis[a[i]];vis[a[i]] = i;}scanf("%d", &q);for (int i = 1; i <= q; i++) {int l, r; scanf("%d %d", &p[i].l, &p[i].r);p[i].id = i;}sort(p + 1, p + 1 + q, [](qu x, qu y) {return x.r < y.r;});int l = 1;for (int i = 1; i <= n; i++) {update(a[i], pos[i] + 1, i, 1, n, 1);while(p[l].r == i) {ans[p[l].id] = query(p[l].l, p[l].r, 1, n, 1);l++;}}for (int i = 1; i <= q; i++) {printf("%lld\n", ans[i]);}}

總結

以上是生活随笔為你收集整理的kuangbin 莫队专题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。