[CERC2017] Intrinsic Interval
程序员文章站
2022-03-30 11:31:16
首先理清这奇葩题意表述 给出一个$1$到$n$的排列$p[]$和$m$次询问,每次询问覆盖区间$[l,r]$的最小区间$[a,b]$,满足$[a,b]$内的元素排序后是连续整数序列。$n,m\le 10^5,\;1\le l\le r\le n$。 方便表述,称满足(省略)的区间是“好”的,否则是“ ......
首先理清这奇葩题意表述
给出一个\(1\)到\(n\)的排列\(p[]\)和\(m\)次询问,每次询问覆盖区间\([l,r]\)的最小区间\([a,b]\),满足\([a,b]\)内的元素排序后是连续整数序列。\(n,m\le 10^5,\;1\le l\le r\le n\)。
方便表述,称满足(省略)的区间是“好”的,否则是“坏”的,钦定空区间是“好”的。
罗列一些可能用到的、很显然的性质
- 好区间的长度等于最大值与最小值之差;
- 不相离的两个好区间的并是好区间;
- 不相离的两个好区间的交是好区间;
- 一个好区间内存在长度-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 %d\n",al[i],ar[i]); } return 0; }
推荐阅读
-
Python 数值区间处理_对interval 库的快速入门详解
-
INTERVAL 用法 mysql
-
AngularJS中$interval的用法详解
-
JVM详解之:HotSpot VM中的Intrinsic methods
-
Time - Time-interval Measurements
-
AngularJs定时器$interval 和 $timeout详解
-
已解决:Elasticsearch报错:Invalid interval specified, must be non-null and non-empty
-
[CERC2017] Intrinsic Interval
-
AngularJS定时器的使用与移除操作方法【interval与timeout】
-
AngularJS中$interval和$timeout的使用