Firstly, a chair tree is used to find the board with the smallest interval K.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid (l+r)/2
using namespace std;
const int N = 1e6+4;
int L[N<<5],R[N<<5],sum[N<<5];
int a[N],b[N],T[N];
int cnt,ss;
int build(int l,int r)
{
int rt = ++cnt;
sum[rt] = 0;
if(l < r){
L[rt] = build(l,mid);
R[rt] = build(mid+1,r);
}
return rt;
}
int update(int pre,int l,int r, int k){
int rt = ++cnt;
L[rt] = L[pre],R[rt] = R[pre],sum[rt] = sum[pre] +1;
if(l<r){
if(k <= mid)L[rt] = update(L[rt],l,mid,k);
else R[rt] = update(R[rt],mid+1,r,k);
}
return rt;
}
int query(int u,int v,int l,int r,int k)
{
if(l >= r)return l;
int x = sum[L[v]] - sum[L[u]];
if(x >= k )return query(L[u] ,L[v] , l, mid ,k);
else return query(R[u] ,R[v] ,mid+1 ,r ,k-x);
}
int main(){
int n,m,q,p;
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
m = unique(b+1,b+1+n)-b-1;
T[0] = build(1,m);
//Discretization
for(int i = 1;i<=n;i++)
{
int t = lower_bound(b+1,b+1+m,a[i])-b;
T[i] = update(T[i-1],1,m,t);
}
while(p--){
int z,y,x;
scanf("%d%d%d",&x,&y,&z);
int t = query( T[x-1],T[y],1,m,z);
printf("%d\n",b[t]);
}
return 0;
This is the ordinary chairman tree.
Of course, this kind of commentary can't be used.
So let's talk about the weight segment tree first.
Example
Find the answer in Hangzhou Electric Power Multicultural College Game 3, 2019
Topic: Group Q sample. The first line of each sample group gives n, m, and the next line gives n (a[i]). For each element, delete the minimum element before it so that it is less than or equal to M.
Establish a weighted line segment tree, and after discretization, check how many are clustered to m.
The code is as follows
#include<bits/stdc++.h>
#define LL long long
#define PLL pair<LL,LL>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=2e5+50;
int n,N;
LL m,a[maxn],b[maxn],sum[maxn<<2],num[maxn<<2];
void init(){
sort(b+1,b+1+n);
N = unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++)
{
a[i] = lower_bound(b+1,b+1+N,a[i])-b;
}
}//Discretization
void updata(int rt,int l,int r,int p)
{
if(l==r)
{
sum[rt]+=b[l]; //The sum of record weight p
num[rt]++; //Record the number of weights p
return;
}
int mid=(l+r)>>1;
if(p<=mid)
updata(rt<<1,l,mid,p);
else
updata(rt<<1|1,mid+1,r,p);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
num[rt]=num[rt<<1]+num[rt<<1|1];
}
PLL query1(int rt,int l,int r,LL k) //Dichotomy Finds the Demarcation Point to Delete Weights
{
if(l==r)
{
if(k%b[l]==0)
return PLL(l,k/b[l]); //Returns the bounding point weight
else //And the specific number of weights of the demarcation point that need to be deleted
return PLL(l,k/b[l]+1);
}
int mid=(l+r)>>1;
if(sum[rt<<1|1]>=k) //If the sum of the right subtrees is greater than k, look for the right subtree.
return query1(rt<<1|1,mid+1,r,k);
else
return query1(rt<<1,l,mid,k-sum[rt<<1|1]); //Otherwise, look for the left subtree and note that k subtracts the weight of the right subtree.
//(Explains that all elements of the right subtree should be deleted)
}
LL query2(int rt,int l,int r,int ql,int qr) //Number of queries
{
if(ql<=l&&r<=qr)
return num[rt];
if(r<ql||l>qr)
return 0;
int mid=(l+r)>>1;
return query2(rt<<1,l,mid,ql,qr)+query2(rt<<1|1,mid+1,r,ql,qr);
}
int main()
{
int Q;
scanf("%d",&Q);
while(Q--)
{
scanf("%d %lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=a[i];
}
init(); //Discretization
memset(sum,0,sizeof(sum));
memset(num,0,sizeof(num));
LL sum=0,ans[maxn];
for(int i=1;i<=n;i++)
{
sum+=b[a[i]];
if(sum>m)
{
PLL temp=query1(1,1,N,sum-m);
ans[i]=temp.second; //Specific Number of Boundary Point Weights to be Deleted
if(temp.first+1<=m)
ans[i]+=query2(1,1,N,temp.first+1,m); //Number of elements greater than the weights of boundary points
}
else
ans[i]=0;
updata(1,1,N,a[i]);
}
for(int i=1;i<=n;i++)
printf("%lld ",ans[i]);
printf("\n");
}
return 0;
}
Obviously, this tree can only look up the previous elements, and can not be queried in a certain subinterval, so we can persist it for a long time and become the President Tree.
The chairman tree can query the interval K, or query the number of occurrences of an element (?????).
Example The 4th K-th Closest Distance of Hangzhou Electric Power Multicultural University in 2019
Topic: Given n n n numbers, q queries, each given l, r, p, k. Ask the interval l, the absolute value of the difference between all the numbers in R and p, what is the largest number in k.
The Presidential Tree + Divide
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6;
struct node{
int val ,l,r;
}tree[N*40]; //
int root[N],cnt;
int n,q,a[N];
int update(int pre,int L,int R,int k)
{
int ctt = ++cnt;
tree[ctt] = tree[pre];
tree[ctt].val ++ ;
if(L==R)return ctt;
int mid = (R+L)/2;
if(mid >= k) tree[ctt].l = update(tree[pre].l,L,mid,k);
else tree[ctt].r = update(tree[pre].r,mid+1,R,k);
return ctt;
}
int query(int pl, int pr, int l, int r, int rt, int lt) {
if(pl <= l && r <= pr) {
return tree[rt].val - tree[lt].val;
}
int mid = (l + r) >> 1;
int res = 0;
if(pl <= mid) res += query(pl, pr, l, mid, tree[rt].l, tree[lt].l);
if(pr > mid) res += query(pl, pr, mid + 1, r, tree[rt].r, tree[lt].r);
return res;
}
int main(){
int t;
scanf("%d",&t);
while(t--)
{
cnt = 0;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
root[i] = update(root[i-1],1,M,a[i]);
}
int prex=0,l,r,p,k;
while(q--)
{
scanf("%d%d%d%d",&l,&r,&p,&k);
l^= prex,r^=prex,p^=prex,k^=prex;
int pl = 0, pr = M;
while(pl <= pr)
{
int mid = (pl + pr) >> 1;
if(query(max(1, p - mid), min(M, p + mid), 1, M, root[r], root[l - 1]) >= k)
{
prex = mid;
pr = mid - 1;
}
else pl = mid + 1;
}
printf("%d\n",prex);
}
}
return 0;
}
Thank you for watching.