分桶法是把一排数据或者是一个平面分成很多个桶,每个桶维护自己内部的信息。平方分割是把n个元素,按照每√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)。 而在查询时
题目: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;
}