POJ2104 K-th Number 静态区间第k最值 平方分割

时间：2022-09-07 08:28:45

干掉这道题的那一刻，我只想说：我终于**的AC了！！！

最终内存1344K，耗时10282ms，比起归并树、划分树以及其他各种黑科技，这个成绩并不算光彩⊙﹏⊙

但至少，从最初的无数次TLE到最终的AC，这过程见证了一个二分算法的艰辛优化

感谢国家，感谢XXTV，感谢《挑战程序设计竞赛》~(￣▽￣)~*

先贴代码：

 ;
 ;
 ;
 ;
 const int maxV=1e9;

 int bucket[bktCount][bktSize];
 int unOrdered[bktSize*bktCount];
 int ordered[bktSize*bktCount];
 int N,K;

 #include <cstdio>
 #include <cstring>
 #include <algorithm>

 void init()
 {
     scanf("%d%d",&N,&K);
     memset(bucket[N>>bktDigit],0x7f,sizeof(bucket[N>>bktDigit]));
     ;i<N;i++)
     {
         scanf("%d",unOrdered+i);
         ordered[i]=unOrdered[i];
         bucket[i>>bktDigit][i&bktMaxIdx]=unOrdered[i];
     }

     using std::sort;
     int bktUsed=N>>bktDigit;
     sort(ordered,ordered+N);
     ;i<=bktUsed;i++) sort(bucket[i],bucket[i]+bktSize);
 }

 inline void enumerate(int _rangeL,int _rangeR,int _val,int& _notMore)
 {
     for(int i=_rangeL;i<=_rangeR;i++)
         if(unOrdered[i]<=_val) ++_notMore;
 }

 inline void countBucket(int _bktIdx,int _val,int& _notMore)
 {
     using std::upper_bound;

     int* ub=upper_bound(bucket[_bktIdx],bucket[_bktIdx]+bktSize,_val);
     _notMore+=(ub-bucket[_bktIdx]);
 }

 int ask(int _rangeL,int _rangeR,int _k) //k-th smallest
 {
     int digitL=_rangeL>>bktDigit;
     int digitR=_rangeR>>bktDigit;
     ;
     ;

     while(vL<vR)
     {
         ;
         ;
         if(digitL==digitR)
             enumerate(_rangeL,_rangeR,ordered[midV],notMore);
         else
         {
             ;i<digitR;i++)
                 countBucket(i,ordered[midV],notMore);
             enumerate(_rangeL,((digitL+)<<bktDigit)-,ordered[midV],notMore);
             enumerate(digitR<<bktDigit,_rangeR,ordered[midV],notMore);
         }

         ;
         else vR=midV;
     }
     return ordered[vL];
 }

 int main()
 {
     init();
     ;i<K;i++)
     {
         int l,r,k;
         scanf("%d%d%d",&l,&r,&k);
         printf(,r-,k));
     }
     ;
 }

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

这道题更好的做法是归并树，比归并树还好的做法是划分树，不过这都是后话了，有时间慢慢填坑

相关文章