生活随笔
收集整理的這篇文章主要介紹了
块状数组
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
例題
本沙茶覺得塊狀數組又好寫又有用（其實就是另一種樸素）……只是那個O(sqrt(n))的復雜度比較大而已（其實如果加上常數的話它并不比Segplaytree慢多少）
編程技巧：
（1）每塊長度設為m=floor(sqrt(n))，最后不足長度的不補值，設n0為總塊數（顯然n0=(n-1)/m+1）；
（2）設立LEN[i]=第i塊的實際長度（顯然除了最后一塊都是m），可以在建立塊狀數組（真正搞成塊狀，也就是二維）的時候得到；
（3）對于區(qū)間[l, r]，要注意：<1>l、r位于同一塊（l/m==r/m）的情況；<2>r位于最后一塊的情況；
（4）別忘了同時更新原數組與塊狀數組；
另外，本例題需要二分+找多少個比它小的這樣的操作，總時間復雜度是O(N*sqrt(N)*log
2N*log
2N)（幸虧N只有10000……）。
如果有插入刪除元素，就需要用動態(tài)的塊狀鏈表了……極其難搞，本沙茶不敢試了……遇到這種題還是寫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;
}
總結
以上是生活随笔為你收集整理的块状数组的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
