LOJ6282 数列分块入门6

LOJ6282 数列分块入门 6

标签

• 分块入门

前言

• 这题一次过了~

简明题意

• 维护序列，支持两种操作：
  1. 插入：给第l个元素前插入一个元素
  2. 查询：查询第r个元素的值

思路

• 直接开一个vector[]保存每一块的所有数。对于插入操作，直接找到对应的块，然后对这一块调用vector的insert。对于查询操作，直接把位置偏移过去，然后查询就好了。

• 这题的数据是随机的。如果是构造的，那么可能会多次多同一个块操作，这一块的大小就会变得很大。复杂度就会爆炸了。这里引入了一种叫做重构的思想，一旦发现块的大小\(>2\sqrt{n}\)，那么把这个块一分为二，复杂度是\(O(\frac{n}{\sqrt{n}})\)

  注意事项

• 无

总结

• 无

AC代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

const int maxn = 1e5 + 10;

int n, a[maxn];
int pos[maxn], len;
vector<int> b[maxn];

void change(int l, int r, int c)
{
    int pt = 1, sum = b[1].size();
    while (sum < l) pt++, sum += b[pt].size();

    b[pt].insert(b[pt].begin() + l - (sum - b[pt].size()) - 1, r);
}

int cal(int l, int r, int c)
{
    int pt = 1, sum = b[1].size();
    while (sum < r) pt++, sum += b[pt].size();

    return b[pt][r - (sum - b[pt].size()) - 1];
}

void solve()
{
    scanf("%d", &n);
    len = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]), pos[i] = (i - 1) / len + 1;
        b[pos[i]].push_back(a[i]);
    }

    for (int i = 1; i <= n; i++)
    {
        int opt, l, r, c;
        scanf("%d%d%d%d", &opt, &l, &r, &c);
        if (opt == 0)
            change(l, r, c);
        else
            printf("%d\n", cal(l, r, c));
    }
}

int main()
{
    freopen("Testin.txt", "r", stdin);
    //freopen("Testout.txt", "w", stdout);
    solve();
    return 0;
}

LOJ6282 数列分块入门6

原文：https://www.cnblogs.com/danzh/p/11363110.html