2653: middle
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 2522 Solved: 1434
[Submit][Status][Discuss]
Description
一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个
长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
其中a<b<c<d。位置也从0开始标号。我会使用一些方式强制你在线。
Input
第一行序列长度n。接下来n行按顺序给出a中的数。
接下来一行Q。然后Q行每行a,b,c,d，我们令上个询问的答案是
x(如果这是第一个询问则x=0)。
令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。
将q从小到大排序之后，令真正的
要询问的a=q[0],b=q[1],c=q[2],d=q[3]。
输入保证满足条件。
第一行所谓“排过序”指的是从小到大排序！
n<=20000,Q<=25000
Output
Q行依次给出询问的答案。
Sample Input
5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
Sample Output
271451044
271451044
969056313
271451044
969056313
HINT
Source
思路：
这道题比较容易想到二分答案，但是check答案比较难想
我们考虑check某个数的时候把大于它的值设为1，小于它的设为-1，那么对【b+1,c-1】区间取和，对【a,b】取右端最大，对【c,d】取左端最大加来如果大于等于0，那么说明值在右边，往右边二分否则往左边二分，
但是如果我们每次check重新建一遍线段树，那肯定是会超时的，我们用主席树存就好了，我们先将主席树上各个点的值赋为1，然后依次输入2-n，每次输入将前一个数赋值为-1（因为排完序后前一个数一定比当前数小），那么当 root [k] 时主席树上的值就等于之前对k建的线段树，主席树上我们维护三个值，一个是区间和，一个是右端最大，以及左端最大。
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define mid int m = (l + r) >> 1
const int M = 2e4 + ;
int sum[M*],lsum[M*],rsum[M*],ls[M*],rs[M*],root[M],b[];
int idx,n;
struct node{
int val,id;
}a[M]; bool cmp(node x,node y){
return x.val < y.val;
} void pushup(int rt){
sum[rt] = sum[ls[rt]] + sum[rs[rt]];
lsum[rt] = max(lsum[ls[rt]],sum[ls[rt]]+lsum[rs[rt]]);
rsum[rt] = max(rsum[rs[rt]],sum[rs[rt]]+rsum[ls[rt]]);
} void build(int l,int r,int &rt){
rt = ++idx;
if(l == r){
sum[rt] = lsum[rt] = rsum[rt] = ;
return ;
}
mid;
build(l,m,ls[rt]); build(m+,r,rs[rt]);
pushup(rt);
} void update(int p,int l,int r,int old,int &rt){
rt = ++idx; ls[rt] = ls[old]; rs[rt] = rs[old];
if(l == r){
sum[rt] = lsum[rt] = rsum[rt] = -;
return ;
}
mid;
if(p <= m) update(p,l,m,ls[old],ls[rt]);
else update(p,m+,r,rs[old],rs[rt]);
pushup(rt);
} int query_sum(int L,int R,int l,int r,int rt){
if(L <= l&&R >= r){
return sum[rt];
}
mid;
int ret = ;
if(L <= m) ret += query_sum(L,R,l,m,ls[rt]);
if(R > m) ret += query_sum(L,R,m+,r,rs[rt]);
return ret;
} int query_lsum(int L,int R,int l,int r,int rt){
if(L <= l&&R >= r){
return lsum[rt];
}
mid;
if(R <= m) return query_lsum(L,R,l,m,ls[rt]);
else if(L > m) return query_lsum(L,R,m+,r,rs[rt]);
else return max(query_lsum(L,R,l,m,ls[rt]),query_sum(L,R,l,m,ls[rt])+query_lsum(L,R,m+,r,rs[rt]));
} int query_rsum(int L,int R,int l,int r,int rt){
if(L <= l&&R >= r){
return rsum[rt];
}
mid;
if(R <= m) return query_rsum(L,R,l,m,ls[rt]);
else if(L > m) return query_rsum(L,R,m+,r,rs[rt]);
else return max(query_rsum(L,R,m+,r,rs[rt]),query_sum(L,R,m+,r,rs[rt])+query_rsum(L,R,l,m,ls[rt]));
} bool check(int a,int b,int c,int d,int rt){
int cnt = ;
if(c- > b) cnt += query_sum(b+,c-,,n,root[rt]);
cnt += query_rsum(a,b,,n,root[rt]);
cnt += query_lsum(c,d,,n,root[rt]);
return cnt >= ;
} int main()
{
scanf("%d",&n);
for(int i = ;i <= n;i ++){
scanf("%d",&a[i].val);
a[i].id = i;
}
sort(a+,a++n,cmp);
build(,n,root[]);
for(int i = ;i <= n;i ++)
update(a[i-].id,,n,root[i-],root[i]);
int q,last = ;
scanf("%d",&q);
for(int i = ;i <= q;i ++){
scanf("%d%d%d%d",&b[],&b[],&b[],&b[]);
for(int j = ;j <= ;j ++)
b[j] = (b[j]+last)%n;
sort(b+,b+);
b[]++; b[]++; b[]++; b[]++;
int l = ,r = n,k;
while(l <= r){
mid;
if(check(b[],b[],b[],b[],m))
k = m,l = m+;
else r = m - ;
}
last = a[k].val;
printf("%d\n",last);
}
}