有一个长度为 的数列，支持以下两种操作：
- 将 移动到 的前面；
- 查询 中 的出现次数。
题解
将序列按照 分块，维护块状链表，将每次修改转化为一次插入一次删除，每个块记录每个数出现次数。
每次查询时，将 的答案转化为 的答案减去 的答案。对于块内部分直接查询，块外部分暴力。
时间复杂度、空间复杂度均为 。
代码
#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;
}