concept

The same function as the segment tree,

The interval p maintains the number of occurrences in this interval

For each occurrence of a number x, the interval of the leaf node [x,x] is +1, and deletion is -1

Support dynamic query of the KTH largest number, the smallest rank of the number x,

Find a precursor to x (i.e., the largest number less than x)

And finding the successor of x (that is, the smallest number greater than x)

Source of ideas

www.bilibili.com/video/av165…

Weight line segment tree and chair tree

tips

Learn the preparatory knowledge of the chairman tree

The chairman tree is good for structure

But usually write the writing habits of the reference will not change

And the notes indicate that it’s easier to understand and remember

It’s not like some of the code on the web is terribly readable

 

It actually works better in a structure

Then a set of boards will be used as hacking technology

But process-oriented ACM programming doesn’t care so much

 

The chairman tree will come back to learn and summarize

I’m not going to write this much code and I’m going to learn new things from blogs

Sample after class

BZOJ1503 unhappy cashier

Code for the board

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=1e5+10;
int num[maxn*5];
// Weight line tree:
// The value of the interval is the line tree of the number in the range
// The value of the leaf node is the number of occurrences of the number in the sequence
// Can be used as a balanced tree to write better than balanced tree code
Void build(int p,int l,int r) {if(l==r) {num[l]=0; return; } int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); } * /
void update(int p,int l,int r,int v,int op)//op==1 or -1, insert or delete
{
	num[p]+=op;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(v<=mid)update(p<<1,l,mid,v,op);
	else update(p<<1|1,mid+1,r,v,op); 
}

int Kth(int p,int l,int r,int rank)/ / k value
{
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(num[p<<1]>=rank)return Kth(p<<1,l,mid,rank);// Left subk is small
	return Kth(p<<1|1,mid+1,r,rank-num[p<<1]);// Right sub (k- left num) is small
} 

// Find the minimum rank of a number, starting from 0
int Rank(int p,int l,int r,int v)// if [1,v-1] >mid,v = rank3 // If [1,v-1] >mid,v = rank3
{
	if(r<v)return num[r];
	int mid=(l+r)>>1,res=0;
	if(v>l)res+=Rank(p<<1,l,mid,v);Rank [1]=0; // Rank [1]=0
	if(v>mid+1)res+=Rank(p<<1|1,mid+1,r,v);// The value of the right segment must be less than v
	return res;
} 

int Findpre(int p,int l,int r)
{
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(num[p<<1|1])return Findpre(p<<1|1,mid+1,r);// The right subtree is not empty
	return Findpre(p<<1,l,mid);// Otherwise look left
}
If possible, find the precursor in the right subtree less than v
int Pre(int p,int l,int r,int v)
{
	if(r<v)//maxr
	{
		if(num[p])return Findpre(p,l,r);
		return 0;
	}
	int mid=(l+r)>>1,Re;
	L =mid+1; l=mid+1; l=mid+1; l=mid+1
	if(mid+1<v&&num[p<<1|1]&&(Re=Pre(p<<1|1,mid+1,r,v)))return Re;
	// if r=mid, make r smaller than v
	return Pre(p<<1,l,mid,v);
} 

int Findnext(int p,int l,int r)
{
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(num[p<<1])return Findnext(p<<1,l,mid);
	return Findnext(p<<1|1,mid+1,r);
} 

If possible, find the successor in the left subtree greater than v
int Next(int p,int l,int r,int v)
{
	if(v<l)// The minimum complete interval greater than v has been found
	{
		if(num[p])return Findnext(p,l,r); 
		return 0;
	}
	int mid=(l+r)>>1,Re;
	If mid is greater than v, search the left subtree; if mid is greater than v, search the right subtree
	if(v<mid&&num[p<<1]&&(Re=Next(p<<1,l,mid,v)))return Re;
	return Next(p<<1|1,mid+1,r,v);
}

int main(a)
{
	return 0;
} 
Copy the code