[DS记录]P6578 [Ynoi2019]魔法少女网站

· · 个人记录

题意 : 第十分块。

给出一个序列，资瓷:

允许离线，n,m\leq 3\times10^5 ，时限\texttt{5s} ，空限\texttt{60M}。

若考虑分块，由于是 \rm pair 贡献，难以够对每个整块分别计算，那么就无法使用离线逐块处理的办法降空间。

离线而空间小的做法，不妨思考一下莫队。

我们有四个维度 : 操作时间 ， l，r ， 以及 \max。

本题的数据范围较大，根据经验，最简单的带修莫队也极限只能在 \texttt{1s} 内处理 10^5 。本题更为复杂，常数进一步增大， \texttt{3s} 跑 3\times10^5 估计没戏。

想要做到 O(n\sqrt{n}) 的复杂度，我们只能使用莫队维护两个维度，剩下的就交给其他数据结构。

时间这一维处理起来最困难，是必然要维护的 (否则也就可能可以在线了?) 。而左右端点维护难度应是相同的，要么都维护，要么都不维护。

这样看来，我们最好尝试在莫队中维护 (时间,\max) 两维，而将 l,r 交给支持区间查询的数据结构。

维护一个 01 序列，表示某个位置是否 \leq \max，答案就是区间内极长 1 区间的 \binom{len}{2} 的和。

考虑如何实现一个 O(1) 修改 O(\sqrt{n}) 查询的数据结构。

我们发现 0\rightarrow 1 较为容易， 1\rightarrow 0 相当困难，于是不考虑后者。

使用分块，对每块记录块内权值和，极长 1 前/后缀长度。

查询时，对边界散块暴力算出上述信息，然后将各个块合并，复杂度为 O(\sqrt{n})。

修改时，对每个块分别维护。对于每个段,在其两端维护段的另一端（类似双向链表），这样就能支持 O(1) 将段合并。

然后还需特判是否扩展了 前/后缀。

由于我们不支持 1\rightarrow 0 ，需要使用回滚莫队。

让时间维乱跳，\max 维块内单调。当 \max 指针增加时，只会在序列中把一些位置 0\rightarrow 1 。

将可能被回滚影响到的 O(\sqrt{n}) 个位置打上标记，在 \max 指针移动时不处理，回滚时才处理。

时间维回滚时会撤回操作，用栈记录撤回信息即可。

综上，时间复杂度为 O(n\sqrt{n}) ，空间复杂度为 O(n)。

#include<algorithm>
#include<cstdio>
#include<cmath>
#define ll long long
#define MaxN 300500
using namespace std;
namespace io {} using namespace io;
const int BS=10,rBS=1024;
struct BData{int len,l,r;ll s;}blo[1050];
inline ll C2(int n){return 1ll*(n+1)*n>>1;}
inline BData operator + (const BData &L,const BData &R){
  return (BData){
    L.len+R.len,
    L.l==L.len ? R.l+L.len : L.l,
    R.r==R.len ? L.r+R.len : R.r,
    L.s+R.s-C2(L.r)-C2(R.l)+C2(L.r+R.l)
  };
}
int tl[MaxN],tr[MaxN];
void clear(int n){
  for (int i=1;i<=n;i++)tl[i]=tr[i]=0;
  for (int k=0;k*rBS<=n;k++)blo[k].l=blo[k].r=blo[k].s=0;
}
inline void add(int p){
  if (tl[p])return ;
  tl[p]=tr[p]=p;
  int tb=p>>BS,bl=tb<<BS,br=bl+rBS,l,r;
  if (bl<=p-1&&tl[p-1])tr[tl[p]=tl[p-1]]=p;
  l=tl[p];
  if (p+1<br&&tl[p+1])tl[tr[l]=tr[p+1]]=l;
  r=tr[l];
  blo[tb].s+=C2(r-l+1)-C2(p-l)-C2(r-p);
  if (l==bl)blo[tb].l=r-l+1;
  if (r==br-1)blo[tb].r=r-l+1;
}
int stk[2050],top;
void add2(int p){stk[++top]=p;add(p);}
inline void undo(int p)
{
  int tb=p>>BS,bl=tb<<BS,br=bl+rBS,l,r;
  tl[p]=tr[p]=0;
  if (bl<=p-1&&tl[p-1])tr[l=tl[p-1]]=p-1;
  else l=p;
  if (p+1<br&&tl[p+1])tl[r=tr[p+1]]=p+1;
  else r=p;
  blo[tb].s-=C2(r-l+1)-C2(p-l)-C2(r-p);
  if (l==bl)blo[tb].l=p-l;
  if (r==br-1)blo[tb].r=r-p;
}
BData get(int l,int r)
{
  BData R;R.len=r-l+1;
  R.l=0;for (int i=l;i<=r&&tl[i];i++)R.l++;
  R.r=0;for (int i=r;i>=l&&tl[i];i--)R.r++;
  int len=0;R.s=0;
  for (int i=l;i<=r;i++)
    if (tl[i])len++;
    else {R.s+=C2(len);len=0;}
  R.s+=C2(len);
  return R;
}
ll qry(int l,int r)
{
  if (l/rBS==r/rBS)return get(l,r).s;
  BData R=get(l,l/rBS*rBS+rBS-1);
  for (int i=l/rBS+1;i<r/rBS;i++)R=R+blo[i];
  R=R+get(r/rBS*rBS,r);
  return R.s;
}
struct QData{int l,r,lim,t,p;}b[MaxN];
int BS2;
bool cmp(const QData &A,const QData &B)
{return A.t/BS2==B.t/BS2 ? A.lim<B.lim : A.t<B.t;}
struct CData{int p,x;}t[MaxN];
int a[MaxN],sa[MaxN],sp[MaxN],p[MaxN<<1],n,m,q,tim;
ll ans[MaxN];
int main()
{
  n=rd();m=rd();
  for (int i=1;i<=n;i++)sp[a[i]=rd()]++;
  for (int i=1,op;i<=m;i++){
    if (rd()==1){
      t[++tim].p=rd();
      sp[t[tim].x=rd()]++;
    }else {
      b[++q].l=rd();b[q].r=rd();b[q].lim=rd();
      b[q].t=tim;b[q].p=q;
    }
  }
  for (int i=1;i<=n;i++)sp[i]+=sp[i-1];
  for (int i=1;i<=n;i++)p[++sp[a[i]-1]]=i;
  for (int i=1;i<=tim;i++)p[++sp[t[i].x-1]]=t[i].p;
  for (int i=n;i;i--)sp[i]=sp[i-1];sp[0]=0;
  BS2=min(1.8*tim/sqrt(q)+1,2000.0);
  for (int k=0;k*rBS<=n;k++)blo[k].len=rBS;
  sort(b+1,b+q+1,cmp);
  int st[2050];
  for (int qi=1,k=0,x,tn=0;qi<=q;qi++){
    if (qi==1||b[qi].t/BS2!=b[qi-1].t/BS2){
      int las=k;k=b[qi].t/BS2*BS2;
      for (int i=las+1;i<=k;i++)a[t[i].p]=t[i].x;
      x=tn=0;
      for (int i=k+1;i<=min(k+BS2-1,tim);i++)st[++tn]=t[i].p;
      sort(st+1,st+tn+1);tn=unique(st+1,st+tn+1)-st-1;
      for (int i=1;i<=tn;i++){sa[st[i]]=a[st[i]];a[st[i]]=n+1;}
      clear(n);
    }
    if (x<b[qi].lim){
      for (int i=sp[x]+1;i<=sp[b[qi].lim];i++)
        if (x<a[p[i]]&&a[p[i]]<=b[qi].lim)add(p[i]);
      x=b[qi].lim;
    }
    for (int i=1;i<=tn;i++)a[st[i]]=sa[st[i]];
    for (int i=k+1;i<=b[qi].t;i++)a[t[i].p]=t[i].x;
    for (int i=1;i<=tn;i++){
      if (a[st[i]]<=b[qi].lim)add2(st[i]);
      a[st[i]]=n+1;
    }ans[b[qi].p]=qry(b[qi].l,b[qi].r);
    while(top)undo(stk[top--]);
  }
  for (int i=1;i<=q;i++)print(ans[i]),putc('\n');
  flush();
  return 0;
}

考虑分块。

询问时将 \leq lim 的位置记为 1 ，其余记为 0。

散块暴力。对于整块只需要得到左侧连续 1，右侧连续 1，块中答案。

注意到对于每个块只产生 O(\sqrt{n}) 个本质不同的 01 序列，且 lim 的分界点正是块中元素。

利用插入排序，重构一个块容易做到 O(\sqrt{n})。

查询时需要二分。用分散层叠可以优化到 O(n\sqrt{n})。