2.3 闲话 & solution - 『如蝶般地舞蹈哪会恐高』

今天挺抽象的，上午一切正常，下午....

先是因为明天\(1\)号楼锁宿舍楼断电断水所以搬宿舍到\(9\)号楼

喵喵： 去二楼，没电就去三楼

然后去了二楼，没电没水啥也没有

去三楼，没电没水啥也没有

去四楼，有点有水其他奥赛

去五楼才找到的合适位置，在\(9518\)，快来找我玩？但是有宿管还是算了，也可能不是宿管

然后晚上去吃饭，因为去搬宿舍所以提前去的食堂，买完饭其他不知道高几的奥赛过来了，人数众多，感觉排队\(10min\)起步

似乎 \(\text{HZOI}2023\) 是倒数\(rk1\)到的，哈哈，估计明天我也倒数\(rk1\)了

晚上有\(\text{ABC}\)，我要上分我要上分我要上分

solution - 『主席树』

E. 『HNOI2017/AHOI2017』影魔

• 简要题意

  有一个长度为 \(n\) 的序列和两个值 \(p_1\) 和 \(p_2\)，序列中每个数都有一个值\(k_i\)

  对于\(i,j\),当不存在\(k_s\)使\(k_s\)大于\(k_i\)或\(k_j\)时让\(ans+p_1\)

  让\(c\)为\(\{i+1 \sim j-1\}\)的最大值，若 \(k_i<c<k_j\) 或 \(k_j<c<k_i\) 时让\(ans+p_2\)

  有\(m\)次询问，每次询问一个区间\(\{l \sim r\}\)的\(ans\)值

• 思路

  维护一个单调栈，求出每个\(a[i]\)对应左侧第一个它大\(j_1\)的和右侧第一个比它大的\(j_2\)

  首先可以发现对于\(\{i\sim i+1\}\)一定存在\(p_1\)的贡献 \((\)显然\()\)

  然后发现\(\{j_1+1 \sim i-1,j_2-1\sim i+1\}\)中都一定能做出\(p_2\)的贡献

  我们只要用总贡献减去不包含的贡献就行

• 代码

  就放个 main 函数里的吧，其他就线段树板子

  FastI>>n>>m>>p1>>p2;
  for(int i=1;i<=n;i++) 
      FastI>>a[i];
  sta[top]=0; 
  for(int i=1;i<=n;i++){
      while(top>0&&a[sta[top]]<a[i])top--;
      pl[i]=sta[top],sta[++top]=i;
  }  
  top=0;
  sta[top]=n+1;
  for(int i=n;i>=1;i--){
      while(top>0&&a[sta[top]]<a[i])top--;
      pr[i]=sta[top],sta[++top]=i;
  }
  for(int i=1;i<=n;i++){
      tot[1][pr[i]].push_back(i);
      tot[2][pl[i]].push_back(i);
  }
  int l,r;
  for(int i=1;i<=m;i++){
      FastI>>ql[i]>>qr[i];
      sum2[i]+=(qr[i]-ql[i])*p1;
      tot[3][ql[i]-1].push_back(i);
      tot[4][qr[i]].push_back(i);
  }  
  for(int i=1;i<=n;i++) {
      ans=0;
      for(int j=0;j<tot[1][i].size();j++){
          add(1,0,n,pl[tot[1][i][j]],pl[tot[1][i][j]],p1);
          add(1,0,n,pl[tot[1][i][j]]+1,tot[1][i][j]-1,p2);
      }
      for(int j=0;j<tot[2][i].size();j++){
          add(1,0,n,tot[2][i][j]+1,pr[tot[2][i][j]]-1,p2);
      }
      for(int j=0;j<tot[3][i].size();j++){
          ans=0;
          sum1[tot[3][i][j]]=query(1,0,n,ql[tot[3][i][j]],qr[tot[3][i][j]]);
      }
      for(int j=0;j<tot[4][i].size();j++){
          ans=0;
          sum2[tot[4][i][j]]+=query(1,0,n,ql[tot[4][i][j]],qr[tot[4][i][j]]);
      }
  }
  for(int i=1;i<=m;i++) 
      FastO<<sum2[i]-sum1[i]<<endl;
  

• 难存的情缘

树链剖分板子裸题，直接上边权转点权即可

代码不放了

晚上打ABC，4题遗憾离场(其实还没打完)