6
题意
给出一个长为\(n\)的数列，以及\(n\)个操作，操作涉及单点插入，单点询问，数据随机生成。
题解
每个块内用一个\(vector\)维护，每次插入时先找到位置所在的块，再暴力插入。
如果数据不随机，即如果先在一个块有大量单点插入，这个块的大小会大大超过\(\sqrt n\)，那块内的暴力就没有复杂度保证了。
为此引入一个操作：重新分块（重构）
每\(\sqrt n\)次插入后，重新把数列平均分一下块，重构需要的复杂度为\(O(n)\)，重构的次数为\(\sqrt n\)，所以重构的复杂度没有问题，而且保证了每个块的大小相对均衡。
当然，也可以当某个块过大时重构，或者只把这个块分成两半。
// 代码中采取的是当块过大时进行重构。
Code
#include <bits/stdc++.h>
#define maxn 200010
#define C 20
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
int n, blo, a[maxn], num;
vector<int> v[510];
struct node { int bl, p; };
node query(int p) {
int i=0;
while (p>v[i].size()) p -= v[i++].size();
return {i, p-1};
}
void rebuild() {
int cnt=0;
F(i, 0, num) {
for (auto x : v[i]) a[cnt++] = x;
v[i].clear();
}
blo = sqrt(cnt); num = (cnt+blo-1)/blo;
F(i, 0, cnt) v[i/blo].push_back(a[i]);
}
void insert(int p, int x) {
node nd = query(p);
v[nd.bl].insert(v[nd.bl].begin()+nd.p, x);
if (v[nd.bl].size()>C*blo) rebuild();
}
int main() {
scanf("%d", &n); blo = sqrt(n);
F(i, 0, n) {
scanf("%d", &a[i]);
v[i/blo].push_back(a[i]);
}
num = (n+blo-1)/blo;
F(i, 0, n) {
int op, l, r, c;
scanf("%d%d%d%d", &op, &l, &r, &c);
if (op) {
node nd = query(r);
printf("%d\n", v[nd.bl][nd.p]);
}
else insert(l, r);
}
return 0;
}9
题意
给出一个长为\(n\)的数列，以及\(n\)个操作，操作涉及询问区间的最小众数。
题解
离散化。
对每一个数开一个桶，即对每个数用一个\(vector\)按序记录它所有的出现位置。
预处理出\(f[s][t]\)表示第\(s\)块到第\(t\)块的最小众数：
方法是：枚举\(s\)，向右扫，每扫一个块得到一个值。
复杂度：\(\sqrt n*\sqrt n+(\sqrt n-1)*\sqrt n+\cdots+2*\sqrt n+\sqrt n=\sqrt n*(1+2+\cdots+\sqrt n)=O(n\sqrt n)\)对于一个询问\([l,r]\)：
不完整的块中共有\(2\sqrt n\)个数，完整的块根据3. 中的预处理得到一个数。
暴力比较这\(2\sqrt n+1\)个数的出现次数，
方法是：要知道\(x\)在\([l,r]\)中的出现次数，只需在\(vector[x]\)中进行二分查找。
复杂度：\(O(\sqrt n*logn)\)
Code
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 100010
#define inf 0x3f3f3f3f
using namespace std;
int cnt[maxn], a[maxn], n, num, blo, f[1010][1010], bl[maxn], mp2[maxn];
map<int, int> mp;
vector<int> v[maxn];
typedef long long LL;
inline void update(int temp, int& maxx, int x, int& ans) {
if (temp>maxx || (temp==maxx&&mp2[x]<mp2[ans])) {
maxx = temp, ans = x;
}
}
void pre(int s) {
memset(cnt, 0, sizeof cnt);
int ans = -inf, maxx = 0;
F(i, s, num) {
F(j, i*blo, min((i+1)*blo, n)) {
++cnt[a[j]];
update(cnt[a[j]], maxx, a[j], ans);
}
f[s][i] = ans;
}
}
inline int count(int l, int r, int x) {
return upper_bound(v[x].begin(), v[x].end(), r)-upper_bound(v[x].begin(), v[x].end(), l-1);
}
int query(int l, int r) {
int ans = -inf, maxx = 0;
F(i, l, min(r+1, (bl[l]+1)*blo)) {
int temp = count(l, r, a[i]);
update(temp, maxx, a[i], ans);
}
if (bl[l]!=bl[r]) {
F2(i, bl[r]*blo, r) {
int temp = count(l, r, a[i]);
update(temp, maxx, a[i], ans);
}
}
if (bl[l]+1<=bl[r]-1) {
int x = f[bl[l]+1][bl[r]-1];
int temp = count(l, r, x);
update(temp, maxx, x, ans);
}
return ans;
}
int main() {
scanf("%d", &n); blo = sqrt(n);
int tot=0;
F(i, 0, n) {
scanf("%d", &a[i]);
if (!mp[a[i]]) {
mp[a[i]] = ++tot;
mp2[tot] = a[i];
}
bl[i] = i/blo;
v[a[i]=mp[a[i]]].push_back(i);
}
num = bl[n-1]+1;
F(i, 0, num) pre(i);
F(i, 0, n) {
int l, r;
scanf("%d%d", &l, &r); --l, --r;
printf("%d\n", mp2[query(l, r)]);
}
return 0;
}