块状数组

Posted on 2012-01-17 20:31 Mato_No1 阅读(1048) 评论(2)  编辑 收藏 引用 所属分类: 其它高级数据结构

例题
本沙茶觉得块状数组又好写又有用(其实就是另一种朴素)……只是那个O(sqrt(n))的复杂度比较大而已(其实如果加上常数的话它并不比Segplaytree慢多少)
编程技巧:
(1)每块长度设为m=floor(sqrt(n)),最后不足长度的不补值,设n0为总块数(显然n0=(n-1)/m+1);
(2)设立LEN[i]=第i块的实际长度(显然除了最后一块都是m),可以在建立块状数组(真正搞成块状,也就是二维)的时候得到;
(3)对于区间[l, r],要注意:<1>l、r位于同一块(l/m==r/m)的情况;<2>r位于最后一块的情况;
(4)别忘了同时更新原数组与块状数组;

另外,本例题需要二分+找多少个比它小的这样的操作,总时间复杂度是O(N*sqrt(N)*log2N*log2N)(幸亏N只有10000……)。

如果有插入删除元素,就需要用动态的块状链表了……极其难搞,本沙茶不敢试了……遇到这种题还是写Segplaytree吧囧……

#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
#include 
<math.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
const int MAXN = 100002, MAXM = 320, INF = ~0U >> 2;
int n, m, n0, A[MAXN], T[MAXM][MAXM], LEN[MAXM], res;
int cmp(const void *s1, const void *s2)
{
    
return *(int *)s1 - *(int *)s2;
}
void prepare()
{
    m 
= (int) floor(sqrt(n) + 1e-7); n0 = (n - 1/ m + 1; re(i, n0) LEN[i] = 0;
    re(i, n) T[i 
/ m][LEN[i / m]++= A[i];
    re(i, n0) qsort(T[i], LEN[i], 
sizeof(int), cmp);
}
void opr0(int No, int x)
{
    A[No] 
= x; int S = No / m; re(i, LEN[S]) T[S][i] = A[S * m + i]; qsort(T[S], LEN[S], sizeof(int), cmp);
}
int opr1(int l, int r, int x)
{
    
int S0 = l / m, l0 = l % m, S1 = r / m, r0 = r % m, l1, r1, mid, res0 = 0;
    
if (S0 == S1) re3(i, l0, r0) {if (A[S0 * m + i] < x) res0++;} else {
        re2(i, l0, LEN[S0]) 
if (A[S0 * m + i] < x) res0++;
        re3(i, 
0, r0) if (A[S1 * m + i] < x) res0++;
        re2(i, S0
+1, S1) {
            l1 
= 0; r1 = LEN[i];
            
while (l1 < r1) {
                mid 
= l1 + r1 >> 1;
                
if (T[i][mid] >= x) r1 = mid; else l1 = mid + 1;
            }
            res0 
+= l1;
        }
    }
    
return res0;
}
int main()
{
    
int M, a0, b0, x0, l, r, mid; char ss[20];
    scanf(
"%d%d"&n, &M);
    re(i, n) scanf(
"%d"&A[i]); prepare();
    re(i, M) {
        scanf(
"%s", ss);
        
if (ss[0== 'C') {
            scanf(
"%d%d"&a0, &x0); opr0(--a0, x0);
        } 
else {
            scanf(
"%d%d%d"&a0, &b0, &x0); a0--; b0--;
            l 
= 0; r = 1000000000;
            
while (l < r) {
                mid 
= l + r + 1 >> 1;
                
if (opr1(a0, b0, mid) < x0) l = mid; else r = mid - 1;
            }
            printf(
"%d\n", l);
        }
    }
    
return 0;
}



 

Feedback

# re: 块状数组  回复  更多评论   

2013-05-25 20:57 by mato
求什么是Segplaytree

# re: 块状数组  回复  更多评论   

2013-05-29 16:57 by Mato_No1
LS不要山寨……
Segplaytree就是用来当Segtree的Splaytree。

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理