Solution/algorithm {\255. Kth decimal}
@LINK: https://www.acwing.com/problem/content/description/257/;
For array A, find the Kth decimal in the interval A[l...r];
. For example, A = [5,3,2,3,1], for A[123] = [2(1st decimal), 3(1st decimal) 2nd smallest), 3(3rd smallest)];
Algorithm-(persistent segment tree + weighted segment tree)
1: Discretize the array into [0, Range); (of course if min(A)>=0 & amp; & amp; max(A ) is not large There is no need to discretize, that is, Range== max(A));
2: Perform persistent segment tree on the array A[N], that is, there are N versions in total, and the i version of the segment tree is maintainedA[0...i]These numbers; each version of the segment tree is weighted segment tree, that is, the underlying interval of the segment tree is [0 , Range);
For example, A[N] = [4,2,1,2], after discretization is [2,1,0,1] (that is, N= 4, Range=3), for the line segment tree Version[3] (the underlying range is [0, Range)) she maintains 0 ,1,1,2These numbers are the [0].Count=1, [1].Count=2, [2].Count=1 of its leaf nodes, for Version[0] (its underlying range is also [0,Range)) She maintains the number [2] which is the leaf node [2 ].Count=1;
Code
class ___SegmentTree_IntervalOrder{ // For the array `A[]`, query the Kth decimal in the interval `A[l...r]` each time;
//<the specific method is {weight segment tree + persistence}, perform *discretized hashing* on `A[]` and let `N1: set(A[]).size()`, then any version The intervals maintained by the line segment tree are all `[0,N1)`;
// . The `i`th version of the line segment tree maintains the discrete hash values corresponding to the numbers `A[...i]`;
// . The underlying array `[i]` of all versions of the line segment tree corresponds to the same number, that is, the `A[?]`* element whose *discretized hash is equal to `i`;
public:
class __Node_{
public:
__Node_ *SonPtr[2];
std::pair<int,int> Interval;
//{ Data data field
int Count; //The number of elements in `Interval`; this value must comply with *subtraction*, that is, `[l...r].Count = [0...r].Count - [0... l).Count`;
//} Data data field
void Initialize_data(){ // Initialize *all data fields*;
Count = 0;
}
void Update_bySon(){ //Use `SonPtr[0|1].{data field}` to update *all data fields* of the current point;
Count = SonPtr[0]->Count + SonPtr[1]->Count;
}
friend ostream & amp; operator<<( ostream & amp; _cout, const __Node_ & amp; _a){
return _cout<< ___SupimoTools::Debug::__ToString_items( _a.Interval)<< ", "<< _a.Count;
}
};
int __Range = 0; // The range of any version of the line segment tree is `[0...Range)`;
vector<__Node_ *> __VersionRoot; // `a: __VersionRoot[b]` represents the `b` version of the line segment tree (that is, maintaining the numbers `A[...b]`);
vector<__Node_> __NodesPool;
__Node_ * __Get_aNewNode(){
ASSERT_WEAK_( __NodesPool.size() != __NodesPool.capacity());
__NodesPool.emplace_back(); return &__NodesPool.back();
}
void Initialize( const vector<int> & amp; _arr){
ASSERT_MSG_( "Ensure that `_arr` is discretized, such as `A=[3,2,3,-1]` then `_arr==[2,1,2,0]`");
__Range = 1 + *std::max_element( _arr.begin(), _arr.end());
__NodesPool.reserve( __Range * 4 + std::log2(__Range)*_arr.size()); __NodesPool.clear();
__VersionRoot.resize( _arr.size());
{ // Initial `0`th version is `arr[0]`:
static function<__Node_*(int,int)> build = [ & amp;]( int _l, int _r){
__Node_ * cur = __Get_aNewNode(); cur->Interval = {_l,_r};
if( _l == _r){ cur->Initialize_data();}
else{ int mid = (_l + _r)>>1; cur->SonPtr[0] = build( _l, mid); cur->SonPtr[1] = build( mid + 1, _r);}
return cur;
};
__VersionRoot[0] = build(0, __Range-1);
static function<void(__Node_*)> insert = [ & amp;]( __Node_ * _cur){
if( _cur->Interval.first == _cur->Interval.second){
_cur->Count + = 1;
return;
}
int mid = (_cur->Interval.first + _cur->Interval.second)>>1;
if( _arr[0] <= mid){ insert( _cur->SonPtr[0]);} else{ insert( _cur->SonPtr[1]);}
_cur->Update_bySon();
};
insert(__VersionRoot[0]);
}
{ // Based on version `0`, create versions `1,2,3,...`
for( int ver = 1; ver < (int)_arr.size(); + + ver){
static function<void(__Node_*)> create = [ & amp;]( __Node_ * _cur){
if( _cur->Interval.first == _cur->Interval.second){
_cur->Count + = 1;
return;
}
int mid = (_cur->Interval.first + _cur->Interval.second)>>1;
auto neww = __Get_aNewNode();
if( _arr[ver] <= mid){ *neww = *_cur->SonPtr[0]; _cur->SonPtr[0] = neww; create( _cur->SonPtr[0]);}
else{ *neww = *_cur->SonPtr[1]; _cur->SonPtr[1] = neww; create( _cur->SonPtr[1]);}
_cur->Update_bySon();
};
__VersionRoot[ver] = __Get_aNewNode(); *__VersionRoot[ver] = *__VersionRoot[ver-1]; create( __VersionRoot[ver]);
}
}
}
int Get_intervalData( int _l, int _r, int _Kth){ // Get the Kth decimal in `_arr[l...r]` (for example, `arr[l...r] = {1,2,2, 3}`, then the `K=3` decimal is `3`);
ASSERT_WEAK_( 0<=_l & amp; & amp; _l<=_r & amp; & amp; _r<(int)__VersionRoot.size());
ASSERT_WEAK_( 0<=_Kth & amp; & amp; _Kth<(__VersionRoot[_r]->Count - (_l==0?0:__VersionRoot[_l-1]->Count)));
static function<int(__Node_*,__Node_*)> dfs = [ & amp;]( __Node_ * _rig, __Node_ * _lef)->int{
//><there must be `_lef==nullptr || _rig->Interval==_lef->Interval`;
ASSERT_( _lef==nullptr || _rig->Interval==_lef->Interval);
if( _rig->Interval.first == _rig->Interval.second){
return _rig->Interval.first;
}
int count = _rig->SonPtr[0]->Count - (_lef==nullptr?0:_lef->SonPtr[0]->Count);
if( _Kth < count){ return dfs( _rig->SonPtr[0], (_lef==nullptr?nullptr:_lef->SonPtr[0]));}
_Kth -= count; return dfs( _rig->SonPtr[1], (_lef==nullptr?nullptr:_lef->SonPtr[1]));
};
return dfs( __VersionRoot[_r], (_l==0 ? nullptr:__VersionRoot[_l-1]));
}
void Debug(){
cout<< "___SegmentTree_IntervalOrder::Debug::Begin\\
";
for( int version = 0; version < (int)__VersionRoot.size(); + + version){
vector< pair<int,int> > ANS; // `[(2,1), (3,2)]` This means that the elements maintained by the line segment tree are `{2,3,3}`;
static function<void(__Node_*)> dfs = [ & amp;]( __Node_ * _cur){
if( _cur->Count <= 0){ return;}
if( _cur->Interval.first == _cur->Interval.second){
ANS.emplace_back( _cur->Interval.first, _cur->Count);
return;
}
else{ dfs( _cur->SonPtr[0]); dfs( _cur->SonPtr[1]);}
_cur->Update_bySon();
};
dfs(__VersionRoot[version]);
cout<< "Version: "<< version<< ", "<< "Elements: "<< Debug::__ToString( ANS)<< "\\
";
};
cout<< "___SegmentTree_IntervalOrder::Debug::End\\
";
}
}; // class ___SegmentTree_IntervalOrder
___SegmentTree_IntervalOrder SegmentTree;
Notes
For example, {1,1,2,2} ranks 1|2nd largest as 1, and ranks 3rd|4th largest as 2 >;
First consider the case of l==1, that is, find the Kth ranking of these numbers A[0...i];
If violence is used, it will explode the space instead of timeout, that is, each A[0...i] will be treated as a separate array; handle explosion SpaceProblems Git Algorithms Can Solve;
For the array A[N], ensure that N is a constant (cannot be changed), discretize it, that is, each A[i] corresponds to An ordinal with >=0 is H(A[i]) (for example, A=[2,2,1 ], then H(1)=0, H(2)=1, let M=maximum ordinal;
The interval of the line segment tree is set to [0, M], and each node [l,r] is set with a Count to represent the individuals in the interval. number (that is, the number of numbers whose ordinal number is [l,r]); for A[0...i], the corresponding line segment tree is for each A[i] are all executed: [H(A[i]), H(A[i])] of the line segment tree Count + = in this interval 1;
. For example, A = [3, 2, 2, 1], M=2; for A[0...2 ] = [3,2,2] Its corresponding line segment tree is: [0(0), 1(2), 2(1)] where a(b ) means that there are b elements of [a] in the line segment tree; because there are 2 2 H(2)=1 code> So there are 2 1’s in the line segment tree; At this time, for example, if you want to find the third largest number, there are 2 numbers in the [0,1] interval, so the answer must be [2,2]Interval, that is, the answer can be found by dividing it into two;
Note that each number’s H() is fixed, so the premise is that your N, that is, the entire array, is fixed and static and cannot be changed;
@DELI;
Code
Note that the count in __Query is the Count in the left child of the current node, not the Count of the current node. >;
void __Insert( int _node_id, int _left, int _right){
//<The current node’s interval is `[left, right]`;
auto & amp; curNode = Nodes[ _node_id];
if(_left == _right){
curNode.Count + + ;
return;
}
auto mid = (_left + _right)>>1;
int son_id = (__InsertData <= mid ? 0 : 1);
if(__InsertFlag.first == 1){ // Create a new version based on the parent version
Nodes.push_back( Nodes[curNode.SonId[son_id]]); curNode.SonId[ son_id] = (int)Nodes.size() - 1;
}
if( son_id == 0){ __Insert( Nodes[_node_id].SonId[son_id], _left, mid);}
else{ __Insert( Nodes[_node_id].SonId[son_id], mid + 1, _right);}
__Update_fa(Nodes[_node_id], Nodes[Nodes[_node_id].SonId[0]], Nodes[Nodes[_node_id].SonId[1]], _left, _right);
}
void Insert( pair<int,int> _flag, int _data){
//< @IF(`flag.first=1`):[Create a new version with the version number `flag.second` as the parent node (the version number is `VersionRoot.size()`)];
// @ELIF(`flag.first==-1`): [Modify version number `flag.second` directly but make sure *this version must be a leaf node on Git*, that is, there is no `VersionFa[?]=flag. second`];
ASSERT_( IsInInterval_( _data, 0, __Range-1, true));
__InsertFlag = _flag; __InsertData = _data;
int rootId; //The root node of the line segment tree currently being operated;
if( _flag.first == 1){ // Create a new version based on the parent version
ASSERT_( IsInInterval_( _flag.second, 0, (int)VersionRoot.size()-1, true));
rootId = Nodes.size();
Nodes.push_back( Nodes[ VersionRoot[ _flag.second]]); // Copy
VersionRoot.push_back( rootId);
VersionFa.push_back( _flag.second);
}
else if( _flag.first == -1){ // Operate on existing version
ASSERT_( IsInInterval_( _flag.second, 0, (int)VersionRoot.size()-1, true));
ASSERT_MSG_( "Make sure there is no `VersionFa[?]==flag.second`, that is, this version is a *leaf node* on Git;");
rootId = VersionRoot[_flag.second];
}
else{
ASSERT_(0);
}
__Insert( rootId, 0, __Range-1);
}
int __Query( int _leftNodeId, int _rightNodeId, int _l, int _r){
if( _l == _r){
int count = Nodes[_rightNodeId].Count;
if( _leftNodeId != -1){ count -= Nodes[_leftNodeId].Count;}
ASSERT_( IsInInterval_( __QueryData, 1, count, true));
return _l;
}
int count = Nodes[Nodes[_rightNodeId].SonId[0]].Count;
if( _leftNodeId != -1){ count -= Nodes[Nodes[_leftNodeId].SonId[0]].Count;}
//<the definition of `T` is the definition in `@LINK: Query function`. At this time, count represents the *left son information* of the node corresponding to the `[l,r]` interval of the line segment tree `T`;
int son_id = 0;
if( __QueryData > count){ son_id = 1; __QueryData -= count;}
int newLeftId = -1;
if( _leftNodeId != -1){ newLeftId = Nodes[_leftNodeId].SonId[son_id];}
int mid = (_l + _r)>>1;
if( son_id == 0){ return __Query( newLeftId, Nodes[_rightNodeId].SonId[son_id], _l, mid);}
return __Query( newLeftId, Nodes[_rightNodeId].SonId[son_id], mid + 1, _r);
}
int Query(int _lv, int _rv, int _data){
//< `T` is defined as a line segment tree (this is virtual) constructed with (`[_lv + 1,...,_rv]` newly added numbers in these versions). At this time, it is in `T `Query `data` on this virtual line segment tree;
// . Ensure that `lv` must be the *ancestor node* of `rv` in the Git tree, let the string set corresponding to the TRIE tree of the `lv` version be `SL` and let the string set corresponding to the `rv` version is `SR`, then `T` is equal to the difference set `SR/SL`];
// . Note that `lv,rv` here is very similar to the prefix and idea but there is one difference. It does not contain `lv`, that is, what you are actually querying is `[lv + 1, ..., rv]` This interval (i.e. the modification operations called by these `(lv,rv]` versions);
ASSERT_( _lv>=-1 & amp; & amp; _lv<=_rv & amp; & amp; _rv>=0 & amp; & amp; _rv<(int)VersionRoot.size());
__QueryData = _data;
int rightId = VersionRoot[_rv];
int leftId;
if(_lv == -1){
leftId = -1;
}
else{
ASSERT_MSG_( "Ensure that `lv` must be the *ancestor node* of `rv` in the Git tree");
leftId = VersionRoot[_lv];
}
return __Query( leftId, rightId, 0, __Range-1);
}out;
}
}; // class ___SegmentTree_Persistent
int N, M; cin>>N>>M;
vector<int> A(N); for( auto & amp; i : A){ cin>> i;}
auto B = A; sort( B.begin(), B.end()); B.erase( unique(B.begin(), B.end()), B.end());
___SegmentTree_PersistentTr;
Tr.Initialize( B.size(), 5000006, N + 5);
FOR_(i, 0, N-1){
int id = lower_bound( B.begin(), B.end(), A[i]) - B.begin();
if(i==0){
Tr.Create();
Tr.Insert({-1,0}, id);
}
else{
Tr.Insert({1,i-1}, id);
}
}
while( M -- ){
int l, r, k; cin>>l>>r>>k;
-- l, -- r;
cout<< B.at( Tr.Query( l-1, r, k))<< "\\
";
}