题解 P4747 【[CERC2017]Intrinsic Interval】

这题真的是一道思维好题。（感谢$i207M$神犇提供的思路qwq） 首先显而易见的有这个好区间的$max-min=r-l$，不过要做这题光有这个还不够，做这种题的时候就不能把这堆数完全当做离散量来处理，我们还需要找出一些别的性质。 我们发现包含着这段区间的好区间可能会有很多吧，考虑两个包着这个区间的好区间$[l_1,r_1]$和$[l_2,r_2]$，我们只讨论不包含的情况（因为包含的话外层那个区间肯定是没用的），不妨设$l_2>l_1$，那么这两个区间的交$[l_2,r_1]$也是包含着这个询问区间的。既然他是两个好区间的交，我们不妨考虑这样一个问题：$[l_2,r_1]$为什么既能和$[l_1,l_2-1]$拼成一个好区间，又能和$[r_1+1,r_2]$拼成一个好区间？我们发现$[l_2,r_1]$居然也是一个好区间！假如他不好的话，也就是说中间不连续，那么它最多只能和一边的区间拼成好区间。那么我们可以断言，**从$r$开始的第一个能够包住$[l,r]$的好区间的右端点对应的最短能够包住$[l,r]$的好区间就是唯一的答案**（~~这话好绕口啊……~~）。 于是就可以有这样一个思路，我们维护一个扫描线，把这些区间离线下来，然后想办法找出当前点$i$对应的右端点的好区间按照$l$的顺序（用个set维护）直接处理掉。那么考虑如何找所有可行的左端点。 其实题面上已经给了我们一个非常好的提示： _若它的一个子串 $\pi[a..b]$ 排序后是连续正整数，则称 $\pi[a..b]$ 是一个“好区间”。_ 我们发现把这玩意排序之后相邻的两项差为1对吧，那么这个好区间$[l,r]$有多少无序二元组$(i,j)$是相邻两项或者绝对值为1呢？显然就是$r-l$，显然对于无序二元组可以在靠后的那个位置统计。那么我们就可以把好区间换个定义了： _在$[l,r]$内有$r-l$个无序二元组的区间_ 那么我们现在枚举的是$r$，那么直接找$l$后面有多少个二元组即可。于是我们可以把式子变形，不妨设$val[l]$为$l$后面有多少个合法的二元组，那么显然就有$val[l]+l=r$当且仅当$[l,r]$为好区间。于是我们就可以换一种角度进行统计：开一个初始值为下标的线段树，然后我们在扫描线的时候如果发现$a_{i-1}$或者$a_{i+1}$在$i$前面就把1~他们的位置进行区间加，显然值为$i$的位置就是可行的好区间。 那么我们该如何在处理询问的时候找出区间内等于$i$的最后一个位置呢？表面上看起来是不可做的，但是不难发现一个区间内最多只会有$r-l$个合法的二元组（其实就是把他们排序一下看然后就不可能再多了），也就是说等于$i$的位置是区间内的最大值，既然是最大值就可以在线段树上乱搞了。 上代码~ ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<set> #include<vector> #define ls(_o) (_o<<1) #define rs(_o) ((_o<<1)|1) #define up(_o) maxn[_o]=max(maxn[ls(_o)],maxn[rs(_o)]) using namespace std; namespace ywy{ inline int get(){ int n=0;char c;while((c=getchar())||23333){ if(c>='0'&&c<='9')break;if(c=='-')goto s; }n=c-'0';while((c=getchar())||23333){ if(c>='0'&&c<='9')n=n*10+c-'0';else return(n); }s:while((c=getchar())||23333){ if(c>='0'&&c<='9')n=n*10-c+'0';else return(n); } } void print(int num){ if(num>=10)print(num/10);putchar(num%10+'0'); } int ansl[100001],ansr[100001]; typedef struct _qj{ int l;int r;int id; friend bool operator <(const _qj &a,const _qj &b){ if(a.l==b.l)return(a.id<b.id); return(a.l<b.l); } }qj; set<qj> st; int ints[100001],pos[100001],maxn[1000001],adds[1000001]; inline void down(int tree){ if(!adds[tree])return; int cjr=adds[tree]; adds[tree]=0; adds[ls(tree)]+=cjr;adds[rs(tree)]+=cjr; maxn[ls(tree)]+=cjr;maxn[rs(tree)]+=cjr; } int query(int rl,int rr,int l,int r,int tree,int num){//cout<<tree<<endl; down(tree);int mid=(l+r)>>1; if(rl>rr)return(-1); if(rl==l&&rr==r){ if(maxn[tree]!=num)return(-1);if(l==r)return(l); if(maxn[rs(tree)]==num)return(query(mid+1,r,mid+1,r,rs(tree),num)); return(query(l,mid,l,mid,ls(tree),num)); } if(rl>mid)return(query(rl,rr,mid+1,r,rs(tree),num)); if(rr<=mid)return(query(rl,rr,l,mid,ls(tree),num)); int cjr=query(mid+1,rr,mid+1,r,rs(tree),num); if(cjr!=-1)return(cjr); return(query(rl,mid,l,mid,ls(tree),num)); } vector<qj> vec[100001]; void inc(int rl,int rr,int l,int r,int tree){ if(rl==l&&rr==r){ adds[tree]++;maxn[tree]++;return; } int mid=(l+r)>>1;down(tree); if(rl>mid)inc(rl,rr,mid+1,r,rs(tree));else{ if(rr<=mid)inc(rl,rr,l,mid,ls(tree));else{ inc(rl,mid,l,mid,ls(tree)); inc(mid+1,rr,mid+1,r,rs(tree)); } }up(tree); } void build(int l，int r,int tree){ if(l==r){ maxn[tree]=l;return; } int mid=(l+r)>>1; build(l,mid,ls(tree)); build(mid+1,r,rs(tree));up(tree); } typedef set<qj>::iterator it; void ywymain(){ int n=get(); for(register int i=1;i<=n;i++)pos[ints[i]=get()]=i; int m=get(); for(register int i=1;i<=m;i++){ int l=get(),r=get(); qj cjr;cjr.l=l;cjr.r=r;cjr.id=i; vec[r].push_back(cjr); } build(1,n,1); for(register int i=1;i<=n;i++){ if(ints[i]!=1&&pos[ints[i]-1]<i)inc(1,pos[ints[i]-1],1,n,1); if(ints[i]!=n&&pos[ints[i]+1]<i)inc(1,pos[ints[i]+1],1,n,1); for(register int j=0;j<vec[i].size();j++){ st.insert(vec[i][j]); } while(st.begin()!=st.end()){ it lp=st.end();lp--;qj me=*lp; int cjr=query(1,me.l,1,n,1,i); if(cjr==-1)break; ansl[me.id]=cjr; ansr[me.id]=i;st.erase(lp); } } for(register int i=1;i<=m;i++)print(ansl[i]),putchar(' '),print(ansr[i]),putchar('\n')； } } int main(){ ywy::ywymain();return(0);//再见程序 } ```