POJ2104 K-th Number 靜態區間第k最值 平方分割，poj2104k-th
干掉這道題的那一刻，我只想說：我終於**的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 }
View Code
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
這道題更好的做法是歸並樹，比歸並樹還好的做法是劃分樹，不過這都是後話了，有時間慢慢填坑
