Luogu p2839 [national training team]middle (two points + chairman tree + interval merging)

Luogu P2839 [ National Team ]middle（ Two points + Chairman tree ）

The question ：

A length of $n$ Sequence $a$, Let it be followed by $b$, Where the number of digits is defined as $b_{n/2}$ , among $a,b$ from $0$ Start tagging , Division takes the whole . Give you a length of $n$ Sequence $s$.

answer $Q$ A question like this ：$s$ The left-hand end of $[a,b]$ Between , The right endpoint is $[c,d]$ In the subinterval between , The largest median .

among $a<b<c<d$

The position also changes from 0 Start tagging

Ideas ：

Sort the initial array from small to large , The subscript of the median binary x , Determine whether the element at this position conforms to ： Greedy thought , stay x stay [a,d] Than a[x] All small numbers become -1, Big numbers all become 1, And then sum up ： stay [a,b] Find an interval from the right endpoint b The largest continuous interval starting to the left and + [b+1,c-1] and + stay [c,d] Find an interval from the left endpoint c Start the largest continuous interval to the right and .

root[i] Express , Than a No i Large numbers and small numbers have all been assigned to -1, All large numbers are assigned to 1.root[i] Of i Satisfy continuity , It can be divided into two parts .

Use the chairman tree , First assign all the points to 1, Then press the weight from small to large , In the corresponding position （a The initial position of the array ）-1. Every time violence logn To modify the tree .

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int INF=0x3f3f3f3f;
const int maxn=1e5+6;
int n,m,tot,a[maxn],id[maxn],root[maxn],p[6],pre;
struct NODE{
    
	int sum,ml,mr,l,r;
	void init(){
    
		sum=0,ml=mr=-INF;
	}
}tr[maxn*400],ANS;
bool cmp(int x,int y){
    
	return a[x]<a[y];
}
void build(int &t,int l,int r){
    // Dynamic opening point  
	t=++tot;
	tr[t].ml=tr[t].mr=tr[t].sum=r-l+1;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(tr[t].l,l,mid);
	build(tr[t].r,mid+1,r);
}
NODE merge(NODE h,NODE x,NODE y){
    //
	NODE z;
	z.l=h.l,z.r=h.r;// Initial subscript  
	z.sum=x.sum+y.sum;//sum Direct addition  
	z.mr=max(y.mr,y.sum+x.mr);// The maximum continuous sum of right intervals  
	z.ml=max(x.ml,x.sum+y.ml);// The maximum continuous sum of the left interval  
	return z;
}
void update(int &t,int l,int r,int x){
    
	tr[++tot]=tr[t],t=tot;
	if(l==r){
    
		tr[t].ml=tr[t].mr=tr[t].sum=-1;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)update(tr[t].l,l,mid,x);
	else update(tr[t].r,mid+1,r,x);
	tr[t]=merge(tr[t],tr[tr[t].l],tr[tr[t].r]);
}
void query(int t,int l,int r,int x,int y){
    
	if(x<=l&&r<=y){
    
		ANS=merge(ANS,ANS,tr[t]);// Merge the results of each query  
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)query(tr[t].l,l,mid,x,y);
	if(y>mid)query(tr[t].r,mid+1,r,x,y);
}
bool check(int pos){
    
	int he=0;
	if(p[2]+1<=p[3]-1){
    
		ANS.init();// Remember to initialize  
		query(root[pos],1,n,p[2]+1,p[3]-1);
		he+=ANS.sum;
	}
	ANS.init();
	query(root[pos],1,n,p[1],p[2]);
	he+=ANS.mr;
	ANS.init();
	query(root[pos],1,n,p[3],p[4]);
	he+=ANS.ml;
	return he>=0;
}
int solve(){
    
	for(int i=1;i<=4;i++)
	    p[i]=(p[i]+pre)%n+1;// Subscript from 0 Start , want +1 
	sort(p+1,p+1+4);
	int l=1,r=n,ans=0;// stay id Array subscripts are bisected  
	while(l<=r){
    
		int mid=(l+r)>>1;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	pre=a[id[ans]];
	return pre;
}
int main(){
    
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
    
		scanf("%d",&a[i]);
		id[i]=i;
	}
	sort(id+1,id+1+n,cmp);// discretization , take id Array by  a The size order of , Easy to handle  
	build(root[1],1,n);
	for(int i=2;i<=n;i++){
    
		root[i]=root[i-1];
		update(root[i],1,n,id[i-1]);
	}
	scanf("%d",&m);
	while(m--){
    
		scanf("%d%d%d%d",&p[1],&p[2],&p[3],&p[4]);
		printf("%d\n",solve());
	}
}