6

题意

给出一个长为\(n\)的数列，以及\(n\)个操作，操作涉及单点插入，单点询问，数据随机生成。

题解

参考：http://hzwer.com/8053.html

每个块内用一个\(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\)个操作，操作涉及询问区间的最小众数。

题解

参考：http://hzwer.com/3582.html

离散化。
对每一个数开一个桶，即对每个数用一个\(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;

}

巴特西

loj 数列分块入门 6 9(区间众数)

6

题意

题解

Code

9

题意

题解

Code

最新文章

热门文章