(可持久化)带修莫队的实现方法

在普通的莫队中引入一维时间戳，读入时对每次询问记录最近一次修改的时间。离线操作时增加一维时间的操作，如果当前时间在当前询问的时间戳之前，那么把中间这一段时间的贡献加入答案，否则，把多出来的这段时间的贡献删除。删除的操作如下：正向经过时间是把修改贡献一个个累加，反向经过时间相当于把之前累加的贡献还原，所以每正向经过时间就把当前的修改贡献和本来的贡献互换一下，当正向经过时间的时候把修改的贡献加入把本来的贡献删除，互换过后当反向经过时间的时候就会把本来的贡献加入而把修改的贡献删除，然后每反向经过时间也把修改的贡献和本来的贡献互换一下，下次正向经过时间又能达到同样的效果。

时间复杂度上需要注意的地方：

1.排序方式(增加了一维时间戳后的排序方式):

bool friend operator<(const Q &a, const Q &b) {
//        return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
//        return (pos[a.l] ^ pos[b.l]) ? pos[a.l] < pos[b.l] : ((pos[a.l] & 1) ? a.r < b.r : a.r > b.r);
        return (pos[a.l] ^ pos[b.l]) ? pos[a.l] < pos[b.l] : ((pos[a.r] ^ pos[b.r]) ? pos[a.r] < pos[b.r] : a.t < b.t);
    }

2.分块大小:

经过某些dalao证明分块采用n^(2/3)的时间优于sqrt(n)的复杂度,因此可以这样:

int siz = ceil(pow(n, 0.6666)); 
    for (register int i = 1; i <= n; i++) a[i] = rd(), pos[i] = i / siz;

板题 Luogu P1903 [国家集训队]数颜色 / 维护队列:

#pragma GCC optimize(2)
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>
#include 
#define fi first
#define se second
#define re register
#define ls i << 1
#define rs i << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007

//#define int long long

using namespace std;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);

inline int rd(){
    re int res = 0,flag = 0;char ch;
    if ((ch = getchar()) == '-')flag = 1;
     else if(ch >= '0' && ch <= '9')res = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9')res = (res<<1) + (res<<3) + (ch - '0');
    return flag ? -res : res;
}

void out(int a) {
    if (a < 0) {
        putchar('-');a = -a;
    }
    if (a >= 10) out(a / 10);
    putchar(a % 10 + '0');
}

int n, m;
const int maxn = 233333;
const int N = 1e6+10;
char opt;
int res;
int a[maxn], pos[maxn], ans[maxn];
int cnt[N];
struct Q{
    int l, r, k, t;
    bool friend operator<(const Q &a, const Q &b) {
//        return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
//        return (pos[a.l] ^ pos[b.l]) ? pos[a.l] < pos[b.l] : ((pos[a.l] & 1) ? a.r < b.r : a.r > b.r);
        return (pos[a.l] ^ pos[b.l]) ? pos[a.l] < pos[b.l] : ((pos[a.r] ^ pos[b.r]) ? pos[a.r] < pos[b.r] : a.t < b.t);
    }
}q[maxn];

struct C{
    int pos, color;
}c[maxn];

int cntq, cntc;

//signed main(){
int main() {
    n = rd(), m = rd();
    int siz = ceil(pow(n, 0.6666)); 
    for (register int i = 1; i <= n; i++) a[i] = rd(), pos[i] = i / siz;
    for (register int i = 1; i <= m; i++) {
        cin >> opt;
        if (opt == 'Q') {
            q[++cntq].l = rd();
            q[cntq].r = rd();
            q[cntq].t = cntc;
            q[cntq].k = cntq;
        } else {
            c[++cntc].pos = rd();
            c[cntc].color = rd();
        }
    }
    sort(q+1, q+cntq+1);
    int l = 1, r = 0, time = 0;
    for (register int i = 1; i <= cntq; i++) {
        int lq = q[i].l, rq = q[i].r, qt = q[i].t;
        while (lq < l) res += !cnt[a[--l]]++;
        while (rq > r) res += !cnt[a[++r]]++;
        while (lq > l) res -= !--cnt[a[l++]];
        while (rq < r) res -= !--cnt[a[r--]];
        while (time < qt) {
            ++time;
            if (lq <= c[time].pos && c[time].pos <= rq) {
                res += !cnt[c[time].color]++ - !--cnt[a[c[time].pos]];
            }
            swap(a[c[time].pos], c[time].color);
        }
        while (time > qt) {
            if (lq <= c[time].pos && c[time].pos <= rq) {
                res += !cnt[c[time].color]++ - !--cnt[a[c[time].pos]];
            }
            swap(a[c[time].pos], c[time].color);
            --time;
        }
        ans[q[i].k] = res;
    }
    for (register int i = 1; i <= cntq; i++) {
        out(ans[i]);puts("");
    }
    return 0;
}

参考博客:https://www.cnblogs.com/WAMonster/p/10118934.html

莫队

(可持久化)带修莫队的实现方法

相关

【莫队算法】

莫队算法小记

P4688-[Ynoi2016]掉进兔子洞【莫队,bitset】

【CodeForces】700 D. Huffman Coding on Segment 哈夫曼树+莫队+分块

二次离线莫队学习笔记

【YBT2022寒假Day5 A】序列计数（组合数）（莫队）

【洛谷 P3674】小清新人渣的本愿（bitset，莫队）

[后缀数组][二分][莫队]luogu P2336 [SCOI2012]喵星球上的点名

待修改的莫队洛谷P1903 [国家集训队] 数颜色 / 维护队列

二次离线莫队学习笔记

分块+莫队

莫队

标签