[DS记录]CF997E Good Subsegments

· · 个人记录

题意 : 给出长度为 n 的一个排列。

定义一个集合是连续的,当且仅当 \max S-\min S+1=|S|

允许离线。$n,q\leq 1.2\times 10^5$ ,时限 $\texttt{7s}$。 ------------ - $\rm Sub\ Ploblem$ : [CF526F Pudding Monsters](https://www.luogu.com.cn/problem/CF526F) 考虑枚举右端点,并维护每个后缀(左端点)的答案。 新加入的位置会对所有后缀都产生影响。 可以使用类似单调栈的技巧,可以使用若干次区间加法完成对 $\min$ 和 $\max$ 的维护。 但是,我们发现统计 $\max S-\min S+1=|S|$ 的后缀的个数并不容易。 $\Rightarrow \max [l,r]-\min [l,r]+1=(r-l+1) \Rightarrow \max [l,r]-\min [l,r]+l=r

而又可以证明 \max [l,r]-\min [l,r]+l\geq r ,所以只需要把位置 l 的初始值设为 l ,然后维护最小值以及最小值个数即可。

#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 300500
using namespace std;
int read(){
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
struct Node{
  int x,c,tg;
  inline void add(int _t)
  {x+=_t;tg+=_t;}
}a[MaxN<<2];
inline void up(int u)
{
  int l=u<<1,r=u<<1|1;
  a[u].x=min(a[l].x,a[r].x);
  a[u].c=(a[l].x==a[r].x) ? a[l].c+a[r].c
        : (a[l].x<a[r].x) ? a[l].c : a[r].c;
}
inline void ladd(int u)
{
  if (a[u].tg){
    a[u<<1].add(a[u].tg);
    a[u<<1|1].add(a[u].tg);
    a[u].tg=0;
  }
}
int n,wfl,wfr,wfc;
void add(int l=1,int r=n,int u=1)
{
  if (wfl<=l&&r<=wfr)
    {a[u].add(wfc);return ;}
  int mid=(l+r)>>1;ladd(u);
  if (wfl<=mid)add(l,mid,u<<1);
  if (mid<wfr)add(mid+1,r,u<<1|1);
  up(u);
}
void build(int l=1,int r=n,int u=1)
{
  if (l==r){a[u].x=l;a[u].c=1;return ;}
  int mid=(l+r)>>1;
  build(l,mid,u<<1);
  build(mid+1,r,u<<1|1);
  up(u);
}
int x[MaxN],stk0[MaxN],t0,stk1[MaxN],t1;
int main()
{
  n=read();
  for (int i=1,t;i<=n;i++)
    {t=read();x[t]=read();}
  build();
  ll ans=0;
  for (int i=1;i<=n;i++){
    while(t0&&x[stk0[t0]]>x[i]){
      wfl=stk0[t0-1]+1;wfr=stk0[t0];
      wfc=x[stk0[t0--]]-x[i];add();
    }while(t1&&x[stk1[t1]]<x[i]){
      wfl=stk1[t1-1]+1;wfr=stk1[t1];
      wfc=x[i]-x[stk1[t1--]];add();
    }stk0[++t0]=i;stk1[++t1]=i;
    ans+=a[1].c; 
  }printf("%lld",ans);
  return 0;
}

回到本题。

在上一题算法的基础上,若询问 : 某个区间有多少个后缀是好的。直接求后缀和即可。

如果把每个版本的贡献位置列成一个二维表,则是一个三角形。

其中,蓝色线覆盖的部分为某次后缀和,而红色部分为某次询问的答案。

这其实就对应历史版本和。

注意更新标记只能传给最小值相等的儿子。

#include<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define MaxN 120500
using namespace std;
int read(){
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
struct Node{
  int x,c,tg,u;ll m;
  inline void add(int _t)
  {x+=_t;tg+=_t;}
  inline void adu(int _u)
  {u+=_u;m+=1ll*_u*c;}
}a[MaxN<<2];
inline void up(int u){
  int l=u<<1,r=u<<1|1;
  a[u].x=min(a[l].x,a[r].x);
  a[u].c=((a[l].x==a[u].x) ? a[l].c : 0)
        +((a[r].x==a[u].x) ? a[r].c : 0);
}
int n;
void build(int l=1,int r=n,int u=1)
{
  if (l==r){a[u].x=l;a[u].c=1;return ;}
  int mid=(l+r)>>1;
  build(l,mid,u<<1);
  build(mid+1,r,u<<1|1);
  up(u);
}
inline void ladd(int u)
{
  if (a[u].tg){
    a[u<<1].add(a[u].tg);
    a[u<<1|1].add(a[u].tg);
    a[u].tg=0;
  }
  if (a[u].u){
    if (a[u<<1].x==a[u].x)
      a[u<<1].adu(a[u].u);
    if (a[u<<1|1].x==a[u].x)
      a[u<<1|1].adu(a[u].u);
    a[u].u=0;
  }
}
int wfl,wfr,wfc;
void add(int l=1,int r=n,int u=1)
{
  if (wfl<=l&&r<=wfr)
    {a[u].add(wfc);return ;}
  int mid=(l+r)>>1;ladd(u);
  if (wfl<=mid)add(l,mid,u<<1);
  if (mid<wfr)add(mid+1,r,u<<1|1);
  up(u);
}
ll qry(int l=1,int r=n,int u=1)
{
  if (wfl<=l&&r<=wfr)return a[u].m;
  int mid=(l+r)>>1;ll ret=0;ladd(u);
  if (wfl<=mid)ret=qry(l,mid,u<<1);
  if (mid<wfr)ret+=qry(mid+1,r,u<<1|1);
  return ret;
}
int x[MaxN],stk0[MaxN],t0,stk1[MaxN],t1;
struct Data{int l,r,p;};
vector<Data> b[MaxN];
int q;ll ans[MaxN];
int main()
{
  n=read();
  for (int i=1,t;i<=n;i++)x[i]=read();
  q=read();
  for (int i=1;i<=q;i++){
    wfl=read();wfr=read();
    b[wfr].push_back((Data){wfl,wfr,i});
  }build();
  for (int i=1;i<=n;i++){
    while(t0&&x[stk0[t0]]>x[i]){
      wfl=stk0[t0-1]+1;wfr=stk0[t0];
      wfc=x[stk0[t0--]]-x[i];add();
    }while(t1&&x[stk1[t1]]<x[i]){
      wfl=stk1[t1-1]+1;wfr=stk1[t1];
      wfc=x[i]-x[stk1[t1--]];add();
    }a[1].adu(1);
    for (int j=0;j<b[i].size();j++){
      wfl=b[i][j].l;wfr=b[i][j].r;
      ans[b[i][j].p]=qry();
    }stk0[++t0]=i;stk1[++t1]=i;
  }
  for (int i=1;i<=q;i++)
    printf("%lld\n",ans[i]);
  return 0;
}