[BZOJ4491]我也不知道题目名字是什么
试题描述
给定一个序列A[i]，每次询问l,r，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串
输入
第一行n，表示A数组有多少元素
接下来一行为n个整数A[i]
接下来一个整数Q，表示询问数量
接下来Q行，每行2个整数l，r
输出
对于每个询问，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串
输入示例
9 1 2 3 4 5 6 5 4 3 5 1 6 1 7 2 7 1 9 5 9
输出示例
6 6 5 6 4
数据规模及约定
对于100%的数据，m<=5n，任意时刻，每个地点的刷卡机台数不超过10000。N<=1.5×105
题解
因为“不上升”或“不下降”是独立的，我们先只考虑不下降的情况。
容易发现不下降的区间是没有交集的，所以从左往右依次给每个不下降区间标号，并维护每个标号的个数，那么对于询问[ql, qr]，令L = ql位置的标号，R = qr位置的标号，则有：
answer = qr - ql + 1 (L = R)
answer = max{ [ql, qr]中L标号的个数, [ql, qr]中R标号个数, 标号L+1~R-1个数的最大值 } (L < R)
对于不上升也是一样的。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <cstdlib>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *tail;
inline char Getchar() {
if(Head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 50010
#define maxlog 17
int n, q, A[maxn], up[maxn], U[maxn], stU[maxn], enU[maxn], down[maxn], D[maxn], stD[maxn], enD[maxn];
int qu[maxlog][maxn], qd[maxlog][maxn], Log[maxn];
void init(int* a, int n, int b[][maxn]) {
for(int i = 1; i <= n; i++) b[0][i] = a[i];
for(int j = 1; (1 << j) <= n; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++)
b[j][i] = max(b[j-1][i], b[j-1][i+(1<<j-1)]);
return ;
}
int query(int ql, int qr, int b[][maxn]) {
if(ql > qr) return -1;
int l = qr - ql + 1, t = Log[l];
return max(b[t][ql], b[t][qr-(1<<t)+1]);
}
int main() {
n = read();
for(int i = 1; i <= n; i++) A[i] = read();
up[1] = 1; U[1] = 1; stU[1] = enU[1] = 1;
for(int i = 2; i <= n; i++) {
if(A[i] >= A[i-1]) up[i] = up[i-1];
else up[i] = up[i-1] + 1;
U[up[i]]++;
if(!stU[up[i]]) stU[up[i]] = i;
enU[up[i]] = i;
}
down[1] = 1; D[1] = 1; stD[1] = enD[1] = 1;
for(int i = 2; i <= n; i++) {
if(A[i] <= A[i-1]) down[i] = down[i-1];
else down[i] = down[i-1] + 1;
D[down[i]]++;
if(!stD[down[i]]) stD[down[i]] = i;
enD[down[i]] = i;
}
Log[1] = 0;
for(int i = 2; i <= n; i++) Log[i] = Log[i>>1] + 1;
init(U, up[n], qu);
init(D, down[n], qd);
q = read();
while(q--) {
int ql = read(), qr = read();
int l = up[ql], r = up[qr], ll = down[ql], rr = down[qr];
int ans = min(max(max(query(l+1, r-1, qu), query(ll+1, rr-1, qd)), max(max(enU[l] - ql + 1, qr - stU[r] + 1), max(enD[ll] - ql + 1, qr - stD[rr] + 1))), qr - ql + 1);
printf("%d\n", ans);
}
return 0;
}