P6107 题解

· · 题解

P6107 题解

题目大意

给定序列 a_0\sim a_{n+1}，其中 a_0=a_{n+1}=+\infty，对于所有 x\in[1,n] 与 \max\limits_{i\in[0,x),a_i\ge a_x}i 和 \min\limits_{i\in(x,n+1],a_x<a_i} i 连双向边。

数据范围：$n,q\le 5\times 10^5$。

思路分析

首先建大根笛卡尔树，注意到笛卡尔树上的每个大小为 4 的连通块，加上联通块根节点的左右父亲必定构成一个六元环，且不存在其他可能构成方式。

因此答案等于笛卡尔树上大小为 4 的连通块数量，但是不包含树根，因为 0,n+1 之间不连边。

注意到每次 a_x 变大相当于在笛卡尔树上不停上旋，暴力更新可以做到 \mathcal O(nq)。

但是复杂度过高，注意到 a_x 要么向左上旋要么向右上旋，通过势能分析可以证明旋转方向改变次数总和为 \mathcal O((n+q)\log n) 级别。

而注意到 a_x 不停左旋到一个点上，树结构总的变化只有 \mathcal O(1)，更新的点数也只有 \mathcal O(1)。

问题变成如何快速求 a_x 不断左旋会到哪里，先考虑这一段链的根在哪里，即求出 a_x 左边 \ge a_x 的第一个位置 u，v=rs_u 就是这段链的根。

右旋情况同理，为了减少常数，建议使用 zkw 线段树实现。

时间复杂度 \mathcal O((n+q)\log^2n)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e5+5;
int n,q,rt;
struct SegmentTree {
      const int N=1<<19;
      ll tr[1<<20];
      inline void add(int x,int v) {
            tr[x+=N]+=v;
            for(x>>=1;x;x>>=1) tr[x]=max(tr[x<<1],tr[x<<1|1]);
      }
      inline int lpos(int x,ll k) {
            for(x+=N+1;x>1;x>>=1) if((x&1)&&tr[x^1]>=k) break;
            if(x==1) return 0;
            for(x^=1;x<=N;) x=(tr[x<<1|1]>=k)?(x<<1|1):(x<<1);
            return x-N;
      }
      inline int rpos(int x,ll k) {
            for(x+=N-1;x>1;x>>=1) if((~x&1)&&tr[x^1]>=k) break;
            if(x==1) return n+1;
            for(x^=1;x<=N;) x=(tr[x<<1]>=k)?(x<<1):(x<<1|1);
            return x-N;
      }
}      TR;
ll a[MAXN],dp[MAXN][5],ans=0;
inline int cmp(int x,int y) { return x<y?a[x]<a[y]:a[x]<=a[y]; }
int ch[MAXN][2],fa[MAXN];
inline void upd(int u) {
      if(!u) return ;
      ans-=dp[u][4];
      bool ok=false;
      int ls=ch[u][0],rs=ch[u][1],cur;
      cur=dp[rs][1]+dp[ls][1];
      ok|=dp[u][2]!=cur,dp[u][2]=cur;
      cur=dp[rs][2]+dp[ls][1]*dp[rs][1]+dp[ls][2];
      ok|=dp[u][3]!=cur,dp[u][3]=cur;
      cur=dp[ls][3]+dp[ls][2]*dp[rs][1]+dp[ls][1]*dp[rs][2]+dp[rs][3];
      ok|=dp[u][4]!=cur,dp[u][4]=cur;
      ans+=dp[u][4];
      if(ok) upd(fa[u]);
}
int id[MAXN],stk[MAXN];
inline void init() {
      for(int i=1,tp=0;i<=n;++i) {
            bool add=false;
            while(tp&&cmp(stk[tp],i)) --tp,add=true;
            if(tp) ch[stk[tp]][1]=i;
            if(add) ch[i][0]=stk[tp+1];
            stk[++tp]=i;
      }
      iota(id+1,id+n+1,1),sort(id+1,id+n+1,cmp);
      rt=id[n],dp[0][0]=1;
      for(int i=1;i<=n;++i) {
            int u=id[i];
            fa[ch[u][0]]=fa[ch[u][1]]=id[i];
            dp[u][0]=dp[u][1]=1,upd(id[i]);
      }
}
inline void link(int f,int x,int c) { ch[f][c]=x,fa[x]=x?f:0; }
signed main() {
      scanf("%d",&n);
      for(int i=1;i<=n;++i) scanf("%lld",&a[i]),TR.add(i,a[i]);
      init(),scanf("%d",&q);
      for(int x,t;q--;) {
            scanf("%d%d",&x,&t),a[x]+=t;
            while(x!=rt) {
                  int f=fa[x];
                  if(cmp(x,f)) break;
                  if(x==ch[f][0]) {
                        int u=TR.lpos(f-1,a[f]),v=u?ch[u][1]:rt;
                        if(cmp(v,x)) {
                              link(f,ch[x][1],0);
                              link(x,v,1);
                              if(u) link(u,x,1);
                              else rt=x,fa[x]=0;
                        } else {
                              int w=TR.rpos(x+1,a[x]+1),y=ch[w][0];
                              link(f,ch[x][1],0);
                              link(x,y,1);
                              link(w,x,0);
                        }
                  } else {
                        int u=TR.rpos(f+1,a[f]+1),v=u<=n?ch[u][0]:rt;
                        if(cmp(v,x)) {
                              link(f,ch[x][0],1);
                              link(x,v,0);
                              if(u<=n) link(u,x,0);
                              else rt=x,fa[x]=0;
                        } else {
                              int w=TR.lpos(x-1,a[x]),y=ch[w][1];
                              link(f,ch[x][0],1);
                              link(x,y,0);
                              link(w,x,1);
                        }
                  }
                  upd(f),upd(x),upd(fa[x]);
            }
            TR.add(x,t);
            printf("%lld\n",ans-dp[rt][4]);
      }
      return 0;
}