有了上一题的经验（POJ的静态区间第K最值）再解决这道题就轻松多了
空间5256KB，时间3330ms，如果把动态开点的平衡树换成数组模拟的话应该会更快
之所以选择了平方分割而不是树套树，不仅是所谓趁热打铁，更是因为：
平方分割的修改操作，无论编程复杂度还是时间复杂度都远优于树套树。
代码如下：（鄙人不才，不会压代码，所以写了300多行Σ( ° △ °|||)
template <class T>
struct SbtNode
{
typedef SbtNode<T> Node;
Node* lch;
Node* rch;
T val;
int lSize;
int rSize;
SbtNode(const T& _val):
lch(),rch(),val(_val),lSize(),rSize() {}
void assign(const T& _val)
{
lch=rch=;
val=_val;
lSize=rSize=;
}
};
template <class T,class Comp>
struct SizeBlcTree
{
,Left=,Right= };
typedef SbtNode<T> Node;
typedef SizeBlcTree<T,Comp> Sbt;
Node* root;
Comp cmp;
SizeBlcTree():root() {}
~SizeBlcTree() { clear(); }
void clear_aux(Node* _cur)
{
if(_cur->lch) clear_aux(_cur->lch);
if(_cur->rch) clear_aux(_cur->rch);
delete _cur;
}
void clear()
{
if(root) clear_aux(root);
root=;
}
Node* lRotate(Node* _cur)
{
Node* next=_cur->rch;
_cur->rch=next->lch;
next->lch=_cur;
_cur->rSize=next->lSize;
next->lSize+=(_cur->lSize+);
return next;
}
Node* rRotate(Node* _cur)
{
Node* next=_cur->lch;
_cur->lch=next->rch;
next->rch=_cur;
_cur->lSize=next->rSize;
next->rSize+=(_cur->rSize+);
return next;
}
Node* insert_aux(const T& _val,Node* _cur)
{
if(!_cur) return new Node(_val);
if(cmp(_val,_cur->val))
{
++_cur->lSize;
_cur->lch=insert_aux(_val,_cur->lch);
if(_cur->lch->lSize > _cur->rSize) return rRotate(_cur);
else if(_cur->lch->rSize > _cur->rSize)
{
_cur->lch=lRotate(_cur->lch);
return rRotate(_cur);
}
else return _cur;
}
else
{
++_cur->rSize;
_cur->rch=insert_aux(_val,_cur->rch);
if(_cur->rch->rSize > _cur->lSize) return lRotate(_cur);
else if(_cur->rch->lSize > _cur->lSize)
{
_cur->rch=rRotate(_cur->rch);
return lRotate(_cur);
}
else return _cur;
}
}
Sbt& operator << (const T& _val)
{
root=insert_aux(_val,root);
return *this;
}
Node* erase_aux(const T& _val,Node* _cur,bool& _found)
{
if(!_cur)
{
_found=false;
;
}
if(cmp(_val,_cur->val))
{
_cur->lch=erase_aux(_val,_cur->lch,_found);
if(_found) --_cur->lSize;
return _cur;
}
if(cmp(_cur->val,_val))
{
_cur->rch=erase_aux(_val,_cur->rch,_found);
if(_found) --_cur->rSize;
return _cur;
}
_found=true;
;
;
;
Node* res;
Node* &prev=res;
switch(status)
{
:
delete _cur;
;
:
res=_cur->lch;
delete _cur;
return res;
:
res=_cur->rch;
delete _cur;
return res;
:
prev=_cur;
if(prev->rch->lch)
{
--prev->rSize;
prev=prev->rch;
while(prev->lch->lch)
{
--prev->lSize;
prev=prev->lch;
}
_cur->val=prev->lch->val;
prev->lch=erase_aux(prev->lch->val,prev->lch,_found);
--prev->lSize;
}
else
{
_cur->val=_cur->rch->val;
_cur->rch=erase_aux(_cur->rch->val,_cur->rch,_found);
--_cur->rSize;
}
return _cur;
}
}
Sbt& operator >> (const T& _val)
{
bool found=false;
root=erase_aux(_val,root,found);
return *this;
}
int notMoreCount(const T& _val)
{
Node* cur=root;
;
while(cur)
{
if(cmp(_val,cur->val)) cur=cur->lch;
else
{
res+=(cur->lSize+);
cur=cur->rch;
}
}
return res;
}
int lessCount(const T& _val)
{
Node* cur=root;
;
while(cur)
{
if(cmp(cur->val,_val))
{
res+=(cur->lSize+);
cur=cur->rch;
}
else cur=cur->lch;
}
return res;
}
};
;
;
;
;
#include <functional>
#include <algorithm>
int unOrd[bktCount*bktSize];
using std::less;
SizeBlcTree<int,less<int> > all;
SizeBlcTree<int,less<int> > bucket[bktCount];
int N,K;
int cs;
#include <cstdio>
void init()
{
scanf("%d%d",&N,&K);
;i<N;i++)
{
scanf("%d",unOrd+i);
all<<unOrd[i];
bucket[i>>bktDigit] << unOrd[i];
}
}
inline void enumerate(int _rL,int _rR,int _val,int& _less,int& _notMore)
{
for(int i=_rL;i<=_rR;i++) if(unOrd[i]<=_val)
{
_notMore++;
if(unOrd[i]<_val) _less++;
}
}
int getAns(int _rL,int _rR,int _k)
{
int bktL = _rL>>bktDigit;
int bktR = _rR>>bktDigit;
int prevVal;
SbtNode<int> *cur=all.root;
while(cur)
{
;
;
if(bktL==bktR) enumerate(_rL,_rR,cur->val,less,notMore);
else
{
;i<bktR;i++)
{
notMore += bucket[i].notMoreCount(cur->val);
less += bucket[i].lessCount(cur->val);
}
enumerate(_rL,((bktL+)<<bktDigit)-,cur->val,less,notMore);
enumerate(bktR<<bktDigit,_rR,cur->val,less,notMore);
}
if(less<_k && notMore>=_k) return cur->val;
prevVal=cur->val;
if(less>=_k) cur=cur->lch;
else cur=cur->rch;
}
return prevVal;
}
void solve()
{
char cmd;
do cmd=getchar(); while(cmd==' ' || cmd=='\n');
if(cmd=='Q')
{
int rL,rR,k;
scanf("%d%d%d",&rL,&rR,&k);
printf(,rR-,k));
}
else
{
int pos,v;
scanf("%d%d",&pos,&v);
--pos;
all<<v;
bucket[pos>>bktDigit] >> unOrd[pos];
bucket[pos>>bktDigit] << (unOrd[pos]=v) ;
}
}
void reset()
{
all.clear();
int used=N>>bktDigit;
;i<=used;i++) bucket[i].clear();
}
int main()
{
scanf("%d",&cs);
while(cs--)
{
init();
while(K--) solve();
reset();
}
;
}简析：
可以和我的这篇随笔进行对比：http://www.cnblogs.com/Onlynagesha/p/5353531.html
前面将近2/3都是SBT的模板
平方分割的大致思路和静态第k大是一样的，中间分块高效维护，然后枚举两边的零头
但在动态第k大问题中，每个桶维护的都是一棵平衡树。这样我们便可以高效的修改。
若要进行高效的二分，我们还要维护一颗“总的”平衡树all，存放当前所有的数值。
二分的时候从all的根节点开始，边界是走到叶子节点。二分的每一步都有三种可能：
（1）当前节点就是答案
（2）当前节点的值过大，那么取下一个值为其左孩子
（3）当前节点的值过大，那么取下一个值为其右孩子
注意体会基于树的二分和基于区间的二分的差异。前者难以保证“可能”会成为答案的值被保留（因为每走一步当前的值就被“丢弃”了），而后者可以
另外维护all的时候还有一个小技巧：修改数值时只需将新值插入而不需将旧值删去，这样可以省下一点时间常数
被“删去”的值在之后的二分过程中一定不会满足第（1）种可能