例題
本沙茶覺得塊狀數(shù)組又好寫又有用（其實就是另一種樸素）……只是那個O(sqrt(n))的復(fù)雜度比較大而已（其實如果加上常數(shù)的話它并不比Segplaytree慢多少）
編程技巧：
（1）每塊長度設(shè)為m=floor(sqrt(n))，最后不足長度的不補(bǔ)值，設(shè)n0為總塊數(shù)（顯然n0=(n-1)/m+1）；
（2）設(shè)立LEN[i]=第i塊的實際長度（顯然除了最后一塊都是m），可以在建立塊狀數(shù)組（真正搞成塊狀，也就是二維）的時候得到；
（3）對于區(qū)間[l, r]，要注意：<1>l、r位于同一塊（l/m==r/m）的情況；<2>r位于最后一塊的情況；
（4）別忘了同時更新原數(shù)組與塊狀數(shù)組；
另外，本例題需要二分+找多少個比它小的這樣的操作，總時間復(fù)雜度是O(N*sqrt(N)*log2N*log2N)（幸虧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;
}