P2839 [国家集训队]middle

LuoP2839 [国家集训队]middle

主席树好题,点个赞！

这道题让我知道了,主席树不只是维护权值线段树。也是可以去像普通线段树一样操作的.

首先,关于求区间中位数的一个小(trick)(反正我之前没听说过)

二分答案

将大于等于(mid)的值看做(1)，小于(mid)的看做(-1)

那么如果区间和大于等于(0),则说明区间中位数大于等于(mid)(因为此题定义偶数个元素时,中位数为中间靠前的一个,如果是靠后的就要严格大于了)

之后,发现这个左端点和右端点不固定有点恶心.但是([b + 1,c - 1])是一定要选的,所以([b + 1,c - 1])这个区间和的贡献是要算的

所以我们先算这一区间的值。然后区间([a,b]),([c,d]).我们最优选,就是最大前缀后缀和啊

所以要维护区间和，最大左起子段和,最大右起子段和

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cctype>
#define LL long long
const int N = 2e4 + 3;
struct node{
	int sum;
	int lsum,rsum;
	int lc,rc;
}a[N << 6];
struct inf{
	LL val;
	int pos;	
}v[N];
int rt[N];
int n,q,t;
inline LL read(){
	LL v = 0,c = 1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') c = -1;
		ch = getchar();	
	}
	while(isdigit(ch)){
		v = v * 10 + ch - 48;
		ch = getchar();	
	}
	return v * c;	
}
inline void pushup(int u){
	a[u].sum = a[a[u].lc].sum + a[a[u].rc].sum;
	a[u].lsum = std::max(a[a[u].lc].lsum,a[a[u].lc].sum + a[a[u].rc].lsum);
	a[u].rsum = std::max(a[a[u].rc].rsum,a[a[u].rc].sum + a[a[u].lc].rsum);
}
inline void build(int &u,int l,int r){
	u = ++t;
	if(l == r){
		a[u].sum = a[u].lsum = a[u].rsum = 1;
		return ;	
	}
	int mid = (l + r) >> 1;
	build(a[u].lc,l,mid);
	build(a[u].rc,mid + 1,r);
	pushup(u);
}
inline void ins(int &u,int l,int r,int x){
	a[++t] = a[u];	
	u = t;
	if(l == r){
		a[u].sum = -1;
		a[u].lsum = -1;
		a[u].rsum = -1;
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) ins(a[u].lc,l,mid,x);
	else ins(a[u].rc,mid + 1,r,x);
	pushup(u);
}
inline int query_sum(int u,int l,int r,int ll,int rr){
	if(rr < ll) return 0;
	if(l == ll && r == rr) return a[u].sum;
	int mid = (l + r) >> 1;
	if(rr <= mid) return query_sum(a[u].lc,l,mid,ll,rr);
	else if(ll > mid) return query_sum(a[u].rc,mid + 1,r,ll,rr);
	else return query_sum(a[u].lc,l,mid,ll,mid) + query_sum(a[u].rc,mid + 1,r,mid + 1,rr);	
}
inline int query_lsum(int u,int l,int r,int ll,int rr){
	if(rr < ll) return 0;
	if(l == ll && r == rr) return a[u].lsum;
	int mid = (l + r) >> 1;
	if(rr <= mid) return query_lsum(a[u].lc,l,mid,ll,rr);
	else if(ll > mid) return query_lsum(a[u].rc,mid + 1,r,ll,rr);
	else return std::max(query_lsum(a[u].lc,l,mid,ll,mid),query_sum(a[u].lc,l,mid,ll,mid) 
	+ query_lsum(a[u].rc,mid + 1,r,mid + 1,rr));
}
inline int query_rsum(int u,int l,int r,int ll,int rr){
	if(rr < ll) return 0;
	if(l == ll && r == rr) return a[u].rsum;
	int mid = (l + r) >> 1;
	if(rr <= mid) return query_rsum(a[u].lc,l,mid,ll,rr);
	else if(ll > mid) return query_rsum(a[u].rc,mid + 1,r,ll,rr);
	else return std::max(query_rsum(a[u].rc,mid + 1,r,mid + 1,rr),query_sum(a[u].rc,mid + 1,r,mid + 1,rr) + 
	query_rsum(a[u].lc,l,mid,ll,mid));	
}
inline bool check(int mid,int Q1,int Q2,int Q3,int Q4){
	int res = 0;
	//printf("%d %d %d %d
",Q1,Q2,Q3,Q4);
	res += query_sum(rt[mid],1,n,Q2 + 1,Q3 - 1);
	res += query_rsum(rt[mid],1,n,Q1,Q2);
	res += query_lsum(rt[mid],1,n,Q3,Q4);
	return res >= 0;
}
inline bool cmp(inf x,inf y){
	return x.val < y.val;
}
int main(){
	n = read();
	for(int i = 1;i <= n;++i){
		v[i].val = read();
		v[i].pos = i;	
	}
	std::sort(v + 1,v + n + 1,cmp);
	build(rt[1],1,n);
	for(int i = 2;i <= n + 1;++i) {
		rt[i] = rt[i - 1];
		ins(rt[i],1,n,v[i - 1].pos);
	}
	q = read();
	LL last = 0,Q[4];
	while(q--){
		for(int i = 0;i < 4;++i) Q[i] = (read() + last ) % n + 1;
		std::sort(Q,Q + 4);
		int l = 1,r = n,ans;
		while(l <= r){
			int mid = (l + r) >> 1;//printf("%d
",mid);
			if(check(mid,Q[0],Q[1],Q[2],Q[3])) ans = mid,l = mid + 1;
			else r = mid - 1;	
		}
		printf("%lld
",last = v[ans].val);
	}
	return 0;	
}