「省队集训 2016」Play with array - 块状链表

有一个长度为 n 的数列,支持以下两种操作:

  1. a_r 移动到 a_l 的前面;
  2. 查询 [l,\ r] k 的出现次数。

题解

将序列按照 O(\sqrt n) 分块,维护块状链表,将每次修改转化为一次插入一次删除,每个块记录每个数出现次数。

每次查询时,将 [l,\ r] 的答案转化为 [1,\ r] 的答案减去 [1,\ l - 1] 的答案。对于块内部分直接查询,块外部分暴力。

时间复杂度、空间复杂度均为 O(n \sqrt n)

代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <list>
#include <vector>
#include <algorithm>
#include <stack>

#define dprintf(format, ...) fprintf(stderr, format, __VA_ARGS__)

const int MAXN = 100000;
const int MAXN_SQRT = 316 + 1;
const int MAXM = 100000;

int n, m, a[MAXN];

struct BlockList {
    struct Block {
        std::list<int> l;
        std::vector<int> sum;

        Block() : sum(n) {}

        inline int left(const int k, const int pos) {
            int res = 0;
            std::list<int>::const_iterator it = l.begin();
            for (int i = 0; i <= pos; i++) if (*it++ == k) res++;
            return res;
        }
    };
    std::list<Block> blocks;
    int blockCount, blockSize;

    inline void build(const int *a, const int n) {
        blockCount = floor(sqrt(n) + 1), blockSize = ceil(static_cast<double>(n) / blockCount);
        // dprintf("BlockList::build(): blockCount = %d, blockSize = %d\n", blockCount, blockSize);
        blocks.resize(blockCount);
        std::list<Block>::iterator b = blocks.begin();
        for (int i = 0, j = 0; i < blockCount; i++, b++) {
            for (int k = 0; k <= blockSize && j < n; k++, j++) {
                b->sum[a[j]]++;
                b->l.push_back(a[j]);
            }
        }
    }

    inline int erase(int pos) {
        for (std::list<Block>::iterator b = blocks.begin(); b != blocks.end(); b++) {
            if (pos < b->l.size()) {
                std::list<int>::iterator it = b->l.begin();
                std::advance(it, pos);
                const int x = *it;
                b->sum[*it]--;
                b->l.erase(it);
                return x;
            } else pos -= b->l.size();
        }
        throw;
    }

    inline void insert(int pos, const int x) {
        for (std::list<Block>::iterator b = blocks.begin(); b != blocks.end(); b++) {
            if (pos < b->l.size()) {
                std::list<int>::iterator it = b->l.begin();
                std::advance(it, pos);
                b->sum[x]++;
                b->l.insert(it, x);
                return;
            } else pos -= b->l.size();
        }
        throw;
    }

    inline int query(int pos, const int k) {
        int ans = 0;
        for (std::list<Block>::iterator b = blocks.begin(); b != blocks.end(); b++) {
            if (pos < b->l.size()) {
                ans += b->left(k, pos);
                break;
            } else {
                pos -= b->l.size();
                ans += b->sum[k];
            }
        }
        return ans;
    }

    inline void mergeNext(std::list<Block>::iterator b) {
        std::list<Block>::iterator next = b;
        next++;
        if (next == blocks.end()) return;
        for (std::list<int>::const_iterator it = next->l.begin(); it != next->l.end(); it++) {
            b->l.push_back(*it);
            b->sum[*it]++;
        }
        blocks.erase(next);
    }

    inline void split(std::list<Block>::iterator b) {
        std::list<Block>::iterator newBlock = blocks.insert(b, Block());
        for (int i = 0; i < b->l.size() / 2; i++) {
            const int &x = b->l.front();
            newBlock->l.push_back(x);
            newBlock->sum[x]++;
            b->sum[x]--;
            b->l.pop_front();
        }
    }

    inline void maintain() {
        for (std::list<Block>::iterator b = blocks.begin(); b != blocks.end(); b++) {
            if (b->l.size() <= blockSize / 2) mergeNext(b);
            else if (b->l.size() >= blockSize * 2) split(b);
        }
    }

    inline void print() {
        for (std::list<Block>::const_iterator b = blocks.begin(); b != blocks.end(); b++) {
            dprintf("blockSize = %d\n", b->l.size());
        }

        return;
        for (std::list<Block>::const_iterator b = blocks.begin(); b != blocks.end(); b++) {
            for (std::list<int>::const_iterator it = b->l.begin(); it != b->l.end(); it++) {
                dprintf("%d ", *it + 1);
            }
        }
        dprintf("%c", '\n');
    }
} list;

int main() {
    // freopen("array.in", "r", stdin);
    // freopen("array.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]), a[i]--;
    }

    list.build(a, n);

    // list.print();

    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int t, l, r;
        scanf("%d %d %d", &t, &l, &r), l--, r--;
        if (t == 1) {
            int x = list.erase(r);
            list.insert(l, x);
            // list.print();
            list.maintain();
            // list.print();
            // dprintf("%c", '\n');
        } else {
            int k;
            scanf("%d", &k), k--;
            int R = list.query(r, k), L = l == 0 ? 0 : list.query(l - 1, k);
            printf("%d\n", R - L);
        }
    }

    fclose(stdin);
    fclose(stdout);

    // list.print();

    return 0;
}