题目传送门：https://www.luogu.org/problemnew/show/P2839
题目大意：给出一个长度为$N$的序列与$Q$次询问，每次询问左端点在$[a,b]$，右端点在$[c,d]$的区间中最大的中位数，强制在线（本题中的中位数定义与平常不同，设某区间长度为$L$，则在从小到大排序后的序列中（编号从$0$开始），其中位数为第$\lfloor L/2 \rfloor$号元素）$N,Q \leq 2 \times 10^4$
这鬼题让我知道主席树可以用于除第$K$大以外的问题$qwq$
观察$100 \%$的数据规模，$O(nQ)$的做法都比较吃力，所以考虑使用$log$数据结构进行维护获得$O(Qlogn)$或者$O(Qlog^2n)$的算法。故考虑到使用线段树进行维护，同时使用二分的方式寻找每个询问的答案，
其中check的内容就是寻找是否有满足该询问条件的区间，在其中（大于等于当前二分的数的数字个数）要大于等于（小于当前二分的数的数字个数）。断句略奇怪
不妨将大于等于当前二分的数的数字的权值设为1，小于当前二分的数的数字的权值设为-1，check的内容就等价于询问$$max(\sum_{i=x}^y w_i) \geq 0 (x \in {[a , b]} , y \in{[c , d]})$$是否成立。
所以想到对于每个数字建立一个线段树存储权值，在每一次二分询问时求出对应线段树中$x \in {[a , b]} , y \in{[c , d]},\sum_{i=b+1}^{c-1} w_i + max(\sum_{i=x}^b w_i)+max(max(\sum_{i=c}^y w_i))$是否大于0，刚好这三个式子对应区间和、区间最大后缀、区间最大前缀，可以使用线段树解决。
然后发现对于排序后的相邻两数只有一个$1$变成$-1$，就可以使用主席树将空间压到允许范围内了
时间复杂度为$O(Qlog^2n)$，空间复杂度为$O(nlogn)$，符合本题数据范围
#include<bits/stdc++.h>
#define MAXN 100002
using namespace std;
inline int read(){
;
;
char c = getchar();
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
];
inline void print(int x){
;
)
fwrite( , stdout);
else{
){
x = -x;
fwrite( , stdout);
}
while(x){
output[--dirN] = x % + ;
x /= ;
}
fwrite(output + dirN , , strlen(output + dirN) , stdout);
}
fwrite( , , stdout);
}
struct node{
int sum , lMax , rMax , l , r;
}Tree[ * MAXN];
struct sortNum{//用于排序
int ind , num;
bool operator <(sortNum a){
return num < a.num;
}
}sorted[MAXN];
int num[MAXN] , root[MAXN];
, rMax , rSum , lMax , lSum;
inline int max(int a , int b){
return a > b ? a : b;
}
inline void swap(int &a , int &b){
int t = a;
a = b;
b = t;
}
//初始化一个所有叶子结点权值都为1的线段树
void init(int dir , int l , int r){
Tree[dir].sum = Tree[dir].lMax = Tree[dir].rMax = r - l + ;
if(l != r){
init(Tree[dir].l = ++cntNode , l , l + r >> );
init(Tree[dir].r = ++cntNode , (l + r >> ) + , r);
}
}
inline void pushup(int dir){
Tree[dir].lMax = max(Tree[Tree[dir].l].lMax , Tree[Tree[dir].l].sum + Tree[Tree[dir].r].lMax);
Tree[dir].rMax = max(Tree[Tree[dir].r].rMax , Tree[Tree[dir].r].sum + Tree[Tree[dir].l].rMax);
Tree[dir].sum = Tree[Tree[dir].l].sum + Tree[Tree[dir].r].sum;
}
//更新版本
void update(int now , int last , int l , int r , int dir){
if(l == r){
Tree[now].lMax = Tree[now].rMax = ;
Tree[now].sum = -;
}
else{
){
Tree[now].l = Tree[last].l;
update(Tree[now].r = ++cntNode , Tree[last].r , (l + r >> ) + , r , dir);
}
else{
Tree[now].r = Tree[last].r;
update(Tree[now].l = ++cntNode , Tree[last].l , l , l + r >> , dir);
}
pushup(now);
}
}
//区间和
int findSum(int dir , int l , int r , int L , int R){
if(L >= l && R <= r)
return Tree[dir].sum;
;
)
sum += findSum(Tree[dir].l , l , r , L , L + R >> );
)
sum += findSum(Tree[dir].r , l , r , (L + R >> ) + , R);
return sum;
}
//区间最大后缀
void findRightMax(int dir , int l , int r , int L , int R){
if(L >= l && R <= r){
rMax = max(rMax , Tree[dir].rMax + rSum);
rSum += Tree[dir].sum;
return;
}
)
findRightMax(Tree[dir].r , l , r , (L + R >> ) + , R);
)
findRightMax(Tree[dir].l , l , r , L , L + R >> );
}
//区间最大前缀
void findLeftMax(int dir , int l , int r , int L , int R){
if(L >= l && R <= r){
lMax = max(lMax , Tree[dir].lMax + lSum);
lSum += Tree[dir].sum;
return;
}
)
findLeftMax(Tree[dir].l , l , r , L , L + R >> );
)
findLeftMax(Tree[dir].r , l , r , (L + R >> ) + , R);
}
//二分check
//为了方便处理这里的代码与上面的公式稍有不同
inline bool check(int mid , int a , int b , int c , int d){
lSum = rSum = ;
lMax = rMax = -;
findRightMax(root[mid] , a , b - , , N);
findLeftMax(root[mid] , c + , d , , N);
, N) + lMax + rMax >= ;
}
int main(){
N = read();
;
; i <= N ; i++)
num[sorted[i].ind = i] = sorted[i].num = read();
init(root[] = , , N);
sort(sorted + , sorted + N + );
; i <= N ; i++)
update(root[i + ] = ++cntNode , root[i] , , N , sorted[i].ind);
for(int Q = read() ; Q ; Q--){
, b = (read() + lastans) % N + , c = (read() + lastans) % N + , d = (read() + lastans) % N + ;
if(a > b)
swap(a , b);
if(a > c)
swap(a , c);
if(a > d)
swap(a , d);
if(b > c)
swap(b , c);
if(b > d)
swap(b , d);
if(c > d)
swap(c , d);
, r = N;
while(l < r){
>> ;
if(check(mid , a , b , c , d))
l = mid;
else
r = mid - ;
}
printf("%d\n" , lastans = sorted[l].num);
}
;
}