P4747 [CERC2017] Intrinsic Interval

先说线段数做法

发现一个区间连续有一个性质：这个区间\([l,r]\)存在相邻两个数的对数是\(r-l\)

考虑离线下来，线段数维护每个区间存在相邻数的对数，当前是\(i\)，每次扫描新的一个\(a[i]\)进来，因为我扫描线是钦定了以\(i\)位右端点，所以若\(a[i]-1\)的位置在\(a[i]\)前面，我就将\([1,a[i]-1]\)区间+1，因为这样\(l\)取\([1,a[i]-1]\)这个范围，我的相邻对数都会+1。\(a[i]+1\)同理。

然后处理查询的话，存在合法的\([l,r]\)，就是\(query(l)=r-l\)，那我每次线段数赋初值都是下标，就只要判断是否等于\(r\)就可以了，就是看query(1~L)的最大值有没有等于R的。有一个必须的优化：如果\([1,l]\)最大值都到大不了\(r\)，那么\([1,l']\)且\(l'<l\)都不可以了

#include<bits/stdc++.h>
#define vd void 
#define MAXN 100005
#define pr std::pair<int,int>
#define fi first
#define se second 
int gi(){
	char c;int x=0,f=0;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))x=(x*10)+(c^48),c=getchar();
	return f?-x:x;
}
int n,m,a[MAXN],pos[MAXN];
std::vector<pr>q[MAXN];
std::priority_queue<pr>pq;
pr ans[MAXN];
namespace segtree{ //维护最大值和最大值的位置
#define ls x<<1
#define rs x<<1|1
#define mid ((l+r)>>1)
	int maxi[MAXN<<2],pmax[MAXN<<2],tag[MAXN<<2];
	vd up(int x){
		if(maxi[ls]>maxi[rs])maxi[x]=maxi[ls],/*std::cout<<"$"<<pmax[x]<<' '<<pmax[ls]<<'\n',*/pmax[x]=pmax[ls];
		else maxi[x]=maxi[rs],pmax[x]=pmax[rs];
	}
	vd addtag(int x,int w){maxi[x]+=w,tag[x]+=w;}
	vd down(int x){
		if(!tag[x])return;
		addtag(ls,tag[x]),addtag(rs,tag[x]);
		tag[x]=0;
	}
	vd build(int x,int l,int r){
		if(l==r)return maxi[x]=pmax[x]=l,void();
		build(ls,l,mid),build(rs,mid+1,r);up(x);
	}
	vd upd(int x,int l,int r,int qx,int qy,int w){
		if(r<qx||l>qy)return;
		if(l>=qx&&r<=qy){addtag(x,w);return;}
		down(x);
		upd(ls,l,mid,qx,qy,w),upd(rs,mid+1,r,qx,qy,w);
		up(x);
	}
	pr query(int x,int l,int r,int qx,int qy){
		if(r<qx||l>qy)return {0,0};
		if(l>=qx&&r<=qy)return std::make_pair(maxi[x],pmax[x]);
		down(x);
		pr wl=query(ls,l,mid,qx,qy),wr=query(rs,mid+1,r,qx,qy);
		if(wl.fi>wr.fi)return wl;
		else return wr;
	}
}
using namespace segtree;
bool calc(pr l,int r){
	pr tmp=query(1,1,n,1,l.fi);
	if(tmp.fi==r){ans[l.se]=std::make_pair(tmp.se,r);return 1;}
	return 0;
}
int main(){
	n=gi();for(int i=1;i<=n;i++)a[i]=gi(),pos[a[i]]=i;
	m=gi();
	for(int i=1;i<=m;i++){
		int x=gi(),y=gi();
		q[y].emplace_back(std::make_pair(x,i));
	}
	build(1,1,n);
	for(int i=1;i<=n;i++){
		if(a[i]-1>=1&&pos[a[i]-1]<=i)upd(1,1,n,1,pos[a[i]-1],1);
		if(a[i]+1<=n&&pos[a[i]+1]<=i)upd(1,1,n,1,pos[a[i]+1],1);
		for(pr j:q[i])pq.push(j);
		while(!pq.empty()){
			pr u=pq.top();
			if(calc(u,i))pq.pop();
			else break;
		}
	}
	for(int i=1;i<=m;i++)printf("%d %d\n",ans[i].fi,ans[i].se);
	return 0;
}

精髓还是把一个要求的东西挖掘一些能维护的性质或信息出来