题目
分析
析合树模板题。
先建出析合树。
就是要统计这样的点对的个数，那么在析合树上其实就是对于每一个点这样统计：
(1.) 对于合点：任意两个儿子之间可以任意选择，那么方案加上 (num imes (num-1)/2)
(2.) 对于析点：任何两个儿子都不能选，于是只有它本身这个节点是一个合法的，答案加一。
然后就完了。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
#define PII pair<int,int>
#define mp make_pair
const int N=2e5+5;
int n,m,a[N];
namespace RMQ1{
int Max[21][N],lg[N];
inline void Init(int n){
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++) Max[0][i]=a[i];
for(int i=1;i<=20;i++) for(int j=1;j+(1<<i)-1<=n;j++) Max[i][j]=max(Max[i-1][j],Max[i-1][j+(1<<(i-1))]);
return ;
}
inline int Query(int l,int r){
int tmp=lg[r-l+1];
return max(Max[tmp][l],Max[tmp][r-(1<<tmp)+1]);
}
}
namespace RMQ2{
int Min[21][N],lg[N];
inline void Init(int n){
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++) Min[0][i]=a[i];
for(int i=1;i<=20;i++) for(int j=1;j+(1<<i)-1<=n;j++) Min[i][j]=min(Min[i-1][j],Min[i-1][j+(1<<(i-1))]);
return ;
}
inline int Query(int l,int r){
int tmp=lg[r-l+1];
return min(Min[tmp][l],Min[tmp][r-(1<<tmp)+1]);
}
}
int Min[N<<2],ad[N<<2];
inline void Pushup(int x){Min[x]=min(Min[x<<1],Min[x<<1|1]);return ;}
inline void PushDown(int x){
if(!ad[x]) return ;
ad[x<<1]+=ad[x],ad[x<<1|1]+=ad[x];
Min[x<<1]+=ad[x],Min[x<<1|1]+=ad[x];ad[x]=0;
return ;
}
void Modify(int x,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr) return Min[x]+=v,ad[x]+=v,void();
PushDown(x);int mid=l+r>>1;
if(ql<=mid) Modify(x<<1,l,mid,ql,qr,v);
if(qr>mid) Modify(x<<1|1,mid+1,r,ql,qr,v);
Pushup(x);
return;
}
int Query(int x,int l,int r){
if(l==r) return l;
PushDown(x);int mid=l+r>>1;
if(!Min[x<<1]) return Query(x<<1,l,mid);
return Query(x<<1|1,mid+1,r);
}
inline bool Check(int l,int r){return RMQ1::Query(l,r)-RMQ2::Query(l,r)==r-l;}
int head[N],nex[N<<1],to[N<<1],idx;
inline void add(int u,int v){
nex[++idx]=head[u];
to[idx]=v;
head[u]=idx;
return ;
}
int fa[N][21],dep[N];
void dfs(int x,int f){
fa[x][0]=f;dep[x]=dep[f]+1;
for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(y==f) continue;
dfs(y,x);
}
return ;
}
inline int QueryKth(int u,int k){
for(int i=0;i<=20&&k;i++) if(k&(1<<i)) u=fa[u][i],k-=(1<<i);
return u;
}
inline int QueryLca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
u=QueryKth(u,dep[u]-dep[v]);
if(u==v) return u;
for(int i=20;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int rt,top1,top2,sta1[N],sta2[N],id[N],L[N],R[N],top,sta[N],cnt,typ[N],lc[N];
void Build(){
for(int i=1;i<=n;i++){
while(top1&&a[i]<=a[sta1[top1]]) Modify(1,1,n,sta1[top1-1]+1,sta1[top1],a[sta1[top1]]),top1--;
while(top2&&a[i]>=a[sta2[top2]]) Modify(1,1,n,sta2[top2-1]+1,sta2[top2],-a[sta2[top2]]),top2--;
Modify(1,1,n,sta1[top1]+1,i,-a[i]),sta1[++top1]=i;
Modify(1,1,n,sta2[top2]+1,i,a[i]),sta2[++top2]=i;
id[i]=++cnt;
L[cnt]=R[cnt]=i;
int tmp=Query(1,1,n),now=cnt;
while(top&&L[sta[top]]>=tmp){
if(typ[sta[top]]&&Check(lc[sta[top]],i)) R[sta[top]]=i,lc[sta[top]]=L[now],add(sta[top],now),now=sta[top--];
else if(Check(L[sta[top]],i)) typ[++cnt]=1,L[cnt]=L[sta[top]],R[cnt]=i,lc[cnt]=L[now],add(cnt,sta[top--]),add(cnt,now),now=cnt;
else{
add(++cnt,now);
do{
add(cnt,sta[top--]);
}while(top&&!Check(L[sta[top]],i));
L[cnt]=L[sta[top]],R[cnt]=i,add(cnt,sta[top--]),now=cnt;
}
}
sta[++top]=now;
Modify(1,1,n,1,i,-1);
}
rt=sta[1];
return ;
}
inline PII Query(int l,int r){
int x=id[l],y=id[r],Lca=QueryLca(x,y),posl=1,posr=1;
if(typ[Lca]&1) posl=L[QueryKth(x,dep[x]-dep[Lca]-1)],posr=R[QueryKth(y,dep[y]-dep[Lca]-1)];
else posl=L[Lca],posr=R[Lca];
return mp(posl,posr);
}
signed main(){
read(n);
for(int i=1;i<=n;i++) read(a[i]);
RMQ1::Init(n),RMQ2::Init(n);
Build();
dfs(rt,0);
read(m);
for(int i=1;i<=m;i++){
int x,y;
read(x),read(y);
PII t=Query(x,y);
write(t.first),putchar(' '),write(t.second),putchar('
');
}
return 0;
}
总结
暂无。