题意：
左端点在[a,b]，右端点在[c,d]，求这个线段里中位数（上取整）最大值
思路：
对数组离散化，对每一个值建中位数的可持久化线段树（有重复也没事），就是对于root[i]，大于等于i的值为1，小于的为-1，
从小到大插入可持久化线段树即可
如果中位数为m，那么从左端点到右端点[l,r]的序列和应该>=0，我们只需要二分这个m检查是不是序列和>=0即可
满足左端点在[a,b]，右端点在[c,d]的子序列和的最大值，就是我们在用线段树维护最大子序和时的
[b+1,c-1]的sum+[a,b]的maxr+[c,d]的maxl
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
//#define lc root<<1
//#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 2e5+;
const int maxm = 2e6+;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0); int n;
PI a[maxn];
int q;
vector<ll>v;
int getid(ll x){
return lower_bound(v.begin(), v.end(), x)-v.begin()+;
}
bool cmp(PI a, PI b){
if(a.fst==b.fst)return a.sc<b.sc;
return a.fst<b.fst;
}
int root[maxn];
struct Node{
int maxl,maxr;
int sum;
}node[maxn*];
int ls[maxn],rs[maxn];
int tot,totn;
void build(int l, int r, int &root){
root = ++tot;
int mid = (l+r)>>;
if(l==r){
node[root].maxl=node[root].maxr=node[root].sum=;
return;
}
build(l, mid, ls[root]);
build(mid+, r, rs[root]);
node[root].maxl=max(node[ls[root]].sum+node[rs[root]].maxl, node[ls[root]].maxl);
node[root].maxr=max(node[rs[root]].sum+node[ls[root]].maxr, node[rs[root]].maxr);
node[root].sum=node[ls[root]].sum+node[rs[root]].sum;
return;
}
void insert(int lst, int &now, int l, int r, int p){
now = ++tot;
ls[now]=ls[lst];
rs[now]=rs[lst];
node[now] = node[lst];
int mid = (l+r)>>;
if(l==r){
node[now].maxl=node[now].maxr=node[now].sum=-;
return;
}
if(p<=mid)insert(ls[lst], ls[now], l, mid, p);
else insert(rs[lst], rs[now], mid+, r, p);
node[now].maxl=max(node[ls[now]].sum+node[rs[now]].maxl, node[ls[now]].maxl);
node[now].maxr=max(node[rs[now]].sum+node[ls[now]].maxr, node[rs[now]].maxr);
node[now].sum=node[ls[now]].sum+node[rs[now]].sum;
}
Node query(int ql, int qr, int l, int r, int now){ int mid = (l+r)>>;
if(l==ql&&r==qr){
return node[now];
}
else if(mid>=qr){
return query(ql, qr, l, mid, ls[now]);
}
else if(mid<ql){
return query(ql, qr, mid+, r, rs[now]);
}
else{
Node ans;
Node lc=query(ql,mid,l,r,now);
Node rc=query(mid+,qr,l,r,now);
ans.sum=lc.sum+rc.sum;
ans.maxl=max(lc.sum+rc.maxl,lc.maxl);
ans.maxr=max(rc.sum+lc.maxr,rc.maxr);
return ans;
}
}
void dfs(int x){
printf("%d %d %d %d %d %d\n",x,ls[x],rs[x],node[x].sum,node[x].maxl,node[x].maxr);
if(ls[x])dfs(ls[x]);
if(rs[x])dfs(rs[x]);
}
int main() {
scanf("%d", &n);
for(int i = ; i <= n; i++){
scanf("%d" ,&a[i].fst);
a[i].sc=i;
v.pb(a[i].fst);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(),v.end()),v.end());
totn=v.size();
int lstans = ;
int tmp[];
sort(a+,a++n,cmp);
build(,n,root[]);
for(int i = ; i <= n; i++){
insert(root[i-],root[i],,n,a[i].sc);
}int q;
//dfs(root[4]);
scanf("%d", &q);
while(q--){
for(int i = ; i <= ; i++){
scanf("%d", &tmp[i]);
tmp[i]=(tmp[i]+lstans)%n;
}
sort(tmp+,tmp++);
int l = ;
int r = n+;
int ans = ; while(l<=r){
int mid = (l+r)>>;
int res=max(query(tmp[]+,tmp[]+-,,n,root[mid-]).maxr,);
res+=query(tmp[]+,tmp[]+,,n,root[mid-]).sum;
res+=max(query(tmp[]++,tmp[]+,,n,root[mid-]).maxl,);
if(res>=){
ans=mid;
l=mid+;
}
else r = mid-;
}
printf("%d\n",lstans=v[ans-]);
}
return ;
}
/*
5
2 4 1 5 3
3
3 1 0 2
2 3 1 4
3 1 4 0 5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
*/