BZOJ-2120 数颜色

数颜色

带修莫队 模板题

看到别人题解，发现有个小技巧，时间纬度在更改的时候直接 swap 当前值和要修改的值，下次回来的时候 swap 回去是一样的，这样就可以不用多记录状态了

https://fangkaipeng.com/?p=1504

我还发现非常 BZOJ 的数据和 AcWing 的数据相当奇怪，用分块大小为 \(\sqrt{n}\) 作为分块会更加快，而洛谷的数据用分块大小为 \(n^{\frac{2}{3}}\) 会更快

我的猜测是数据范围约束的问题，BZOJ 和 AcWing 的条件约束说修改的次数在于 1000 次以下，可能就导致了时间纬度修改的比较少，因此最优分块趋近于 \(\sqrt{n}\)

https://www.acwing.com/problem/content/2523/

正常的复杂度分析来说，分块大小应该为 \(n^{\frac{2}{3}}\)，复杂度为 \(O(n^{\frac{5}{3}})\)

https://www.luogu.com.cn/problem/P1903

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define endl '\n'
#define pii pair
const int maxn = 133333 + 10;
const ll maxm = 1e6 + 10;
const ll inf = 1e17 + 10;
int num[maxn], pos[maxm], cnt[maxm];
int l = 1, r = 0, ans = 0, t = 0, nn = 0;
int last[maxn];

struct node
{
    int l, r, t, id;
    node(){}
    node(int _l, int _r, int _t, int _id){l = _l; r = _r; t = _t; id = _id;}
}seg[maxn], change[maxn];

bool cmp(const node& a, const node& b)
{
    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);
}

inline void add(int x)
{
    ans += (++cnt[num[x]] == 1);
}

inline void del(int x)
{
    ans -= (--cnt[num[x]] == 0);
}

inline void update(int x)
{
    if(change[x].t >= l && change[x].t <= r)
    {
        del(change[x].t);
        swap(num[change[x].t], change[x].l);
        add(change[x].t);
    }
    else swap(num[change[x].t], change[x].l);
}

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    // freopen("text.in", "rb", stdin);
    // freopen("text.out", "wb", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    int maxx = 0;
    for(int i=1; i<=n; i++) {cin >> num[i]; maxx = num[i] > maxx ? num[i] : maxx;}
    nn = pow(maxn, 2.0 / 3.0);
    for(int i=1; i<=maxx; i++) pos[i] = i / nn;
    int tq = 0, tr = 0;
    for(int i=0; i seg[i].t) update(--t);
        while(r < seg[i].r) add(++r);
        while(l > seg[i].l) add(--l);
        while(r > seg[i].r) del(r--);
        while(l < seg[i].l) del(l++);
        last[seg[i].id] = ans;
    }
    for(int i=0; i
分块莫队

相关

【莫队算法】

题解 Count on a tree II/【模板】树分块

LOJ 数列分块入门 8

莫队算法小记

分块矩阵进行分块初等变换后秩不变的证明

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

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

二次离线莫队学习笔记

「 Luogu P2801 」 教主的魔法——分块

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

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

#分块，可撤销并查集#洛谷 3247 [HNOI2016]最小公倍数

标签