题目
区间[l,r]是连续满足，[l,r]中的数字的权值区间是一段连续的。多次询问可以完包含一个区间的连续区间。区间长度尽量小，如果有多个输出左端点靠左的。
分析：
[l,r]区间是连续的，当且仅当区间内有(r-l)*2个相邻的关系，即(2,3)，(6,5)都是相邻关系。那么将询问离线，不断维护左端点到当前点的区间内的相邻关系的数量。
即当前点是i，那么如果pos[a[i]-1]<=i的话，在1~pos[a[i]-1]这些位置+1，表示从这些位置到i的区间，增加一个相邻关系。
如果一个点j开始到i的相邻关系的数量等于(i-j)，那么说明(j~i)区间是连续区间，这里两个相邻关系只算了一个。所以初始时在每个位置增加数字下标即可。
代码：
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<iostream> #include<cctype> #include<set> #include<queue> #include<vector> #include<map> #define pa pair<int,int> using namespace std; typedef long long LL; inline LL read() { LL x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f; } const int N = 100005; pa T[N << 2]; int tag[N << 2], pos[N], a[N], ans1[N], ans2[N], n; set< pa > s; vector< pa > q[N]; pa operator + (pa A, pa B) { return A.first > B.first ? A : B; } inline void col(int x,int y) { T[x].first += y, tag[x] += y; } inline void pushdown(int rt) { col(rt << 1, tag[rt]); col(rt << 1 | 1, tag[rt]); tag[rt] = 0; } void build(int l,int r,int rt) { if (l == r) { T[rt] = pa(l, l); return ; } int mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1); T[rt] = T[rt << 1] + T[rt << 1 | 1]; } void update(int l,int r,int rt,int L,int R) { if (L <= l && r <= R) { T[rt].first ++, tag[rt] ++; return ; } int mid = (l + r) >> 1; if (tag[rt]) pushdown(rt); if (L <= mid) update(l, mid, rt << 1, L, R); if (R > mid) update(mid + 1, r, rt << 1 | 1, L, R); T[rt] = T[rt << 1] + T[rt << 1 | 1]; } pa query(int l,int r,int rt,int L,int R) { if (L <= l && r <= R) return T[rt]; if (tag[rt]) pushdown(rt); int mid = (l + r) >> 1; if (R <= mid) return query(l, mid, rt << 1, L, R); else if (L > mid) return query(mid + 1, r, rt << 1 | 1, L, R); else return query(l, mid, rt << 1, L, R) + query(mid + 1, r, rt << 1 | 1, L, R); } bool check(pa x,int i) { pa now = query(1, n, 1, 1, -x.first); if (now.first == i) { ans1[x.second] = now.second, ans2[x.second] = i; return 1; } return 0; } int main() { n = read(); for (int i = 1; i <= n; ++i) a[i] = read(), pos[a[i]] = i; int m = read(); for (int i = 1; i <= m; ++i) { int l = read(), r = read(); q[r].push_back(pa(-l, i)); } build(1, n, 1); for (int i = 1; i <= n; ++i) { for (int j = 0; j < (int)q[i].size(); ++j) s.insert(q[i][j]); if (a[i] > 1 && pos[a[i] - 1] <= i) update(1, n, 1, 1, pos[a[i] - 1]); if (a[i] < n && pos[a[i] + 1] <= i) update(1, n, 1, 1, pos[a[i] + 1]); while (!s.empty()) if (check(*s.begin(), i)) s.erase(s.begin()); else break; } for (int i = 1; i <= m; ++i) printf("%d %d ", ans1[i], ans2[i]); return 0; }