[ITSA桂冠][n維堆] a574. ITSA2012 桂冠 n維區間查詢＠Morris' Blog

2012-12-31 12:01:07| 人氣894| 回應0 | 上一篇 | 下一篇

[ITSA桂冠][n維堆] a574. ITSA2012 桂冠 n維區間查詢

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 的大小。

範例輸入： help

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 >>

我認為可以考慮出一些答案很大的詢問，L[i]儘量接近於0，U[i]儘量接近於100，
這樣可以讓答案很大，可以卡掉O(∑ans)的做法。

另外，我的做法是O(d*N*Q/32)的。

morris1028 >> 我的做法就是那個

O(∑ans)，我用了十維的二分堆， [2][2][2][2][2][2][2][2][2][2]

#include <stdio.h>
#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;
}

我要檢舉

#a574#ITSA2012 桂冠 n維區間查詢

台長： Morris

您可能對以下文章有興趣

a121. 質數又來囉

[ZJ][BIT+掃描線] a457. TOI2010 第五題：餐廳評鑑

d985. Gran Turismo 5

d639. 企鵝村三兄弟penguin

人氣(894) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][線段樹][懶操作] a126. NOI2004 Day1.1.郁闷的出纳员
此分類上一篇:[ITSA桂冠][方格法] a573. ITSA2012 桂冠元件計算

回應(0)