Description
详见OJ
Solution
考场先想到(O(nlog^2n))的线段树，发现过不了。于是开始“异想天开”。
最后神奇想到分块。
我们对于(a[])维护一个(to[i])。
(to[i])表示(a[i]>=b[j])的最大的(j)。
维护时用分块来标记防止修改的区间太大。
赛后同学说分块是(O(m根号n))的，我才发现时间好像过不了。。。
但我好像没有一个点(TLE)。。。
不停改细节最后成功(AC)，(700+ms)没有卡线。
分块打法好！
Code
（分块）
#include <cstdio>
#include <cmath>
#define N 500010
#define mem(x, a) memset(x, a, sizeof x)
#define fo(x, a, b) for (int x = a; x <= b; x++)
#define fd(x, a, b) for (int x = a; x >= b; x--)
using namespace std;
int n, m, a[N], b[N], to[N], now = 0;
int bl[N], val[N], st, zuo[N], you[N];
bool bz[N];
inline int read()
{
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return x;
}
inline int max(int x, int y) {return x > y ? x : y;}
inline int solve(int x) {return bz[bl[x]] ? val[bl[x]] : to[x];}
void gave(int x)
{
if (! bz[x]) return;
fo(i, zuo[x], you[x]) to[i] = val[x];
bz[x] = 0;
}
int main()
{
freopen("median.in", "r", stdin);
freopen("median.out", "w", stdout);
n = read(), m = read(); st = sqrt(n);
fo(i, 1, n)
{
a[i] = read();
bl[i] = (i - 1) / st + 1;
if (! zuo[bl[i]]) zuo[bl[i]] = i;
you[bl[i]] = i;
}
fo(i, 1, n) b[i] = read();
fo(i, 1, n)
{
while (now < n && a[i] >= b[now + 1]) now++;
to[i] = now;
}
to[0] = 0, to[n + 1] = n;
while (m--)
{
int opt = read();
if (opt == 1)
{
int x = read(), y = read(), z = read();
if (x == 0)
{
int l = solve(y - 1), r = solve(y + 1), mid;
while (l <= r)
{
mid = l + r >> 1;
if (z >= b[mid]) l = mid + 1;
else r = mid - 1;
}
a[y] = z;
if (solve(y) != l - 1)
to[y] = l - 1, bz[bl[y]] = 0;
}
else
{
int l = 1, r = n, mid, le, ri;
while (l <= r)
{
mid = l + r >> 1;
if (a[mid] >= b[y - 1]) r = mid - 1;
else l = mid + 1;
}
le = r + 1;
l = r, r = n;
while (l <= r)
{
mid = l + r >> 1;
if (a[mid] < b[y + 1]) l = mid + 1;
else r = mid - 1;
}
ri = l - 1;
l = le, r = ri;
while (l <= r)
{
mid = l + r >> 1;
if (a[mid] >= z) r = mid - 1;
else l = mid + 1;
}
if (le <= r)
{
if (bl[le] == bl[r])
{
gave(bl[le]);
fo(i, le, r) to[i] = y - 1;
}
else
{
fo(i, bl[le] + 1, bl[r] - 1)
bz[i] = 1, val[i] = y - 1;
gave(bl[le]);
fo(i, le, you[bl[le]]) to[i] = y - 1;
gave(bl[r]);
fo(i, zuo[bl[r]], r) to[i] = y - 1;
}
}
r++;
if (r <= ri)
{
if (bl[r] == bl[ri])
{
gave(bl[r]);
fo(i, r, ri) to[i] = y;
}
else
{
fo(i, bl[r] + 1, bl[ri] - 1)
bz[i] = 1, val[i] = y;
gave(bl[r]);
fo(i, r, you[bl[r]]) to[i] = y;
gave(bl[ri]);
fo(i, zuo[bl[ri]], ri) to[i] = y;
}
}
b[y] = z;
}
}
else
{
int l1 = read(), r1 = read(), l2 = read(), r2 = read();
int sum = (r1 - l1 + 1 + r2 - l2 + 1) / 2 + 1;
if (a[r1] <= b[l2])
{
if (r1 - l1 + 1 >= sum) printf("%d
", a[l1 + sum - 1]);
else printf("%d
", b[l2 + sum - (r1 - l1 + 1) - 1]);
}
else if (a[l1] >= b[r2])
{
if (r2 - l2 + 1 >= sum) printf("%d
", b[l2 + sum - 1]);
else printf("%d
", a[l1 + sum - (r2 - l2 + 1) - 1]);
}
else
{
int l = l1, r = r1, mid, num;
while (l <= r)
{
mid = l + r >> 1;
num = mid - l1 + 1;
if (solve(mid) > r2) num += r2 - l2 + 1;
else if (solve(mid) >= l2) num += solve(mid) - l2 + 1;
if (num == sum) {r = mid - 1; break;}
else if (num >= sum) r = mid - 1;
else l = mid + 1;
}
r++;
num = r - l1 + 1;
if (solve(r) > r2) num += r2 - l2 + 1;
else if (solve(r) >= l2) num += solve(r) - l2 + 1;
if (r <= r1 && num == sum) printf("%d
", a[r]);
else printf("%d
", b[l2 + sum - (r - l1 + 1)]);
}
}
}
return 0;
}
不过，听完讲后，发现这题分治做起来好容易啊。