POJ2104：分桶法与平方分割

分桶法是把一排数据或者是一个平面分成很多个桶，每个桶维护自己内部的信息。平方分割是把n个元素，按照每√n个分为一个桶的做法。

基于平方分割的RMQ
给定一个数列a1,a2,…,an,目标是在O(根号n)复杂度内实现两个功能

给定s，t，求as,as+1,…,at的最小值

给定t, x,把ai的值变为x.

基于平方分割RMQ的预处理
令b=floor(√n),把a中的元素每b分成一个桶，并且计算出每个桶内的最小值。

2、基于平方分割的RMQ的查询

如果桶完全包含在区间内，则查询桶的最小值
如果元素所在的桶不完全被区间包含，则逐个检查最小值

基于平方分割的RMQ的值的更新
在更新元素的值时，需要更新该元素所在的桶的最小值。这时只要遍历一遍桶内的元素就可以了。

3、基于平方分割的RMQ的时间复杂度
在更新值时，因为每个桶内有b个元素，所以时间复杂度是O（b）。
而在查询时

完全包含在区间内的桶的个数是O(n/b)
所在的桶不被区间完全包含的元素个数是O(b)
因为设b=√n，则操作的时间复杂度是
O(n/b+b)=O(√n+√n)=O(√n);

平方分割和线段树
因此，在平方分割中，对于任意区间，完全包含于其中的桶的数量和剩余元素的数量都是O(√n)，所以可以在O(√n)时间内完成各种操作。
在上面的RMQ的例题中，线段树进行各种操作的复杂度是O(logn)，比平方分割更快一些。一般地，如果线段树和平方分割都能实现某个功能，多数情况下线段树会比平方分割快。但是，因为平方分割在实现上比线段树简单，所以如果运行时间限制不是太紧时，也可以考虑使用平方分割。除此之外，也有一些功能是线段树无法高效维护但是平方分割却可以做到的。

题目：POJ2104

（下面的代码应该是poj太垃圾，所以TLE了…）

半夜十一点五十分，估摸着poj没人在用了，交一发，选择G++编译器，然后，AC了…

#pragma GCC optimize("O3")
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;
typedef long long ll;
#define MAXN 100005

int n, m;
int a[MAXN], num[MAXN];

const int b_size = 1000;
vector<int> bucket[MAXN / b_size + 2];


inline int read(){
    register int x = 0, t = 1;
    register char ch=getchar(); // 读入单个字符到寄存器
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);  // 移位与异或
      	// 第十行可以换成 x = x * 10 + ch - '0'
        ch=getchar();
    }
    return x*t;
}

inline void solve()
{
    for (int i = 0; i < n; ++i)
    {
        bucket[i / b_size].push_back(a[i]);
        num[i] = a[i];
    }

    //memcpy(num, a, sizeof(a));

    sort(num, num + n);

    int bnum = n / b_size + 1;
    for (int i = 0; i <= bnum; ++i)
        sort(bucket[i].begin(), bucket[i].end());

    int l, r, k;
    while (m--)
    {
        l=read();
        r = read();
        k = read();
        //scanf("%d%d%d", &l, &r, &k);
        int lb = -1, rb = n;
        --l;
        while (lb + 1 < rb)
        {
            int mid = (lb + rb) >> 1;
            int x = num[mid];

            //c为区间中有多少数小于x
            int tl = l, tr = r, c = 0;

            //计算x在两边不在一个桶中的次序
            while (tl < tr && tl % b_size != 0)
                if (a[tl++] <= x)
                    ++c;
            while (tl < tr && tr % b_size != 0)
                if (a[--tr] <= x)
                    ++c;

            while (tl < tr)
            {
                int bb = tl / b_size;
                c += upper_bound(bucket[bb].begin(), bucket[bb].end(), x) - bucket[bb].begin();
                tl += b_size;
            }

            if (c >= k)
            {
                //x过大
                rb = mid;
            }
            else
                lb = mid;
        }
        printf("%d\n", num[rb]);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        //scanf("%d", &a[i]);
        a[i]=read();
    solve();

    return 0;
}

转载请注明来源：https://www.longjin666.top/?p=1213

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~