2012-12-08 12:35:24Morris
[ZJ][zkw線段樹] d801. SCOI2006 2.动态最值(minmax)
內容 ：
有一个包含n个元素的数组，要求实现以下操作：DELETE k：删除位置k上的数。右边的数往左移一个位置。QUERY i j：查询位置i~j上所有数的最小值和最大值。例如有10个元素：
QUERY 2 8的结果为2 9。依次执行DELETE 3和DELETE 6（注意这时删除的是原始数组的元素7）后数组变为：
QUERY 2 8的结果为1 7。
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 元素 | 1 | 5 | 2 | 6 | 7 | 4 | 9 | 3 | 1 | 5 |
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 元素 | 1 | 5 | 6 | 7 | 4 | 3 | 1 | 5 |
輸入說明
：
第一行包含两个数n, m，表示原始数组的元素个数和操作的个数。第二行包括n个数，表示原始数组。以下m行，每行格式为1 k或者2 i j，其中第一个数为1表示删除操作，为2表示询问操作。
輸出說明
：
对每个询问操作输出一行，包括两个数，表示该范围内的最小值和最大值。
範例輸入
：
若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。
10 4 1 5 2 6 7 4 9 3 1 5 2 2 8 1 3 1 6 2 2 8
範例輸出 ：
2 9 1 7
提示
：
50%的数据满足1<=n, m<=104，删除操作不超过100个100%的数据满足1<=n, m<=106, 1<=m<=106对于所有的数据，数组中的元素绝对值均不超过109
//这题是SCOI(四川)2006的第二题，时间限制是每组测试数据5s，还是遵循原来的限制吧，不过时间有点紧。
//由于原测试数据一共有10组，这里只取最大的那一组。
出處
：
SCOI2006 第二题
(管理：liouzhou_101)
總共需要兩棵線段樹去維護。
一個線段樹是要維護最大最小值的查詢，令一個維護的是紀錄實際應該查找的區間。
一開始很傻的用 BIT 去維護，但是後來想是想錯了，那個複雜度是 O(logN*logN)。
O(logN) 的查找會是錯誤的。
#include <stdio.h>
#include <algorithm>
#define INF 200000000
using namespace std;
struct ND {
int mx, mn;
} ST[1<<21|1];
int M, ST2[1<<21|1];
void setST(int n) {
int i;
for(i = 2*M-1; i > 0; i--) {
ST[i].mx = -INF;
ST[i].mn = INF;
if(i >= M)
ST2[i] = 1;
else
ST2[i] = ST2[i<<1]+ST2[i<<1|1];
}
}
void modify(int x, int nv, int xv) {
ST[x+M].mx = xv;
ST[x+M].mn = nv;
x = x+M;
for(x >>= 1; x > 0; x >>= 1) {
ST[x].mn = min(ST[x<<1].mn, ST[x<<1|1].mn);
ST[x].mx = max(ST[x<<1].mx, ST[x<<1|1].mx);
}
}
void query(int& s, int& t) {
static int i;
static ND ans;
ans.mn = INF, ans.mx = -INF;
for(s = s+M-1, t = t+M+1; (s^t) != 1;) {
if(~s&1) {
ans.mn = min(ans.mn, ST[s^1].mn);
ans.mx = max(ans.mx, ST[s^1].mx);
}
if(t&1) {
ans.mn = min(ans.mn, ST[t^1].mn);
ans.mx = max(ans.mx, ST[t^1].mx);
}
s >>= 1, t >>= 1;
}
printf("%d %d\n", ans.mn, ans.mx);
}
int getIdx(int idx) {
static int s;
for(s = 1; s < M;) {
if(ST2[s<<1] < idx)
idx -= ST2[s<<1], s = s<<1|1;
else
s = s<<1;
}
return s-M+1;
}
void delIdx(int idx) {
idx = idx+M-1;
while(idx)
ST2[idx]--, idx >>= 1;
}
int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int n, m, i, j, sum;
int I, J, c, A;
while(scanf("%d %d", &n, &m) == 2) {
for(M = 1; M < n+2; M <<= 1);
setST(n);
for(i = 1; i <= n; i++) {
ReadInt(&A);
modify(i, A, A);
}
while(m--) {
ReadInt(&c);
ReadInt(&I);
if(c == 1) {
I = getIdx(I);
modify(I, INF, -INF);
delIdx(I);
} else {
ReadInt(&J);
I = getIdx(I);
J = getIdx(J);
query(I, J);
}
}
}
return 0;
}
總共需要兩棵線段樹去維護。
一個線段樹是要維護最大最小值的查詢，令一個維護的是紀錄實際應該查找的區間。
一開始很傻的用 BIT 去維護，但是後來想是想錯了，那個複雜度是 O(logN*logN)。
O(logN) 的查找會是錯誤的。
#include <stdio.h>
#include <algorithm>
#define INF 200000000
using namespace std;
struct ND {
int mx, mn;
} ST[1<<21|1];
int M, ST2[1<<21|1];
void setST(int n) {
int i;
for(i = 2*M-1; i > 0; i--) {
ST[i].mx = -INF;
ST[i].mn = INF;
if(i >= M)
ST2[i] = 1;
else
ST2[i] = ST2[i<<1]+ST2[i<<1|1];
}
}
void modify(int x, int nv, int xv) {
ST[x+M].mx = xv;
ST[x+M].mn = nv;
x = x+M;
for(x >>= 1; x > 0; x >>= 1) {
ST[x].mn = min(ST[x<<1].mn, ST[x<<1|1].mn);
ST[x].mx = max(ST[x<<1].mx, ST[x<<1|1].mx);
}
}
void query(int& s, int& t) {
static int i;
static ND ans;
ans.mn = INF, ans.mx = -INF;
for(s = s+M-1, t = t+M+1; (s^t) != 1;) {
if(~s&1) {
ans.mn = min(ans.mn, ST[s^1].mn);
ans.mx = max(ans.mx, ST[s^1].mx);
}
if(t&1) {
ans.mn = min(ans.mn, ST[t^1].mn);
ans.mx = max(ans.mx, ST[t^1].mx);
}
s >>= 1, t >>= 1;
}
printf("%d %d\n", ans.mn, ans.mx);
}
int getIdx(int idx) {
static int s;
for(s = 1; s < M;) {
if(ST2[s<<1] < idx)
idx -= ST2[s<<1], s = s<<1|1;
else
s = s<<1;
}
return s-M+1;
}
void delIdx(int idx) {
idx = idx+M-1;
while(idx)
ST2[idx]--, idx >>= 1;
}
int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int n, m, i, j, sum;
int I, J, c, A;
while(scanf("%d %d", &n, &m) == 2) {
for(M = 1; M < n+2; M <<= 1);
setST(n);
for(i = 1; i <= n; i++) {
ReadInt(&A);
modify(i, A, A);
}
while(m--) {
ReadInt(&c);
ReadInt(&I);
if(c == 1) {
I = getIdx(I);
modify(I, INF, -INF);
delIdx(I);
} else {
ReadInt(&J);
I = getIdx(I);
J = getIdx(J);
query(I, J);
}
}
}
return 0;
}
前幾天才看到 zkw線段樹 wwwww
競賽這回事越來越神了