2012-12-31 12:01:07Morris
[ITSA桂冠][n維堆] a574. ITSA2012 桂冠 n維區間查詢
內容 ：
| n維區間查詢 |
Background
由於在賽後無法得到題目描述與測資，小光盡可能地將原本題目描述清楚。
The Problem
什麼是 n 維區間查詢呢？
對於一個資料庫有很多筆 n 維的資料，一筆資料的維度 d，
可以表示成 A[d]，若對於一個 query(L, U) 符合的集合 S
S = {A | L[i] <= A[i] <= U[i], 0<= i < d, A∈Database}
對於每一筆資料求 S 集合的大小。
輸入說明
：
只會有一組測資。
接下來有 N 個 d 維的資料，每個元素以 ',' 逗號隔開。
結束於一行 "-1" 表示。
接著有 Q 個詢問，每組詢問 L, U，以 "-1" 一行為間隔。
數據範圍
N <= 200000, Q < 1000, d = 10
所有資料元素(包含 L, U) E (0 <= E <= 100)
輸出說明
：
對於每組查詢輸出 S 的大小。
範例輸入
：
98,22,82,100,34,58,57,77,55,97 56,52,58,84,54,14,83,87,67,12 27,81,57,2,27,73,20,53,8,78 89,44,3,87,3,64,85,37,9,73 45,88,49,19,73,100,16,72,29,88 94,84,28,94,12,25,37,15,40,92 11,59,92,89,2,87,24,60,39,82 34,46,53,35,2,41,77,92,27,82 60,49,20,75,6,57,0,22,28,54 59,41,78,32,64,37,62,100,47,81 -1 0,11,11,25,0,20,0,11,26,3 84,57,98,71,64,82,78,100,90,86 -1 0,0,0,0,0,0,0,0,0,0 100,100,100,100,100,100,100,100,100,100 -1
範例輸出 ：
2 10
提示
：
出處
：
ITSA 桂冠
(管理：morris1028)
liouzhou_101 >>
#include <stdio.h>liouzhou_101 >>
我認為可以考慮出一些答案很大的詢問，L[i]儘量接近於0，U[i]儘量接近於100，morris1028 >> 我的做法就是那個
這樣可以讓答案很大，可以卡掉O(∑ans)的做法。 另外，我的做法是O(d*N*Q/32)的。
O(∑ans)，我用了十維的二分堆， [2][2][2][2][2][2][2][2][2][2]
#include <vector>
#define piece 51
using namespace std;
inline 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;
}
struct arr {
char e[10];
};
vector<arr> P[2048];
int A[10], B[10], res = 0;
void dfs(int idx, int ptr) {
int i;
if(idx == 10) {
for(vector<arr>::iterator it = P[ptr].begin();
it != P[ptr].end(); it++) {
for(i = 0; i < 10; i++) {
if(!(A[i] <= it->e[i] && it->e[i] <= B[i]))
break;
}
if(i == 10)
res++;
}
return;
}
int l = A[idx]/piece, r = B[idx]/piece;
for(i = l; i <= r; i++) {
dfs(idx+1, (ptr<<1) + i);
}
}
int main() {
int x, idx = 0, i, j;
arr D;
int ptr;
while(1) {
ReadInt(&x);
if(x == -1) break;
D.e[0] = x;
ptr = x/piece;
for(i = 1; i < 10; i++) {
ReadInt(&x);
D.e[i] = x;
//if(i < 3)
ptr = (ptr<<1) + x/piece;
}
P[ptr].push_back(D);
idx++;
}
while(ReadInt(&x)) {
if(x == -1) break;
A[0] = x;
for(i = 1; i < 10; i++) {
ReadInt(&x);
A[i] = x;
}
for(i = 0; i < 10; i++) {
ReadInt(&x);
B[i] = x;
}
ReadInt(&x);
res = 0;
dfs(0, 0);
printf("%d\n", res);
}
return 0;
}