【BZOJ 2653】middle

链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2653
神犇题解：http://blog.csdn.net/wzq_qwq/article/details/48809845

题解

先来考虑一个子问题：

假如序列左端点在[l1,r1]之间，右端点在[l2,r2]之间
给定中位数x，问能否找出一个区间使得中位数大于等于x

这个问题很简单的样子：将小于x的赋值-1，大于x赋值为1
这样问题就转化为能否找到一个区间使得区间和大于等于0
这个可以用线段树在 log(n) 的时间内处理

如何在可以接受的时间复杂度内搞出每一个中位数对应的那颗线段树
考虑将原序列排序后从小到大来建树
第i棵线段树和第i+1棵线段树就只有第i个位置需要从1变成-1
这个用函数式线段树就好啦！

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 25000 + 9;
const int M = 400000;

int n,m,tot,arr[N],_hash[N],last_ans;
vector<int> pos_que[N];

namespace Chair_Tree{
	#define CT Chair_Tree
	int ch[M][2],ls[M],rs[M],sum[M],root[N],cnt;
	
	void Build(int &w, int l, int r) {
		sum[w=++cnt] = r - l + 1;
		ls[w] = rs[w] = sum[w];
		if (l < r) {
			int mid = l + r + 1 >> 1;
			Build(ch[w][0], l, mid-1);
			Build(ch[w][1], mid, r);
		} 
	}inline void init() {Build(root[1],1,n);}
	
	void insert(int p, int &w, int l, int r, int pur) {
		sum[w=++cnt] = sum[p] - 2;
		memcpy(ch[w],ch[p],sizeof(ch[w]));
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, pur);
			else insert(ch[p][1], ch[w][1], mid, r, pur);
			ls[w] = max(ls[ch[w][0]], sum[ch[w][0]] + ls[ch[w][1]]);
			rs[w] = max(rs[ch[w][1]], sum[ch[w][1]] + rs[ch[w][0]]);
		} else {
			ls[w] = rs[w] = 0;
		}		
	} inline void insert(int p, int w, int val) {
		insert(root[p],root[w],1,n,val);
	}
	
	int Get_sum(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return sum[w];
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			if (L < mid) ret += Get_sum(ch[w][0], l, mid-1, L, R);
			if (mid <= R) ret += Get_sum(ch[w][1], mid, r, L, R);
			return ret;
		}
	} inline int Get_Sum(int w, int l, int r) {
		return Get_sum(root[w],1,n,l,r);
	}
	
	int query_left(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return ls[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (R < mid) return query_left(ch[w][0], l, mid-1, L, R);
			else if (mid <= L) return query_left(ch[w][1], mid, r, L, R);
			else {
				int t1 = query_left(ch[w][0], l, mid-1, L, mid-1);
				int t2 = query_left(ch[w][1], mid, r, mid, R) + Get_sum(ch[w][0], l, mid-1, L, mid-1);
				return max(t1, t2);
			}	
		}
	} inline int Left_Max(int w, int l, int r) {
		return query_left(root[w],1,n,l,r);
	}
	
	int query_right(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return rs[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (R < mid) return query_right(ch[w][0], l, mid-1, L, R);
			else if (mid <= L) return query_right(ch[w][1], mid, r, L, R);
			else {
				int t1 = query_right(ch[w][1], mid, r, mid, R);
				int t2 = query_right(ch[w][0], l, mid-1, L, mid-1) + Get_sum(ch[w][1], mid, r, mid, R);
				return max(t1, t2);
			}
		}
	} inline int Right_Max(int w, int l, int r) {
		return query_right(root[w], 1, n, l, r);
	}
};

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline bool judge(int sta, int *lim) {
	int ret = CT::Get_Sum(sta, lim[2], lim[3]);
	ret += lim[1] < lim[2] ? CT::Right_Max(sta, lim[1], lim[2] - 1) : 0;
	ret += lim[3] < lim[4] ? CT::Left_Max(sta, lim[3] + 1, lim[4]) : 0;
	return ret >= 0;
}

int main() {
	n = read();
	for (int i=1;i<=n;i++) 
		arr[i] = _hash[i] = read();
	sort(_hash+1, _hash+1+n);
	tot = unique(_hash+1, _hash+1+n) - _hash - 1;
	for (int i=1;i<=n;i++) {
		arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
		pos_que[arr[i]].push_back(i);
	}
	CT::init();
	for (int i=2;i<=tot;i++) {
		CT::insert(i-1,i,pos_que[i-1][0]);
		for (int j=1,lim=pos_que[i-1].size();j<lim;j++) 
			CT::insert(i,i,pos_que[i-1][j]);
	}
	
	m = read();
	for (int i=1,lim[5],l,r,mid,ret;i<=m;i++) {
		for (int j=1;j<=4;j++)
			lim[j] = (read() + last_ans) % n + 1;
		sort(lim+1, lim+1+4);
		
		l = 1, r = tot;
		while (l <= r) {
			mid = l + r >> 1;
			if (!judge(mid,lim)) r = mid-1;
			else ret = mid, l = mid + 1; 
		}
		printf("%d\n",last_ans = _hash[ret]);
	}
	return 0;
}