c/c++语言开发共享[CERC2017] Intrinsic Interval

首先理清这奇葩题意表述

给出一个(1)到(n)的排列(p[])和(m)次询问，每次询问覆盖区间([l,r])的最小区间([a,b])，满足([a,b])内的元素排序后是连续整数序列。(n,mle 10^5,;1le lle rle n)。

方便表述，称满足（省略）的区间是“好”的，否则是“坏”的，钦定空区间是“好”的。

罗列一些可能用到的、很显然的性质

1. 好区间的长度等于最大值与最小值之差；
2. 不相离的两个好区间的并是好区间；
3. 不相离的两个好区间的交是好区间；
4. 一个好区间内存在长度-1个值差1的无序二元组（邻数对）

我们形式化的描述性质4：设(a[i])表示(i)到(r)的邻数对数，若([l,r])是好区间，则(a[l]=r-l)，或者说(a[l]+l=r)。令(a[i]=a[i]+i)考虑从左往右扫描区间右端(r)，同时维护关于(r)的(a[])，则与(r)构成好区间的(l)满足(a[l]=r)，显然这是(a[])中最大的元素。

至此使用线段树维护区间最大值和最大值中的最大下标（好区间应将量短）即可。

#include <bits/stdc++.h> #define ls (x<<1) #define rs (x<<1|1) using namespace std; const int n=1e5+10;  int mxa[n<<2],rp[n<<2],tag[n<<2]; void update(int x) {     if(mxa[ls]==mxa[rs]) mxa[x]=mxa[ls],rp[x]=rp[rs];     else if(mxa[ls]>mxa[rs]) mxa[x]=mxa[ls],rp[x]=rp[ls];     else mxa[x]=mxa[rs],rp[x]=rp[rs]; } void pushdown(int x) {     if(!tag[x]) return;     mxa[ls]+=tag[x],tag[ls]+=tag[x];     mxa[rs]+=tag[x],tag[rs]+=tag[x];     tag[x]=0;  } void build(int x,int l,int r) {     if(l==r) {mxa[x]=rp[x]=l; return;}     int mid=(l+r)>>1;     build(ls,l,mid);build(rs,mid+1,r);     update(x); } void modify(int x,int l,int r,int l,int r) {     if(l<=l&&r<=r) {mxa[x]++,tag[x]++; return;}     int mid=(l+r)>>1; pushdown(x);     if(l<=mid) modify(ls,l,mid,l,r);     if(mid<r) modify(rs,mid+1,r,l,r);     update(x); } int query(int x,int l,int r,int p,int w) {     if(mxa[x]<w) return 0;     if(r<=p) return rp[x];     int mid=(l+r)>>1; pushdown(x);     if(mid<p&&mxa[rs]>=w) {         int tmp=query(rs,mid+1,r,p,w);         if(tmp) return tmp; //似乎可以蛮会被卡称o(n)      }     return query(ls,l,mid,p,w); }  int n,m; int a[n],pos[n],al[n],ar[n]; stack<pair<int,int>> d[n]; priority_queue<pair<int,int>> stk;  bool solve(int r) {     if(!stk.size()) return 0;     int ql=stk.top().first,qid=stk.top().second;     al[qid]=query(1,1,n,ql,r);     if(!al[qid]) return 0;     ar[qid]=r; stk.pop(); return 1; }  int main() {     scanf("%d",&n);     for(int i=1; i<=n; ++i) {         scanf("%d",&a[i]);         pos[a[i]]=i;     }      scanf("%d",&m);     for(int i=1,x,y; i<=m; ++i) {         scanf("%d%d",&x,&y);         d[y].push(make_pair(x,i));     }     build(1,1,n);     for(int i=1; i<=n; ++i) {         if(a[i]>1&&pos[a[i]-1]<i) modify(1,1,n,1,pos[a[i]-1]);         if(a[i]<n&&pos[a[i]+1]<i) modify(1,1,n,1,pos[a[i]+1]);         while(d[i].size()) stk.push(d[i].top()),d[i].pop();         while(solve(i));     }        for(int i=1; i<=m; ++i) {         printf("%d %dn",al[i],ar[i]);     }     return 0; }