BZOJ5259/洛谷P4747: [Cerc2017]区间
2019.8.5 [HZOI]NOIP模拟测试13 C.优美序列
思维好题，然而当成NOIP模拟题↑真的好吗...
洛谷和BZOJ都有，就不设密码了。
首先，手玩样例可以发现满足条件的区间是不满足单调性的，所以二分左右端点、单调队列、双指针什么的就不可能了。
然后不会了...
不难看出，一段满足要求的区间[L,R]，符合\(val_{max}-val_{min}=R-L\)，val是数值。
50pts暴力：对val建st表，每次询问枚举序列的子区间，用st表\(O(1)\)判断是否可行，复杂度\(O(n^2m)\)。考试数据可能弱化过，洛谷和BZOJ上应该水不到50pts。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,mx,mn,a[N],Lg[N],f[22][N],g[22][N];
inline void In(int &num){
char c=getchar();
for(num=0;!isdigit(c);c=getchar());
for(;isdigit(c);num=num*10+c-48,c=getchar());
}
void st_init(){
Lg[0]=-1;
for(int i=1;i<=n;++i) f[0][i]=g[0][i]=a[i],Lg[i]=Lg[i>>1]+1;
for(int i=1;i<=20;++i)
for(int j=1;j+(1<<i)-1<=n;++j)
f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))]),
g[i][j]=min(g[i-1][j],g[i-1][j+(1<<(i-1))]);
}
void query(int l,int r){
int d=Lg[r-l+1];
mx=max(f[d][l],f[d][r-(1<<d)+1]);
mn=min(g[d][l],g[d][r-(1<<d)+1]);
}
int main(){
In(n);
for(int i=1;i<=n;++i) In(a[i]);
st_init();
In(m);
for(int i=1,l,r,Mx,Mn;i<=m;++i){
In(l);In(r);
query(l,r);
Mx=mx;Mn=mn;
for(int j=r-l+1;j<=n;++j){
for(int k=1;k+j-1<=n;++k){
query(k,k+j-1);
if(mx-mn==j-1&&mx>=Mx&&mn<=Mn){
printf("%d %d\n",k,k+j-1);
goto nxt;
}
}
}
nxt:;
}
return 0;
}92pts暴力：模拟找答案的过程。记pos[i]为i在原序列中的下标，读入时pos[val[i]]=i。对val和pos数组建st表。
例如样例一，如果询问[5,7]的数（6 4 2），在val的st表中查到下标在[5,7]之间的最小值是2、最大值是6。所以2~6这五个数都要出现。然后在pos的st表中查数字2~6在序列中的出现位置：3出现在第一位，2出现在最后一位，所以整个序列都要选。此时序列中最大值是7，最小值是1，序列为[1,7]，恰好符合，得到答案。
模拟此过程即可，复杂度未知。92pts还是指考试的弱数据，需要轻度卡常，为了可读性只放一份未卡常的。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,mx,mn,Mx,Mn,a[N],pos[N],Lg[N],f[22][N],g[22][N],t[22][N],s[22][N];
inline void In(int &num){
char c=getchar();
for(num=0;!isdigit(c);c=getchar());
for(;isdigit(c);num=num*10+c-48,c=getchar());
}
void st_init(){
Lg[0]=-1;
for(int i=1;i<=n;++i) f[0][i]=g[0][i]=a[i],t[0][i]=s[0][i]=pos[i],Lg[i]=Lg[i>>1]+1;
for(int i=1;i<=20;++i)
for(int j=1;j+(1<<i)-1<=n;++j)
f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))]),
g[i][j]=min(g[i-1][j],g[i-1][j+(1<<(i-1))]),
t[i][j]=max(t[i-1][j],t[i-1][j+(1<<(i-1))]),
s[i][j]=min(s[i-1][j],s[i-1][j+(1<<(i-1))]);
}
void query_val(int l,int r){
int d=Lg[r-l+1];
mx=max(f[d][l],f[d][r-(1<<d)+1]);
mn=min(g[d][l],g[d][r-(1<<d)+1]);
}
void query_pos(int l,int r){
int d=Lg[r-l+1];
Mx=max(t[d][l],t[d][r-(1<<d)+1]);
Mn=min(s[d][l],s[d][r-(1<<d)+1]);
}
int main(){
In(n);
for(int i=1;i<=n;++i) In(a[i]),pos[a[i]]=i;
st_init();
In(m);
for(int i=1,l,r;i<=m;++i){
In(l);In(r);
query_val(l,r);
query_pos(mn,mx);
while(Mx-Mn!=mx-mn){
query_val(Mn,Mx);
query_pos(mn,mx);
}
printf("%d %d\n",Mn,Mx);
}
return 0;
}100pts：
考试的题解
分治法，离线处理。假设现在处理的询问都包含在[L,R] 中，设mid=(L+R)/2。然后将包含在[L,mid],[mid+1,R] 的区间分治处理。剩下的就是包含[mid,mid+1]的询问，然后找出包含[mid,mid+1]的所有优美区间，用这些优美区间更新询问的答案。
时间复杂度\(O(n(logn)^2)\)。
序列分治不太会，咕了。
介绍两种思路。
方法一：
扫描线+线段树
洛谷题解区的dalao想到的。
这个思路不太容易理解，并且我的表达能力确实有限，如果不看代码下面的话应该是看不懂的，建议去luogu题解区看下dalao解释，并结合代码理解。
考虑如何判断一个区间是连续段，当且仅当区间内\((x,x+1)\)的对数为\(r−l\)。
设区间\([l,r]\)内\((x,x+1)\)的对数为\(c(l,r)\)。
我们可以枚举右端点r，用线段树维护\(l+c(l,r)\)。可以发现合法仅当\(l+c(l,r)=r\)，并且\(l+c(l,r)\)最大值为r，所以只需要维护最大值以及最大值的位置就可以了。
实现的时候把所有询问离线，枚举到了询问的r端点就把询问丢进一个优先队列里面，以询问的l端点为关键字，堆顶是l最大的。每次如果能找到答案就pop，否则就break，因为查询的是[1,l]的最大值，l越大一定越容易找到答案。
简单说一下这样做的正确性：
对于询问[ql,qr]，我们从qr开始枚举答案的右端点R，找到第一个能覆盖[ql,qr]的L，区间[L,R]就是答案。
可以反证：![BZOJ5259/洛谷P4747: [Cerc2017]区间](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pLzRiMTc2Mzk4NTE4NWQwMTVkNTJhMTg3ZGZhYWFlZWM5MS5qcGc%3D.jpg?w=700&webp=1 "BZOJ5259/洛谷P4747: [Cerc2017]区间")
假如我们枚举到R1，找到区间[L1,R1]是好区间，作为答案，但答案应该是[L2,R2]。那么[L1,R1]和[L2,R2]都是好区间。实际上[L2,R1]也是好区间，因为如果[L2,R1]的数不连续就不可能成为两个好区间的交集。于是我们枚举到R1得到的答案实际上是L2，[L2,R1]正是最优解。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef pair<int,int> Node;
int n,m,Mx,Mx_pos,a[N],pos[N];
Node ans[N];
priority_queue<Node> heap;
vector<Node> que[N];
struct tree_node{
int l,r,mx,pos,tag;
#define l(p) (node[p].l)
#define r(p) (node[p].r)
#define mx(p) (node[p].mx)
#define pos(p) (node[p].pos)
#define tag(p) (node[p].tag)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l(p)+r(p))>>1)
}node[N<<2];
void pup(int p){
mx(p)=max(mx(ls(p)),mx(rs(p)));
pos(p)=mx(ls(p))>mx(rs(p))?pos(ls(p)):pos(rs(p));
}
void build(int p,int l,int r){
l(p)=l;r(p)=r;
if(l==r) return (void) (mx(p)=pos(p)=l);
build(ls(p),l,mid);
build(rs(p),mid+1,r);
pup(p);
}
void pdown(int p){
if(tag(p)){
mx(ls(p))+=tag(p);tag(ls(p))+=tag(p);
mx(rs(p))+=tag(p);tag(rs(p))+=tag(p);
tag(p)=0;
}
}
void modify(int p,int L,int R){
if(L<=l(p)&&r(p)<=R) return (void) (++mx(p),++tag(p));
pdown(p);
if(L<=mid) modify(ls(p),L,R);
if(R>mid) modify(rs(p),L,R);
pup(p);
}
void query(int p,int L,int R){
if(L<=l(p)&&r(p)<=R){
if(mx(p)>=Mx) Mx=mx(p),Mx_pos=pos(p);
return;
}
pdown(p);
if(L<=mid) query(ls(p),L,R);
if(R>mid) query(rs(p),L,R);
}
bool check(const Node &w,int R){
Mx=0;
query(1,1,w.first);
if(Mx==R) {ans[w.second]=make_pair(Mx_pos,R);return true;}
return false;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&m);
for(int i=1,l,r;i<=m;++i){
scanf("%d%d",&l,&r);
que[r].push_back(make_pair(l,i));
}
for(int i=1;i<=n;++i){
pos[a[i]]=i;
if(pos[a[i]-1]) modify(1,1,pos[a[i]-1]);
if(pos[a[i]+1]) modify(1,1,pos[a[i]+1]);
for(unsigned j=0;j<que[i].size();++j) heap.push(que[i][j]);
while(!heap.empty()){
if(check(heap.top(),i)) heap.pop();
else break;
}
}
for(int i=1;i<=m;++i) printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}方法二：
线段树优化建图+tarjan缩点
可以去dky博客看解释。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5,inf=0x3f3f3f3f;
int n,m,a[N];
struct Graph{
int Top,head[N],ver[N],nxt[N];
inline void add(int u,int v){
ver[++Top]=v;
nxt[Top]=head[u];
head[u]=Top;
}
}G1,G2;
struct Node{
int l,r;
inline Node(int l=inf,int r=-inf):l(l),r(r) {}
inline Node operator + (const Node &b)const{
return Node(min(l,b.l),max(r,b.r));
}
}t1[N],t2[N];
struct SegmentTree{
Node t[N];
#define mid ((l+r)>>1)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
void modify(int p,int l,int r,int pos,const Node &val){
if(l==r) return (void) (t[p]=val);
pos<=mid?modify(ls(p),l,mid,pos,val):modify(rs(p),mid+1,r,pos,val);
t[p]=t[ls(p)]+t[rs(p)];
}
Node query(int p,int l,int r,int L,int R){
if(L<=l&&r<=R) return t[p];
if(L<=mid&&R>mid) return query(ls(p),l,mid,L,R)+query(rs(p),mid+1,r,L,R);
else if(L<=mid) return query(ls(p),l,mid,L,R);
else return query(rs(p),mid+1,r,L,R);
}
}seg[2];
int rt,tot,ls[N],rs[N];
void build_graph(int &p,int l,int r){
if(l==r) return (void) (p=l);
p=++tot;
build_graph(ls[p],l,mid);
build_graph(rs[p],mid+1,r);
G1.add(p,ls[p]);
G1.add(p,rs[p]);
}
void Link(int p,int l,int r,int u,int L,int R){
if(L<=l&&r<=R) return G1.add(u,p);
if(L<=mid) Link(ls[p],l,mid,u,L,R);
if(R>mid) Link(rs[p],mid+1,r,u,L,R);
}
int tp,tim,scc_num,dfn[N],low[N],st[N],c[N];
void tarjan(int u){
st[++tp]=u;
dfn[u]=low[u]=++tim;
for(int i=G1.head[u];i;i=G1.nxt[i]){
int v=G1.ver[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!c[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
++scc_num;
int y;
do{
y=st[tp--];
c[y]=scc_num;
}while(y!=u);
}
}
bool vis[N];
void dfs(int u){
if(vis[u]) return;
vis[u]=true;
for(int i=G2.head[u];i;i=G2.nxt[i]){
int v=G2.ver[i];
dfs(v);
t2[u]=t2[u]+t2[v];
}
}
int main(){
scanf("%d",&n);
tot=n;
build_graph(rt,1,n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) seg[0].modify(1,1,n,a[i],Node(i,i));
for(int i=2;i<=n;++i){
int x=min(a[i-1],a[i]),y=max(a[i-1],a[i]);
t1[i]=seg[0].query(1,1,n,x,y);
Link(rt,1,n,i,t1[i].l+1,t1[i].r);//i表示[i-1,i]两个数
}
for(int i=1;i<=tot;++i) if(!dfn[i]) tarjan(i);
for(int u=1;u<=tot;++u){
for(int i=G1.head[u];i;i=G1.nxt[i]){
int v=G1.ver[i];
if(c[u]!=c[v]) G2.add(c[u],c[v]);
}
}
for(int i=1;i<=tot;++i) t2[c[i]]=t2[c[i]]+t1[i];
for(int i=1;i<=scc_num;++i) dfs(i);
for(int i=2;i<=n;++i) seg[1].modify(1,1,n,i,t2[c[i]]);
scanf("%d",&m);
for(int i=1,l,r;i<=m;++i){
scanf("%d%d",&l,&r);
if(l==r) printf("%d %d\n",l,r);
else{
Node ans=seg[1].query(1,1,n,l+1,r);
printf("%d %d\n",ans.l,ans.r);
}
}
return 0;
}