BZOJ2653 middle

			    <div class="post_brief"><p>
老久之前就看到过的题，不过不会做。今天晚上也是花了差不多俩小时才调过，虽然大概一个半小时都在纠结二分怎么写的问题。我没救了。</p>

考虑经典的中位数二分，是把≤x的数字取-1，>x的数取1，然后算最大子串看是否大于-1或1中的某一个，具体要看题目要求偶数是取上整还是下整什么的。

然后这题就把所有东西排序之后拿可持久化线段树把这个序列搞出来，然后照着之前的思路二分就好了。线段树用来维护最大和最小前缀和。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct dat {
int sm, s;
};
struct seg {
int l, r;
dat v[2];
seg *ls, *rs;
};
#define _l (long long int)
typedef pair <int, int> vpr;
typedef dat(*dat_mf)(const dat&, const dat&);
const int maxn = 20009;
const int maxnd = maxn * 19;
const dat null_str = {0, 0};
const dat neg_str0 = {-1, -1};
const dat neg_str1 = {-1, -1};
const dat pos_str0 = {1, 1};
const dat pos_str1 = {1, 1};
vpr a[maxn];
int n, m, q[4], lans, maxv;
seg slst[maxnd], *sp(slst), *rt[maxn];
#define mid(p) ((p->l+p->r)>>1)
dat ret;
inline dat merd0(const dat& a, const dat& b) {
ret. sm = a. sm + b. sm;
ret. s = min(a. s, a. sm + b. s);
return ret;
}
inline dat merd1(const dat& a, const dat& b) {
ret. sm = a. sm + b. sm;
ret. s = max(a. s, a. sm + b. s);
return ret;
}
const dat_mf dmf[2] = {merd0, merd1};
inline dat addSum(const int& v, const dat& a) {
ret. s = a. s + v;
ret. sm = a. sm + v;
return ret;
}
seg* sgtBuild(int l, int r) {
seg *p(sp ++);
p-> l = l;
p-> r = r;
if (l + 1 == r) {
p-> v[0] = neg_str0;
p-> v[1] = neg_str1;
}
else {
p-> ls = sgtBuild(l, mid(p));
p-> rs = sgtBuild(mid(p), r);
p-> v[0] = merd0(p-> ls-> v[0], p-> rs-> v[0]);
p-> v[1] = merd1(p-> ls-> v[1], p-> rs-> v[1]);
}
return p;
}
seg* sgtChg(seg* q, int p0) {
seg* p(sp ++);
p-> l = q-> l;
p-> r = q-> r;
if (p-> l + 1 == p-> r) {
p-> v[0] = pos_str0;
p-> v[1] = pos_str1;
}
else {
if (p0 < mid(p)) {
p-> ls = sgtChg(q-> ls, p0);
p-> rs = q-> rs;
}
else {
p-> ls = q-> ls;
p-> rs = sgtChg(q-> rs, p0);
}
p-> v[0] = merd0(p-> ls-> v[0], p-> rs-> v[0]);
p-> v[1] = merd1(p-> ls-> v[1], p-> rs-> v[1]);
}
return p;
}
int qv;
dat sgtQry(seg* p, int l, int r) {
if (p-> l == l && p-> r == r)
return p-> v[qv];
else if (r <= mid(p))
return sgtQry(p-> ls, l, r);
else if (l >= mid(p))
return addSum(p-> ls-> v[0]. sm, sgtQry(p-> rs, l, r));
else
return dmf[qv](sgtQry(p-> ls, l, mid(p)), sgtQry(p-> rs, mid(p), r));
}
void pstat(seg* p, bool sr = 1) {
if (p-> l + 1 == p-> r)
printf("%d “, p-> v[0]. sm);
else {
pstat(p-> ls, 0);
pstat(p-> rs, 0);
}
if (sr)
putchar(10);
}
int minSum(int x) {
int v0, v1;
qv = 1;
if (q[0] == 0)
v0 = max(0, sgtQry(rt[x], 0, q[1]). s);
else
v0 = sgtQry(rt[x], q[0] - 1, q[1]). s;
qv = 0;
v1 = sgtQry(rt[x], q[2], q[3] + 1). s;
return v1 - v0;
}
int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif
scanf("%d", &amp;n);
for (int i = 0; i &lt; n; ++ i)
	scanf("%d", &amp;a[i]. first), a[i]. second = i;
sort(a, a + n);
rt[0] = sgtBuild(0, n);
for (int i = 1; i &lt;= n; ++ i)
	rt[i] = sgtChg(rt[i - 1], a[i - 1]. second);
scanf("%d", &amp;m);
lans = 0;
while (m --) {
	for (int i = 0; i &lt; 4; ++ i) {
		scanf("%d", q + i); 
		q[i] = (_l q[i] + lans) % n;
	}
	sort(q, q + 4);
	int l(0), r(n - 1);
	while (l &lt; r) {
		int md((l + r + 1) &gt;&gt; 1);
		if (minSum(md) &gt; 0)
			r = md - 1;
		else
			l = md;
	}
	printf("%d\n", (lans = a[l]. first));
}

}

Comments