POJ2104 K-th Number 靜態區間第k最值 平方分割

幹掉這道題的那一刻，我只想說：我終於**的AC了！！！

最終記憶體1344K，耗時10282ms，比起歸併樹、劃分樹以及其他各種黑科技，這個成績並不算光彩⊙﹏⊙

但至少，從最初的無數次TLE到最終的AC，這過程見證了一個二分演算法的艱辛優化

先貼代碼：

 1 const int bktSize=1024;
 2 const int bktMaxIdx=bktSize-1;
 3 const int bktCount=128;
 4 const int bktDigit=10;
 5 const int maxV=1e9;
 6 
 7 int bucket[bktCount][bktSize];
 8 int unOrdered[bktSize*bktCount];
 9 int ordered[bktSize*bktCount];
10 int N,K;
11 
12 #include <cstdio>
13 #include <cstring>
14 #include <algorithm>
15 
16 void init()
17 {
18     scanf("%d%d",&N,&K);
19     memset(bucket[N>>bktDigit],0x7f,sizeof(bucket[N>>bktDigit]));
20     for(int i=0;i<N;i++) 
21     {
22         scanf("%d",unOrdered+i);
23         ordered[i]=unOrdered[i];
24         bucket[i>>bktDigit][i&bktMaxIdx]=unOrdered[i];
25     }
26     
27     using std::sort;
28     int bktUsed=N>>bktDigit;
29     sort(ordered,ordered+N);
30     for(int i=0;i<=bktUsed;i++) sort(bucket[i],bucket[i]+bktSize);
31 }
32 
33 inline void enumerate(int _rangeL,int _rangeR,int _val,int& _notMore)
34 {
35     for(int i=_rangeL;i<=_rangeR;i++)
36         if(unOrdered[i]<=_val) ++_notMore;
37 }
38 
39 inline void countBucket(int _bktIdx,int _val,int& _notMore)
40 {
41     using std::upper_bound;
42     
43     int* ub=upper_bound(bucket[_bktIdx],bucket[_bktIdx]+bktSize,_val);
44     _notMore+=(ub-bucket[_bktIdx]);
45 }
46 
47 int ask(int _rangeL,int _rangeR,int _k) //k-th smallest
48 {
49     int digitL=_rangeL>>bktDigit;
50     int digitR=_rangeR>>bktDigit;
51     int vL=0;
52     int vR=N-1;
53     
54     while(vL<vR)
55     {
56         int midV=(vL+vR)>>1;
57         int notMore=0;
58         if(digitL==digitR) 
59             enumerate(_rangeL,_rangeR,ordered[midV],notMore);
60         else
61         {
62             for(int i=digitL+1;i<digitR;i++)
63                 countBucket(i,ordered[midV],notMore);
64             enumerate(_rangeL,((digitL+1)<<bktDigit)-1,ordered[midV],notMore);
65             enumerate(digitR<<bktDigit,_rangeR,ordered[midV],notMore);
66         }
67         
68         if(notMore<_k) vL=midV+1;
69         else vR=midV;
70     }
71     return ordered[vL];
72 }
73 
74 int main()
75 {
76     init();
77     for(int i=0;i<K;i++)
78     {
79         int l,r,k;
80         scanf("%d%d%d",&l,&r,&k);
81         printf("%d\n",ask(l-1,r-1,k));    
82     }
83     return 0;
84 }

1、為什麼統計notMore，而不是統計less或者兩者都統計？

二分的過程中，縮減區間的關鍵是：

1、必須使可能成為最終解的值保留在二分區間中

2、每一次都必須使區間大小的確被縮減，以防陷入死迴圈

在這道題中，某個值x為解的條件是：less(x)<x && notMore(x)>=x

如果統計Less的話，上面的代碼很難是保證第一條的

而如果兩者都統計的話，錶面上當x滿足條件時即可跳出，可以減少二分所需的時間

但是事實上，這樣做的代價就是統計的時間複雜度常數乘以2，總的來說得不償失（會TLE）

2、二分的對象是什麼？可否把maxValue和minValue作為二分的對象？

Answer：NO！！！

正確的做法是將原數組排好序，然後對這個有序數組二分

理由很簡單：範圍小。二分區間長不會超過1e5

如果對數值本身二分的話，minValue和maxValue最壞時分別會達到-1e9和+1e9，二分的時間代價是前者的1.9倍

3、平方分割必須是嚴格的麽？

Answer：NO(*^__^*)

設數據規模為N，每個桶的大小為B，則單次詢問的時間複雜度為： O ( (N / B ) * log B + B )

當B = O ( ( N * log N ) ^ 0.5 ) 時，總的時間複雜度會比嚴格的平方分割小一些

代碼中將B取為了1024正是為此。（順便也方便了位運算）

B取512時效率會相對變差，B取256時乾脆TLE

這道題更好的做法是歸併樹，比歸併樹還好的做法是劃分樹，不過這都是後話了，有時間慢慢填坑