2012-10-17 19:54:17Morris
[ZJ][塊狀表] d476. 区间查询
內容 ：
一个长度为n的序列，支持两种操作：
1.输出[A, B]区间第k小的数(从小到大排序后第k个)
2.修改第I个数为W
輸入說明 ：
第二行N个数A[I](1<=A[I]<=1000000000)
以下M行，每行一个操作
Q i j k（查询[I,J]中第k小的数）或 C i W(把第I个数改成W）
以下M行，每行一个操作
Q i j k（查询[I,J]中第k小的数）或 C i W(把第I个数改成W）
輸出說明 ：
对于每个查询操作，输出每个查询结果
範例輸入 ：
5 3
1 2 3 4 5
Q 1 4 2
C 2 5
Q 1 4 2
範例輸出 ：
2
3
提示 ：
经典题目
出處 ：
vijos (管理：vijos_car)
寫完這題我發現我需要鍛煉二分，因為不想用太多的 IF，所以在二分的終止條件就相當的困難。
題解位址
1. 操作調查是 O(sqrt(n) * log(sqrt(n)))。
2. 切成 sqrt(n) 塊，每個使用插入排序法。
3. 記錄 1 1 2 3 3 中的 3 排名時，答案是 5
4. 對於區間[i, j], 設答案為 k, 暴力尋遍i,j所處"不完整的塊"的, 接著二分搜其中完整的塊。
#include <cstdio>
#include <algorithm>
#define oo 0xfffffff
using namespace std;
const int SIZE = 256;
int A[SIZE*SIZE];
int p[SIZE][SIZE];
int getIdx(int pd, int v) {
static int l, r, m;
l = 0, r = SIZE-1;
while(l <= r) {
m = (l+r)>>1;
if(p[pd][m] == v)
return m;
if(p[pd][m] < v)
l = m+1;
else
r = m-1;
}
return -1;
}
int getRank(int x, int y, int k) {
int s = 0, l, r, m;
while(x%SIZE && x <= y) {
if(A[x] <= k) s++;
x++;
}
while((y+1)%SIZE && x <= y) {
if(A[y] <= k) s++;
y--;
}
if(x > y) return s;
x /= SIZE, y /= SIZE;
while(x <= y) {
l = 0, r = SIZE-1, m;
while(l < r) {
m = (l+r+1)>>1;
if(p[x][m] <= k)
l = m;
else
r = m-1;
}
if(p[x][l] > k) l--;
s += l+1;
x++;
}
return s;
}
int main() {
int n, q, i, j, k, d, idx;
char cmd[3];
while(scanf("%d %d", &n, &q) == 2) {
for(i = 0; i < SIZE; i++)
p[(n-1)/SIZE][i] = oo;
for(i = 0; i < n; i++)
scanf("%d", A+i), p[i/SIZE][i%SIZE] = A[i];
for(i = (n-1)/SIZE; i >= 0; i--)
sort(p[i], p[i]+SIZE);
while(q--) {
scanf("%s", cmd);
if(cmd[0] == 'C') {
scanf("%d %d", &i, &k), i--;
d = i/SIZE, idx = getIdx(d, A[i]);
while(idx < SIZE)
p[d][idx] = p[d][idx+1], idx++;
idx = SIZE-2;
while(idx >= 0 && k < p[d][idx])
p[d][idx+1] = p[d][idx], idx--;
p[d][idx+1] = k, A[i] = k;
} else {
scanf("%d %d %d", &i, &j, &k), i--, j--;
int l = 0, r = 1000000000, m;
while(l < r) {
m = (l+r+1)>>1;
if(getRank(i, j, m) >= k)
r = m-1;
else
l = m;
}
printf("%d\n", r+1);
}
}
}
return 0;
}
寫完這題我發現我需要鍛煉二分，因為不想用太多的 IF，所以在二分的終止條件就相當的困難。
題解位址
1. 操作調查是 O(sqrt(n) * log(sqrt(n)))。
2. 切成 sqrt(n) 塊，每個使用插入排序法。
3. 記錄 1 1 2 3 3 中的 3 排名時，答案是 5
4. 對於區間[i, j], 設答案為 k, 暴力尋遍i,j所處"不完整的塊"的, 接著二分搜其中完整的塊。
#include <cstdio>
#include <algorithm>
#define oo 0xfffffff
using namespace std;
const int SIZE = 256;
int A[SIZE*SIZE];
int p[SIZE][SIZE];
int getIdx(int pd, int v) {
static int l, r, m;
l = 0, r = SIZE-1;
while(l <= r) {
m = (l+r)>>1;
if(p[pd][m] == v)
return m;
if(p[pd][m] < v)
l = m+1;
else
r = m-1;
}
return -1;
}
int getRank(int x, int y, int k) {
int s = 0, l, r, m;
while(x%SIZE && x <= y) {
if(A[x] <= k) s++;
x++;
}
while((y+1)%SIZE && x <= y) {
if(A[y] <= k) s++;
y--;
}
if(x > y) return s;
x /= SIZE, y /= SIZE;
while(x <= y) {
l = 0, r = SIZE-1, m;
while(l < r) {
m = (l+r+1)>>1;
if(p[x][m] <= k)
l = m;
else
r = m-1;
}
if(p[x][l] > k) l--;
s += l+1;
x++;
}
return s;
}
int main() {
int n, q, i, j, k, d, idx;
char cmd[3];
while(scanf("%d %d", &n, &q) == 2) {
for(i = 0; i < SIZE; i++)
p[(n-1)/SIZE][i] = oo;
for(i = 0; i < n; i++)
scanf("%d", A+i), p[i/SIZE][i%SIZE] = A[i];
for(i = (n-1)/SIZE; i >= 0; i--)
sort(p[i], p[i]+SIZE);
while(q--) {
scanf("%s", cmd);
if(cmd[0] == 'C') {
scanf("%d %d", &i, &k), i--;
d = i/SIZE, idx = getIdx(d, A[i]);
while(idx < SIZE)
p[d][idx] = p[d][idx+1], idx++;
idx = SIZE-2;
while(idx >= 0 && k < p[d][idx])
p[d][idx+1] = p[d][idx], idx--;
p[d][idx+1] = k, A[i] = k;
} else {
scanf("%d %d %d", &i, &j, &k), i--, j--;
int l = 0, r = 1000000000, m;
while(l < r) {
m = (l+r+1)>>1;
if(getRank(i, j, m) >= k)
r = m-1;
else
l = m;
}
printf("%d\n", r+1);
}
}
}
return 0;
}