[ABC430G] Range Set Modifying Query 题解

· · 题解

Range Set Modifying Query 题解

分块

好玩的数据结构题 看到这道题就有一种分块的欲望。记 m = \max(x)。

先用一个 bitset 维护一下每个集合的状态，有数 i 那么第 i 位就设为 1，否则设为 0。

对于一个零散块我们直接暴力重构，维护一下每个块的最大值和最大值出现的次数即可，现在我们只需要考虑一个整块如何维护即可。

对于一个整块，我们发现如果这一个块第 i 位全部是 1 或者全部是 0，那么修改的时候就可以在 O(1) 的复杂度内维护块中的最大值和最大值的数量，具体地，容易发现最大值的数量一定不变，如果全是 0 且是 add 操作，则最大值加一，如果全是 1 且是 remove 操作，则最大值减一，否则最大值不变。

那么我们就成功地解决了这一位上全部都一样的情况，那么有不一样的情况怎么办呢？我稍微推了一下发现推不出来了，但是注意到一个整块被整体覆盖时这一位就全部一样了（废话），也就是说一个整块在两次重构中最多会出现上述不好解决的情况 m 次，而 m \le 60，所以我们可以考虑在遇到当前位上有不一样的情况时暴力重构这一个块，这样就把一个非常不好解决的问题转换为了暴力。

让我们来分析一下时间复杂度吧。

首先暴力重构的时间复杂度是 O(m\sqrt{n}) 的。每次修改时最多会遇到 O(\sqrt{n}) 个整块。对于整块，若当前修改的这一位上全部都一样，那么时间复杂度是 O(1) 的，否则需要重构，是 O(m\sqrt{n}) 的。

需要重构多少次呢？每次修改操作整块上的全部一样的位不会变少，只有零散块上一样的位会变少，那么一次操作后总的需要重构的次数最多增加 O(m) 个，q 次操作过后最多有 O(qm) 次重构，故在整块上重构的时间复杂度不超过 O(qm^2\sqrt{n})。

查询的时间复杂度是 O(m\sqrt{n}) 的，比较好分析。

总时间复杂度为 O(qm\sqrt{n}+qm^2\sqrt{n})。

CODE

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <cmath>
using namespace std;
typedef long long LL;

const int MAX_N = 3e5+5, SQRT_N = 707, V = 60, MAX_V = 65;

int n, q;

namespace blocks {
    int block_number, block_length, b_l[SQRT_N], b_r[SQRT_N], bb[MAX_N], mx[SQRT_N], num[SQRT_N];
    bitset<V> is[SQRT_N], a[MAX_N], tag[SQRT_N][2];

    void rebuild (int b) {
        is[b].set();
        int l = b_l[b], r = b_r[b];
        mx[b] = 0;
        num[b] = 0;
        for(int i = l; i <= r; i ++) {
            a[i] &= tag[b][0];
            a[i] |= tag[b][1];
            if(i > l) {
                is[b] &= ~(a[i-1] ^ a[i]);
            }
            if((int)a[i].count() > mx[b]) {
                mx[b] = a[i].count();
                num[b] = 1;
            }
            else if((int)a[i].count() == mx[b]) {
                ++ num[b];
            }
        }
        tag[b][0].set();
        tag[b][1].reset();
    }

    void init (int n) {
        block_length = sqrt(n+0.5);
        if(block_length >= 459) block_length = 459;
        block_number = (n + block_length - 1) / block_length;
        for(int i = 1; i <= block_number; i ++) {
            b_l[i] = (i-1)*block_length+1;
            if(i == block_number) b_r[i] = n;
            else b_r[i] = i*block_length;
            for(int j = b_l[i]; j <= b_r[i]; j ++) {
                bb[j] = i;
                a[j].reset();
            }
            rebuild(i);
        }
    }

    void add (int l, int r, int x) {
        int bl = bb[l], br = bb[r];
        if(bl == br) {
            rebuild(bl);
            for(int i = l; i <= r; i ++) {
                a[i][x] = 1;
            }
            rebuild(bl);
            return;
        }
        rebuild(bl);
        for(int i = l; i <= b_r[bl]; i ++) {
            a[i][x] = 1;
        }
        rebuild(bl);
        ++ bl;
        rebuild(br);
        for(int i = b_l[br]; i <= r; i ++) {
            a[i][x] = 1;
        }
        rebuild(br);
        -- br;
        for(int i = bl; i <= br; i ++) {
            if(is[i][x] == 1) {
                if(tag[i][0][x] == 0) ++ mx[i];
                else if(tag[i][1][x] == 0 && a[b_l[i]][x] == 0) ++ mx[i];
                tag[i][0][x] = 1;
                tag[i][1][x] = 1;
            }
            else {
                tag[i][0][x] = 1;
                tag[i][1][x] = 1;
                rebuild(i);
            }
        }
    }

    void remove (int l, int r, int x) {
        int bl = bb[l], br = bb[r];
        if(bl == br) {
            rebuild(bl);
            for(int i = l; i <= r; i ++) {
                a[i][x] = 0;
            }
            rebuild(bl);
            return;
        }
        rebuild(bl);
        for(int i = l; i <= b_r[bl]; i ++) {
            a[i][x] = 0;
        }
        rebuild(bl);
        ++ bl;
        rebuild(br);
        for(int i = b_l[br]; i <= r; i ++) {
            a[i][x] = 0;
        }
        rebuild(br);
        -- br;
        for(int i = bl; i <= br; i ++) {
            if(is[i][x] == 1) {
                if(tag[i][1][x] == 1) -- mx[i];
                else if(tag[i][0][x] == 1 && a[b_l[i]][x] == 1) -- mx[i];
                tag[i][0][x] = 0;
                tag[i][1][x] = 0;
            }
            else {
                tag[i][0][x] = 0;
                tag[i][1][x] = 0;
                rebuild(i);
            }
        }
    }

    pair<int,int> query (int l, int r) {
        int bl = bb[l], br = bb[r];
        int mxs = 0, nums = 0;
        if(bl == br) {
            rebuild(bl);
            for(int i = l; i <= r; i ++) {
                if((int)a[i].count() > mxs) {
                    mxs = a[i].count();
                    nums = 1;
                }
                else if((int)a[i].count() == mxs) {
                    ++ nums;
                }
            }
            return {mxs, nums};
        }
        rebuild(bl);
        for(int i = l; i <= b_r[bl]; i ++) {
            if((int)a[i].count() > mxs) {
                mxs = a[i].count();
                nums = 1;
            }
            else if((int)a[i].count() == mxs) {
                ++ nums;
            }
        }
        ++ bl;
        rebuild(br);
        for(int i = b_l[br]; i <= r; i ++) {
            if((int)a[i].count() > mxs) {
                mxs = a[i].count();
                nums = 1;
            }
            else if((int)a[i].count() == mxs) {
                ++ nums;
            }
        }
        -- br;
        for(int i = bl; i <= br; i ++) {
            if(mx[i] > mxs) {
                mxs = mx[i];
                nums = num[i];
            }
            else if(mx[i] == mxs) {
                nums += num[i];
            }
        }
        return {mxs, nums};
    }
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    blocks::init(n);
    while(q --) {
        int opt, l, r, x;
        cin >> opt >> l >> r;
        if(opt == 1) {
            cin >> x;
            blocks::add(l, r, x-1);
        }
        else if(opt == 2) {
            cin >> x;
            blocks::remove(l, r, x-1);
        }
        else {
            pair<int, int> k = blocks::query(l, r);
            cout << k.first << " " << k.second << "\n";
        }
    }
    return 0;
}