「BZOJ2653」middle

Description

数组ss左端点在[a,b][a,b]之间,右端点在[c,d][c,d]之间的所有子串中,最大的中位数。长度为nn的数组bb的中位数定义为b[n2]b[\lceil\frac{n}{2}\rceil]
其中a<b<c<da<b<c<d。位置也从00开始标号。

Input

第一行序列长度nn。接下来n行按顺序给出a中的数。
接下来一行QQ。然后QQ行每行a,b,c,da,b,c,d,我们令上个询问的答案是
x(如果这是第一个询问则x=0)。
令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}q=\{(a+x)\%n,(b+x)\%n,(c+x)\%n,(d+x)\%n\}
qq从小到大排序之后,令真正的
要询问的a=q[0]a=q[0],b=q[1]b=q[1],c=q[2]c=q[2],d=q[3]d=q[3]。  
输入保证满足条件。
第一行所谓“排过序”指的是从小到大排序!
n20000,Q25000n\leq 20000,Q\leq 25000

Output

QQ行依次给出询问的答案。

Sample Input

1
2
3
4
5
6
7
8
9
10
5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4

Sample Output

1
2
3
271451044
271451044
969056313

Solution

二分答案xx
ai=1a_i=1aixai\ge x否则ai=1ai=-1
问题转变成sum[b+1,c1]+sum[l,b]+sum[d,r]sum[b + 1,c - 1]+sum[l,b]+sum[d,r]最大值,其中l[a,b],r[c,d]l\in[a,b],r\in[c,d]
对于每一种权值建立线段树,每个节点统计最大左边和最大右边以及区间的aia_i和。
rt[i1]rt[i-1]转移到rt[i]rt[i] 显然就是所有ai=Vi1a_i=V_i-1的位置都变成1-1
但要注意,比如{2,3,3,3,3}\{2,3,3,3,3\}在插入的时候要一段段插入。
xx先插入{2}\{2\},再插入{3,3,3,3}\{3,3,3,3\}
代码里有两种一段段插入的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<vector>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 41000;
int n;
struct Node {
int v, i;
bool operator < (const Node &rhs) const {
return v < rhs.v;
}
}a[N];
int b[N], tot,rt[N];
struct Tree {
int l, r, lm, rm, s;
}t[N * 32];
void up(int o) {
t[o].lm = max(t[t[o].l].lm, t[t[o].l].s + t[t[o].r].lm);
t[o].rm = max(t[t[o].r].rm, t[t[o].r].s + t[t[o].l].rm);
t[o].s = t[t[o].l].s + t[t[o].r].s;
}
void build(int &o, int L, int R) {
o = ++tot;
if(L == R) {
t[o].lm = t[o].rm = t[o].s = 1;
return;
}
int mid = (L + R) >> 1;
if(L <= mid) build(t[o].l, L, mid);
if(R > mid) build(t[o].r, mid + 1, R);
up(o);
}
void insert(int pre, int &o, int L, int R, int x) {
o = ++tot;
t[o] = t[pre];
if(L == R) {
t[o].lm = t[o].rm = t[o].s = -1;
return;
}
int mid = (L + R) >> 1;
if(x <= mid)insert(t[pre].l, t[o].l, L, mid, x);
else insert(t[pre].r, t[o].r, mid + 1, R, x);
up(o);
}
Tree query(int o, int L, int R, int l, int r) {
if(!o || l > r) return (Tree){0,0,0,0,0};
if(l <= L && r >= R) return t[o];
int mid = (L + R) >> 1;
if(r <= mid) return query(t[o].l, L, mid, l, r);
if(l > mid) return query(t[o].r, mid + 1, R, l, r);
Tree x = query(t[o].l, L, mid, l, r);
Tree y = query(t[o].r, mid + 1, R, l, r);
Tree z;
z.s = x.s + y.s;
z.lm = max(x.lm, x.s + y.lm);
z.rm = max(y.rm, y.s + x.rm);
return z;
}
int get(int t, int *q) {
Tree x = query(rt[t], 1, n, q[1], q[2]);
Tree y = query(rt[t], 1, n, q[0], q[1] - 1);
Tree z = query(rt[t], 1, n, q[2] + 1, q[3]);
return x.s + max(y.rm, 0) + max(z.lm,0);
}
vector<int>c[N];
int main() {
n = read();
for(int i = 1 ; i <= n; ++i) a[i].v = read(), a[i].i = i, b[i] = a[i].v;
*b = n;
sort(b + 1, b + 1 + *b);
*b = unique(b + 1, b + 1 + *b) - b - 1;
for(int i = 1; i <= n; ++i) a[i].v = lower_bound(b + 1, b + 1 + *b, a[i].v) - b, c[a[i].v].pb(i);
sort(a + 1, a + 1 + n);
build(rt[0], 1, n);
a[n + 1].v = 1e9 + 2333;
int p = n + 1;
/* for(int i = 1; i <= n; ++i) if(a[i].v != a[i - 1].v) { //坑点啊
rt[a[i].v] = rt[a[i].v - 1];
while(p < i) insert(rt[a[i].v], rt[a[i].v], 1, n, a[p].i), ++p;
p = n + 1;
if(a[p].v != a[i].v) p = i;
}*/
/* for(int i = 1; i <= n; ++i) if(a[i].v != a[i - 1].v) {
if(i > 1)insert(rt[a[i].v - 1], rt[a[i].v], 1, n, a[i - 1].i); // a[i - 1].i会等于1
else rt[a[i].v] = rt[a[i].v - 1];
while(p < i - 1) insert(rt[a[i].v], rt[a[i].v], 1, n, a[p].i), ++p;
p = i;
}*/
for(int i = 1; i <= *b; ++i) { //尽量想到去用vector
rt[i] = rt[i - 1];
for(int j = c[i - 1].size() - 1;~j;--j) insert(rt[i], rt[i], 1, n, c[i-1][j]);
}
int Q = read();
int q[4], ans = 0;
while(Q--) {
for(int i = 0; i < 4; ++i) q[i] = (read() + ans) % n + 1;
sort(q, q + 4);
int r = *b + 1, l = 1;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(get(mid, q) >= 0) l = mid;
else r = mid;
}
writeln(ans = b[l]);
}
return 0;
}