线段树 学习笔记

· · 个人记录

概述

线段树（Segment Tree）是一种常用的维护区间信息的数据结构。线段树的结构是如下的分治结构：

线段树是完全二叉树，每一个节点表示一个区间，将每个长度不为 1 的区间均分成左右两个区间。对于节点 i，左右儿子的编号分别为 2i,2i+1。

下面以 P3372 为例。

定义

每个节点维护两个值：v,tag 分别是维护的值和懒惰标记。其中 tag 在区间修改时会用到。

注意线段树的数组要开到原数组的四倍大小。

建树

递归建树。如果递归到叶节点就赋值，否则分治并递归，在回溯时用已经赋值的子节点更新父节点的值。

void pushup(int pos){
  tr[pos].v=tr[pos<<1].v+tr[pos<<1|1].v;
}
void build(int pos,int nl,int nr,T a[]){
  tr[pos].tag=0;
  if(nl==nr)tr[pos].v=a[nl];
  else{
    int mid=(nl+nr)>>1;
    build(pos<<1,nl,mid,a),build(pos<<1|1,mid+1,nr,a),pushup(pos);
  }
}

单点修改，区间查询

单点修改时找到叶节点更新，在回溯时 pushup。

void add(int pos,int nl,int nr,int g,T k){
  if(nl==nr){
    tr[pos].v+=k;
    return;
  }
  int mid=(nl+nr)>>1;
  if(g<=mid)add(pos<<1,nl,mid,g,k);
  if(g>mid)add(pos<<1|1,mid+1,nr,g,k);
  pushup(pos);
}

区间查询时，如果整个区间被包含在目标区间内，那么返回这个区间的值。否则需要继续往下细分。

T query(int pos,int nl,int nr,int gl,int gr){
  if(gl<=nl&&nr<=gr)return tr[pos].v;
  int mid=(nl+nr)>>1;
  T ans=0;
  if(gl<=mid)ans+=query(pos<<1,nl,mid,gl,gr);
  if(gr>mid)ans+=query(pos<<1|1,mid+1,nr,gl,gr);
  return ans;
}

区间修改，区间查询

懒惰标记

区间查询时目标区间包含当前区间可以直接返回，但是如果暴力区间修改，当前区间被包含时还要修改子树。这样如果查询 [1,n] 就要把整棵树都遍历，显然要炸。

这时对这个区间打懒惰标记表示对一颗子树的修改，因为不需要用到子树的信息，所以不用修改子节点真正的值。

当需要用到子树的信息时，将标记下传给两个子节点并更新实际值，自身的标记清空，用一个函数 pushdown 表示。

void pushdown(int pos,int nl,int nr){
  int mid=(nl+nr)>>1;
  tr[pos<<1].tag+=tr[pos].tag,tr[pos<<1|1].tag+=tr[pos].tag;
  tr[pos<<1].v+=(mid-nl+1)*tr[pos].tag,tr[pos<<1|1].v+=(nr-mid)*tr[pos].tag;
  tr[pos].tag=0;
}

区间操作

区间修改：目标区间包含当前区间时，修改当前节点并打标记，直接返回。否则要往下细分并下传标记。回溯时由于不知道当前节点需要修改多少，要 pushup。

void add(int pos,int nl,int nr,int gl,int gr,T k){
  if(gl<=nl&&nr<=gr){
    tr[pos].tag+=k;
    tr[pos].v+=(tr[pos].r-tr[pos].l+1)*k;
    return;
  }
  pushdown(pos,nl,nr);
  int mid=(nl+nr)>>1;
  if(gl<=mid)add(pos<<1,nl,mid,gl,gr,k);
  if(gr>mid)add(pos<<1|1,mid+1,nr,gl,gr,k);
  pushup(pos);
}

区间查询：

类似单点修改的情况，多一个下传标记。

T query(int pos,int nl,int nr,int gl,int gr){
  if(gl<=nl&&nr<=gr)return tr[pos].v;
  pushdown(pos,nl,nr);
  int mid=(nl+nr)>>1;
  T ans=0;
  if(gl<=mid)ans+=query(pos<<1,nl,mid,gl,gr);
  if(gr>mid)ans+=query(pos<<1|1,mid+1,nr,gl,gr);
  return ans;
}

小技巧

两倍空间

上面说线段树需要开四倍空间。但是显然线段树的节点最多有 2n-1 个，下面介绍一种开两倍空间的方法：令区间 [l,r] 的编号为 (l+r)\operatorname{or}[l\ne r]。

叶节点的标号为偶数，其他为奇数。一个区间 [l,r] 的标号为 2mid+1，左儿子的标号范围为 [2l,2mid]，右儿子的标号范围为 [2mid+2,2r]。因此不会重复。最大标号为 [n,n] 的标号 2n。

标记永久化

标记永久化是懒惰标记之外维护区间修改的方式，不下传标记或用儿子的信息更新自身。

如果不下传标记，那么标记会影响整一棵子树。

区间修改：对于完全包含的打标记，对于不完全包含的，直接算出这个节点的区间与修改区间的交集计算影响而非 pushup。

区间查询：对于标记，由于标记不下传，每个经过的节点都要算标记与查询区间的交集的贡献。

void add(int pos,int nl,int nr,int gl,int gr,T k){
  if(gl<=nl&&nr<=gr){
    tr[pos].tag+=k;
    return;
  }
  tr[pos].v+=k*(min(nr,gr)-max(nl,gl)+1);
  int mid=(nl+nr)>>1;
  if(gl<=mid)add(pos<<1,nl,mid,gl,gr,k);
  if(gr>mid)add(pos<<1|1,mid+1,nr,gl,gr,k);
}
T query(int pos,int nl,int nr,int gl,int gr){
  if(gl<=nl&&nr<=gr)return tr[pos].v+tr[pos].tag*(nr-nl+1);
  int mid=(nl+nr)>>1;
  T ans=tr[pos].tag*(min(nr,gr)-max(nl,gl)+1);
  if(gl<=mid)ans+=query(pos<<1,nl,mid,gl,gr);
  if(gr>mid)ans+=query(pos<<1|1,mid+1,nr,gl,gr);
  return ans;
}

动态开点

当 n 很大，达到不能直接开数组的级别，可以动态开点 节约空间，当一个节点用到的时候才分配编号。

单点修改时需要多加一行 if(!pos)pos=++cnt;查询时如果节点没有建出就返回 0。如果区间修改就要在 pushdown 时也给子节点分配编号。

每个节点记录左儿子和右儿子的编号，pos 需要改为引用，这样对新建节点时，也给父节点的 ls,rs 赋值了。

一次修改最多经过 \log n 个点，一共 m 次修改，那么只需要开 O(m\log n) 的空间。

当需要开多棵线段树时，可以把线段树开在同一个数组里。

权值线段树

用线段树维护一个桶，这样的线段树叫权值线段树。

权值线段树可能出现值域过大的情况，因此可以使用动态开点。可以发现这样也自带离散化。

权值线段树也能处理负数。此时 mid 应取 \frac{l+r-1}{2}。

线段树合并

合并两棵线段树，如果有一棵树的节点没有建出就返回另一棵树上的节点，叶节点合并信息，非叶结点递归合并左右子树。最后一路 pushup。

int merge(int a,int b,int nl,int nr){
  if(!a||!b)return a^b;
  if(nl==nr)return tr[a].v+=tr[b].v,a;
  int mid(nl+nr)>>1;
  tr[a].ls=merge(tr[a].ls,tr[b].ls,nl,mid),tr[a].rs=merge(tr[a].rs,tr[b].rs,mid+1,nr),pushup(a);
  return pushup(a),a;
}

线段树合并的复杂度是均摊的。从过程可以看成，线段树合并的复杂度约等于两棵树的公共节点数，而公共节点在合并后会被删除一个。因此线段树合并的均摊复杂度约等于总共创建的节点数。也可以进行可持久化线段树合并，复杂度相同。

在一些题目中，若区间信息可以快速合并，就可以直接合并信息，无需 pushup。这种写法不用判断叶节点。如果题目保证了叶节点不会重合，也不用判断叶节点。

P3224

板子题。用并查集维护连通块，每个连通块开一棵权值线段树。连边操作为线段树合并，第 k 小在这个连通块的线段树上二分。此题线段树合并不会有两个相同的叶子，不需要判断在叶子处合并信息。

#include<bits/stdc++.h>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T&a){
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename ...Args>void in(T&a,Args&...args){
  in(a),in(args...);
}
int n,m,q,p[100005],rt[100005],f[100005];
struct node{
  int v,ls,rs;
};
template<int maxn>struct SMT{
  node tr[maxn];
  int cnt;
  void pushup(int pos){
    tr[pos].v=tr[tr[pos].ls].v+tr[tr[pos].rs].v;
  }
  void add(int&pos,int nl,int nr,int g,int k){
    if(!pos)pos=++cnt;
    tr[pos].v+=k;
    if(nl==nr)return;
    int mid=(nl+nr)>>1;
    if(g<=mid)add(tr[pos].ls,nl,mid,g,k);
    if(g>mid)add(tr[pos].rs,mid+1,nr,g,k);
  }
  int query(int pos,int nl,int nr,int k){
    if(tr[pos].v<k||!pos)return 0;
    if(nl==nr)return nl;
    int mid=(nl+nr)>>1;
    if(tr[tr[pos].ls].v>=k)return query(tr[pos].ls,nl,mid,k);
    else return query(tr[pos].rs,mid+1,nr,k-tr[tr[pos].ls].v);
  }
  int merge(int a,int b){
    if(!a||!b)return a^b;
    tr[a].ls=merge(tr[a].ls,tr[b].ls),tr[a].rs=merge(tr[a].rs,tr[b].rs);
    return pushup(a),a;
  }
};
SMT<2000005>t;
int find(int x){
  return f[x]?f[x]=find(f[x]):x;
}
int main(){
  p[0]=-1,in(n,m);
  for(int i=1,x;i<=n;i++)in(x),p[x]=i,t.add(rt[i],1,n,x,1);
  for(int i=1,x,y;i<=m;i++){
    in(x,y),x=find(x),y=find(y);
    if(x!=y)rt[x]=t.merge(rt[x],rt[y]),f[y]=x;
  }
  in(q);
  for(int i=1,x,y;i<=q;i++){
    char opt=getc();
    while(opt<'A'||opt>'Z')opt=getc();
    in(x,y);
    if(opt=='B'){
      x=find(x),y=find(y);
      if(x!=y)rt[x]=t.merge(rt[x],rt[y]),f[y]=x;
    }
    else cout<<p[t.query(rt[find(x)],1,n,y)]<<'\n';
  }
  return 0;
}

线段树分裂

线段树可以将树分成值域不交的两部分。类似 FHQ treap，有按值分裂和按排名分裂两种。

对于按值分裂，以将树 A 值在 [l,r] 内的部分分裂给树 B 为例。找出 A 树上代表区间 [l,r] 的节点，中间与 [l,r] 相交但不被包含的节点需要开一个新节点给 B。当前节点被 [l,r] 包含时，将这个节点给 B，返回。

void split(int&a,int&b,int nl,int nr,int gl,int gr){
  if(!a)return;
  if(gl<=nl&&nr<=gr){
    b=a,a=0;
    return;
  }
  b=++cnt;
  int mid=(nl+nr)>>1;
  if(gl<=mid)split(tr[a].ls,tr[b].ls,nl,mid,gl,gr);
  if(gr>mid)split(tr[a].rs,tr[b].rs,mid+1,nr,gl,gr);
  pushup(a),pushup(b);
}

对于按排名分裂，假设将 A 的前 k 大给 B。在线段树上找第 k 大的同时分裂。对于路径上的节点，给 B 开一个新节点。维护子树内有值的个数，若第 k 大在右子树，则递归，否则将右子树给 B，如果分界点不恰好在两棵子树中间就递归。最后分裂节点的信息。

void split(int&a,int&b,int k){
  b=++cnt;
  if(k>tr[tr[a].ls].v)split(tr[a].rs,tr[b].rs,k-tr[tr[a].ls].v);
  else tr[b].rs=tr[a].rs,tr[a].rs=0;
  if(k<tr[tr[a].ls].v)split(tr[a].ls,tr[b].ls,k);
  tr[b].v=tr[a].v-k,tr[a].v=k;
}

分析复杂度，和区间操作一样，新建节点数和复杂度都是单次 O(\log n)。线段树分裂与合并搭配，因为合并的复杂度只依赖总节点数，只要分裂的次数正确复杂度就正确。

P2824

考虑直接维护。任意时刻，序列可以分为若干个上升段和下降段。对于每个段开一个权值线段树维护段内存在的数，外面用 set 维护所有连续段。区间赋值时需要支持将序列的前若干大/小分裂与线段树合并。

其中 set 维护连续段有颜色段均摊，所以合并分裂都是 O(n) 次，总复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
int n,m,q,p[100005],rt[100005];
struct node1{
  int ls,rs,v;
};
template<int maxn>struct SMT{
  node1 tr[maxn];
  int cnt;
  void add(int &pos,int nl,int nr,int g){
    if(!pos)pos=++cnt;
    tr[pos].v++;
    if(nl==nr)return;
    int mid=(nl+nr)>>1;
    if(g<=mid)add(tr[pos].ls,nl,mid,g);
    else add(tr[pos].rs,mid+1,nr,g);
  }
  int query(int pos,int nl,int nr){
    if(nl==nr)return nl;
    int mid=(nl+nr)>>1;
    if(tr[pos].ls)return query(tr[pos].ls,nl,mid);
    else return query(tr[pos].rs,mid+1,nr);
  }
  int merge(int a,int b){
    if(!a||!b)return a^b;
    tr[a].v+=tr[b].v,tr[a].ls=merge(tr[a].ls,tr[b].ls),tr[a].rs=merge(tr[a].rs,tr[b].rs);
    return a;
  }
  void split0(int&a,int&b,int k){
    b=++cnt;
    if(k>tr[tr[a].ls].v)split0(tr[a].rs,tr[b].rs,k-tr[tr[a].ls].v);
    else tr[b].rs=tr[a].rs,tr[a].rs=0;
    if(k<tr[tr[a].ls].v)split0(tr[a].ls,tr[b].ls,k);
    tr[b].v=tr[a].v-k,tr[a].v=k;
  }
  void split1(int&a,int&b,int k){
    b=++cnt;
    if(k>tr[tr[a].rs].v)split1(tr[a].ls,tr[b].ls,k-tr[tr[a].rs].v);
    else tr[b].ls=tr[a].ls,tr[a].ls=0;
    if(k<tr[tr[a].rs].v)split1(tr[a].rs,tr[b].rs,k);
    tr[b].v=tr[a].v-k,tr[a].v=k;
  } 
};
SMT<5000005>t1;
struct node{
  int l,r;
  mutable bool v;
  bool operator<(node a)const{
    return l<a.l;
  }
};
struct chtholly_tree{
  set<node>tr;
  set<node>::iterator split(int pos){
    set<node>::iterator it=tr.lower_bound((node){pos,0,0});
    if(it!=tr.end()&&(*it).l==pos)return it;
    if((*--it).r<pos)return tr.end();
    int l=(*it).l,r=(*it).r;
    bool v=(*it).v;
    if(v)t1.split1(rt[l],rt[pos],pos-l);
    else t1.split0(rt[l],rt[pos],pos-l);
    return tr.erase(it),tr.insert((node){l,pos-1,v}),tr.insert((node){pos,r,v}).first;
  }
  void assign(int l,int r,bool k){
    set<node>::iterator itr=split(r+1),itl=split(l),it=itl;
    for(it++;it!=itr;it++)t1.merge(rt[l],rt[(*it).l]);
    tr.erase(itl,itr),tr.insert((node){l,r,k});
  }
};
chtholly_tree t;
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>p[i],t1.add(rt[i],1,n,p[i]),t.tr.insert((node){i,i,0});
  for(int i=1,opt,l,r;i<=m;i++)cin>>opt>>l>>r,t.assign(l,r,opt);
  return cin>>q,t.split(q+1),t.split(q),cout<<t1.query(rt[q],1,n)<<'\n',0;
}

zkw 线段树

定义

zkw 线段树是一种非递归的线段树，相比于递归线段树具有小常数，好码，空间小等优点，缺点是适用范围更小。

建树

zkw线段树需要先将数组长度填充成 2 的整数幂。这时这棵树为一颗满二叉树，具有很多性质。

建树时，可以利用满二叉树的性质，先对叶节点赋值，然后自底向上建树。

diff=2<<__lg(n+1);
for(int i=1;i<=n;i++)v[diff+i]=a[i];
for(int i=diff-1;i>=1;i--)v[i]=v[i<<1]+v[i<<1|1];

为了方便查询，建树时需要在叶节点的左右留下一个空位，原数组对应的叶节点为第 2\sim n+1 个叶节点。

单点修改，区间查询

单点修改时，直接从叶节点开始向根节点跳，修改沿途的节点。

for(x+=diff;x;x>>=1)tr[x]+=k;

区间查询时，需要维护两个指针 l,r。一开始这两个指针分别指向 [l-1,l-1],[r+1,r+1]，剩下要查询的区间在 l,r 中间。比如下图中 l,r 分别指向 [2,2],[7,7]，表示剩下的区间为 (2,7)。

然后让 l,r 不断向上跳。对于 l，如果指向的是左儿子，那么其兄弟在当前区间内，需要统计答案。同理，如果 r 指向右儿子则统计兄弟节点的答案。当 l,r 为兄弟节点，说明剩下的区间为空，结束循环。

比如此时 l,r 分别指向 [1,2],[7,8]，那么 兄弟节点 [3,4],[7,8] 在查询区间内，加入答案。然后 l,r 跳到 [1,4],[5,8]，查询结束。

for(l+=diff-1,r+=diff+1;l^r^1;l>>=1,r>>=1){
  if(~l&1)ans+=tr[l^1];
  if(r&1)ans+=tr[r^1];
}
return ans;

区间修改，区间查询

zkw 线段树自底向上遍历，显然不能标记下传，需要使用标记永久化。

修改时遍历方法同上，对于 l,r 指向的节点修改值，兄弟节点整体修改值并打标记，表示子树需要修改。并且当这一个循环结束时，l,r 更上方的节点也需要修改，所以要继续跳到根节点。要开三个变量 cntl,cntr,len 表示 l,r 与修改区间重合的长度和当前层区间的长度。

void add(int l,int r,T k,int cntl=0,int cntr=0,int len=1){
  for(l+=diff-1,r+=diff+1;l^r^1;l>>=1,r>>=1,len<<=1){
    v[l]+=cntl*k,v[r]+=cntr*k;
    if(~l&1)v[l^1]+=len*k,tag[l^1]+=k,cntl+=len;
    if(r&1)v[r^1]+=len*k,tag[r^1]+=k,cntr+=len;
  }
  for(;l;l>>=1,r>>=1)v[l]+=cntl*k,v[r]+=cntr*k;
}

区间查询类似，需要开一个变量统计子树打标记的区间长度。由于标记不下传，有些标记可能打在更上方，需要一直跳到根节点。

T query(int l,int r,T ans=0,int cntl=0,int cntr=0,int len=1){
  for(l+=diff-1,r+=diff+1;l^r^1;l>>=1,r>>=1,len<<=1){
    ans+=cntl*tag[l]+cntr*tag[r];
    if(~l&1)ans+=v[l^1],cntl+=len; 
    if(r&1)ans+=v[r^1],cntr+=len; 
  }
  for(;l;l>>=1,r>>=1)ans+=cntl*tag[l]+cntr*tag[r];
  return ans;
}

李超线段树

一种数据结构，可以动态维护平面直角坐标系上的一些线段。

P4254

板子题。有两个操作：动态插入直线，询问与直线 x=x_0 相交的已插入线段中交点 y 的最值。

这一题全是直线，可以看做左右端点取到边界的线段，相当于全局修改。每条线段转成斜截式，线段树的每个节点记录与 x=mid 的交点 y 最大的线段。

采用标记永久化，直接修改经过的每条线段。设原来的线段的斜率和截距为 k_0,b_0，新的线段为 k_1,b_1。分类讨论：

  1. 原来的线段整体在新的线段的上方，新的线段不可能更新，直接返回；

  2. 原来的线段整体在新的线段的下方，直接更新后返回；

  3. 两条线段相交，更新并用淘汰的线段递归进交点所在的儿子。

查询时递归到节点 y，由于是标记永久化要一路取 \max。

template<int maxn>struct SMT{
  int tr[maxn],cnt;
  double k[maxn],b[maxn];
  bool check(int u,int v,int x){
    return k[u]*x+b[u]>k[v]*x+b[v];
  } 
  void add(int pos,int nl,int nr,int g){
    int mid=(nl+nr)>>1;
    if(check(g,tr[pos],mid))swap(g,tr[pos]);
    if(check(g,tr[pos],nl))add(pos<<1,nl,mid,g);
    if(check(g,tr[pos],nr))add(pos<<1|1,mid+1,nr,g);
  }
  void insert(int pos,int nl,int nr,double k1,double b1){
    k[++cnt]=k1,b[cnt]=b1,add(pos,nl,nr,cnt);
  }
  double query(int pos,int nl,int nr,int g){
    if(nl==nr)return k[tr[pos]]*g+b[tr[pos]];
    int mid=(nl+nr)>>1;
    double ans=k[tr[pos]]*g+b[tr[pos]];
    if(g<=mid)ans=max(ans,query(pos<<1,nl,mid,g));
    if(g>mid)ans=max(ans,query(pos<<1|1,mid+1,nr,g));
    return ans;
  }  
};

P4097

这一题是线段，所以是区间修改。先在线段树上拆分区间，然后按照全局修改的办法递归。复杂度 O(n\log^2n)。

template<int maxn>struct SMT{
  int tr[maxn],cnt;
  double k[maxn],b[maxn];
  bool check(int u,int v,int x){
    return fabs(k[u]*x+b[u]-k[v]*x-b[v])<1e-6?u<v:k[u]*x+b[u]>k[v]*x+b[v];
  }
  void add(int pos,int nl,int nr,int gl,int gr,int g){
    int mid=(nl+nr)>>1;
    if(gl<=nl&&nr<=gr){
      if(check(g,tr[pos],mid))swap(g,tr[pos]);
      if(check(g,tr[pos],nl))add(pos<<1,nl,mid,gl,gr,g);
      if(check(g,tr[pos],nr))add(pos<<1|1,mid+1,nr,gl,gr,g);
      return;  
    }
    if(gl<=mid)add(pos<<1,nl,mid,gl,gr,g);
    if(gr>mid)add(pos<<1|1,mid+1,nr,gl,gr,g);
  }
  void insert(int pos,int nl,int nr,double k1,double b1){
    k[++cnt]=k1,b[cnt]=b1,add(pos,1,39989,nl,nr,cnt);
  }
  double query(int pos,int nl,int nr,int g){
    if(nl==nr)return tr[pos];
    int mid=(nl+nr)>>1,ans;
    if(g<=mid)ans=query(pos<<1,nl,mid,g);
    else ans=query(pos<<1|1,mid+1,nr,g);
    if(check(tr[pos],ans,g))return tr[pos];
    else return ans;
  }  
};

查询和全局修改是 O(\log n) 的。不过区间修改 O(\log^2 n)。

李超线段树是线段树的一种，所以上面线段树的操作也可应用于李超线段树。

可持久化线段树

可持久化数据结构进行操作时，还可以保存所有历史版本。

如果直接对每一个版本都建一棵树，显然时间和空间都寄。但是根据线段树的特性，每次只有 O(\log n) 级别的节点会被修改，剩下的节点可以共用剩余的点。

以 P3919 为例：

首先需要建出一棵基础树。

void build(int&pos,int nl,int nr,T a[]){
  pos=++cnt;
  if(nl==nr)tr[pos].v=a[nl];
  else{
    int mid=(nl+nr)>>1;
    build(tr[pos].ls,nl,mid,a),build(tr[pos].rs,mid+1,nr,a);
  }
}

修改时，同时在两个版本的树上递归并复制路径。

void add(int&pos,int v,int nl,int nr,int g,T k){
  tr[pos=++cnt]=tr[v];
  if(nl==nr){
    tr[pos].v=k;
    return;
  }
  int mid=(nl+nr)>>1;
  if(g<=mid)add(tr[pos].ls,tr[v].ls,nl,mid,g,k);
  else add(tr[pos].rs,tr[v].rs,mid+1,nr,g,k);
}

查询与普通线段树一样，这道题还需要将当前版本的根指向查询的版本。

P3834

如果询问全局 kth，可以用权值线段树。

对于区间问题，可以维护桶的前缀和，即对于序列的每个前缀都建一棵权值线段树，差分就可以得到一个区间的权值线段树。这需要用到可持久化线段树。

#include<bits/stdc++.h>
using namespace std;
template<typename T>struct node{
  T v;
  int ls,rs;
};
template<typename T,int maxn>struct SMT{
  node<T>tr[maxn];
  int cnt;
  void pushup(int pos){
    tr[pos].v=tr[tr[pos].ls].v+tr[tr[pos].rs].v;
  }
  void add(int&pos,int v,int nl,int nr,int g,T k){
    tr[pos=++cnt]=tr[v];
    if(nl==nr){
      tr[pos].v+=k;
      return;
    }
    int mid=(nl+nr)>>1;
    if(g<=mid)add(tr[pos].ls,tr[v].ls,nl,mid,g,k);
    else add(tr[pos].rs,tr[v].rs,mid+1,nr,g,k);
    pushup(pos);
  }
  T query(int pl,int pr,int nl,int nr,int k){
    if(nl==nr)return nl;
    int mid=(nl+nr)>>1;
    if(tr[tr[pr].ls].v-tr[tr[pl].ls].v>=k)return query(tr[pl].ls,tr[pr].ls,nl,mid,k);
    else return query(tr[pl].rs,tr[pr].rs,mid+1,nr,k-(tr[tr[pr].ls].v-tr[tr[pl].ls].v));
  }
};
SMT<int,6000005>t;
int n,m,rt[200005],a[200005],p[200005];
void rebuild(int n,int a[],int cnt=0){
  int temp[n+5];
  for(int i=1;i<=n;i++)temp[i]=a[i];
  sort(temp+1,temp+n+1),cnt=unique(temp+1,temp+n+1)-temp-1;
  for(int i=1,t;i<=n;i++)t=lower_bound(temp+1,temp+cnt+1,a[i])-temp,p[t]=a[i],a[i]=t;
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i];
  rebuild(n,a);
  for(int i=1;i<=n;i++)t.add(rt[i],rt[i-1],1,n,a[i],1);
  for(int i=1,l,r,k;i<=m;i++)cin>>l>>r>>k,cout<<p[t.query(rt[l-1],rt[r],1,n,k)]<<'\n';
  return 0;
}

线段树优化建图

CF786B

这题里有对一个区间连边的操作，直接连是 O(n) 的。考虑将这些区间拆成比较少的区间，发现线段树满足这个要求。

如图，建出两棵线段树，一棵由父亲向儿子连边，一棵由儿子向父亲连边，边权为零。线段树的子节点向原图的节点连双向边，边权为零。

当点向区间连边时，就把区间在第一棵线段树拆分出若干个区间，点向这些区间代表的点。这样点就可以先走到这些区间，再向下走到原图的节点。同理，区间向点连边，就在第二个线段树上拆分连向点。

边数 O(m\log n)，复杂度 O(m\log^2n)。

#include<bits/stdc++.h>
using namespace std;
int n,m,s,cnt;
long long w,dis[900005];
bool vis[900005];
vector<pair<int,long long>>e[900005];
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
void build(int pos,int nl,int nr){
  if(nl==nr){
    e[pos].push_back(make_pair(8*n+nl,0)),e[8*n+nl].push_back(make_pair(pos,0));
    e[4*n+pos].push_back(make_pair(8*n+nl,0)),e[8*n+nl].push_back(make_pair(4*n+pos,0));
  }
  else{
    int mid=(nl+nr)>>1;
    build(pos<<1,nl,mid),build(pos<<1|1,mid+1,nr);
    e[pos].push_back(make_pair(pos<<1,0)),e[pos].push_back(make_pair(pos<<1|1,0));
    e[4*n+(pos<<1)].push_back(make_pair(4*n+pos,0)),e[4*n+(pos<<1|1)].push_back(make_pair(4*n+pos,0));
  }
}
void add1(int pos,int nl,int nr,int gl,int gr,int u,long long w){
  if(gl<=nl&&nr<=gr){
    e[8*n+u].push_back(make_pair(pos,w));
    return;
  }
  int mid=(nl+nr)>>1;
  if(gl<=mid)add1(pos<<1,nl,mid,gl,gr,u,w);
  if(gr>mid)add1(pos<<1|1,mid+1,nr,gl,gr,u,w);
}
void add2(int pos,int nl,int nr,int gl,int gr,int u,long long w){
  if(gl<=nl&&nr<=gr){
    e[4*n+pos].push_back(make_pair(8*n+u,w));
    return;
  }
  int mid=(nl+nr)>>1;
  if(gl<=mid)add2(pos<<1,nl,mid,gl,gr,u,w);
  if(gr>mid)add2(pos<<1|1,mid+1,nr,gl,gr,u,w);
}
void dijkstra(int st,int n,vector<pair<int,long long>>e[],long long dis[]){
  for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f3f3f3f3f;
  dis[st]=0,q.push(make_pair(0,st));
  while(!q.empty()){
    int now=q.top().second;
    q.pop();
    if(vis[now])continue;
    vis[now]=1;
    for(int i=0;i<e[now].size();i++){
      int v=e[now][i].first;
      long long w=e[now][i].second;
      if(dis[v]>dis[now]+w)dis[v]=dis[now]+w,q.push(make_pair(dis[v],v));
    }
  }
}
int main(){
  cin>>n>>m>>s,cnt=n,build(1,1,n);
  for(int i=1,opt,u,l,r;i<=m;i++){
    cin>>opt;
    if(opt==1)cin>>u>>l>>w,e[8*n+u].push_back(make_pair(8*n+l,w));
    else if(opt==2)cin>>u>>l>>r>>w,add1(1,1,n,l,r,u,w);
    else cin>>u>>l>>r>>w,add2(1,1,n,l,r,u,w);
  }
  dijkstra(8*n+s,9*n,e,dis);
  for(int i=1;i<=n;i++)cout<<(dis[8*n+i]==0x3f3f3f3f3f3f3f3f?-1:dis[8*n+i])<<(i==n?'\n':' ');
  return 0;
}

P6348

区间向区间连边也类似，把两个区间都拆分，然后 \log n 个区间向 \log n 个区间连边即可。

这样做边数是 O(m\log^2n) 的。可以优化，建两个虚点中转，让 \log n 个区间向虚点连零权边，在虚点之间连一权边。这样就把边数优化到 O(m\log n)。0/1 BFS 即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,s,dis[4900005];
vector<pair<int,int>>e[4900005];
bool vis[4900005];
deque<int>q;
void build(int pos,int nl,int nr){
  if(nl==nr){
    e[pos].push_back(make_pair(8*n+nl,0)),e[8*n+nl].push_back(make_pair(pos,0));
    e[4*n+pos].push_back(make_pair(8*n+nl,0)),e[8*n+nl].push_back(make_pair(4*n+pos,0));
  }
  else{
    int mid=(nl+nr)>>1;
    build(pos<<1,nl,mid),build(pos<<1|1,mid+1,nr);
    e[pos].push_back(make_pair(pos<<1,0)),e[pos].push_back(make_pair(pos<<1|1,0));
    e[4*n+(pos<<1)].push_back(make_pair(4*n+pos,0)),e[4*n+(pos<<1|1)].push_back(make_pair(4*n+pos,0));
  }
}
void add1(int pos,int nl,int nr,int gl,int gr,int u){
  if(gl<=nl&&nr<=gr){
    e[u].push_back(make_pair(pos,0));
    return;
  }
  int mid=(nl+nr)>>1;
  if(gl<=mid)add1(pos<<1,nl,mid,gl,gr,u);
  if(gr>mid)add1(pos<<1|1,mid+1,nr,gl,gr,u);
}
void add2(int pos,int nl,int nr,int gl,int gr,int u){
  if(gl<=nl&&nr<=gr){
    e[4*n+pos].push_back(make_pair(u,0));
    return;
  }
  int mid=(nl+nr)>>1;
  if(gl<=mid)add2(pos<<1,nl,mid,gl,gr,u);
  if(gr>mid)add2(pos<<1|1,mid+1,nr,gl,gr,u);
}
void bfs(int st,int n,vector<pair<int,int>>e[],int dis[]){
  for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f;
  dis[st]=0,q.push_front(st);
  while(!q.empty()){
    int now=q.front();
    q.pop_front();
    if(vis[now])continue;
    vis[now]=1;
    for(int i=0;i<e[now].size();i++){
      int v=e[now][i].first,w=e[now][i].second;
      if(dis[now]+w<dis[v]){
        dis[v]=dis[now]+w;
        if(w)q.push_back(v);
        else q.push_front(v);
      }
    }
  }
}
int main(){
  cin>>n>>m>>s,build(1,1,n);
  for(int i=1,a,b,c,d;i<=m;i++){
    cin>>a>>b>>c>>d;
    add1(1,1,n,c,d,9*n+i),add2(1,1,n,a,b,9*n+m+i),add1(1,1,n,a,b,9*n+2*m+i),add2(1,1,n,c,d,9*n+3*m+i);
    e[9*n+m+i].push_back(make_pair(9*n+i,1)),e[9*n+3*m+i].push_back(make_pair(9*n+2*m+i,1));
  }
  bfs(8*n+s,9*n+4*m,e,dis);
  for(int i=1;i<=n;i++)cout<<dis[8*n+i]<<'\n';
  return 0;
}

线段树分治

线段树分治一般用于带删除的问题，可以用一只 \log 的代价把删除变为撤销。假设有若干元素，出现时间可以看做一段段区间。

P5787

假如不删边，可以用种类并查集。

每条边的存在时间是一个区间。在时间轴上构建一颗线段树，将每条边按存在时间挂在线段树上。此时一个时刻存在的边就是线段树上叶子结点到祖先路径上的所有边。对线段树 DFS，在途中用并查集维护。

在回溯时，需要撤销这个节点的加边，这就将删除任意边变为撤销。用一个栈存储操作即可。

另一种写法是写成和其他分治一样，维护当前节点上挂了几个区间，递归时分到左右儿子。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,f[200005],sz[200005],st[200005],top;
struct node{
  int u,v;
};
vector<node>tr[400005];
int find(int x){
  return f[x]?find(f[x]):x;
}
bool merge(int u,int v){
  u=find(u),v=find(v);
  if(u==v)return 0;
  if(sz[u]<sz[v])swap(u,v);
  return f[v]=u,sz[u]+=sz[v]+1,st[++top]=v,1;
}
void del(){
  sz[f[st[top]]]-=sz[st[top]]+1,f[st[top--]]=0;
}
void add(int pos,int nl,int nr,int gl,int gr,node k){
  if(gl<=nl&&nr<=gr){
    tr[pos].push_back(k);
    return;
  }
  int mid=(nl+nr)>>1;
  if(gl<=mid)add(pos<<1,nl,mid,gl,gr,k);
  if(gr>mid)add(pos<<1|1,mid+1,nr,gl,gr,k);
}
void dfs(int pos,int nl,int nr){
  int temp=top;
  for(int i=0;i<tr[pos].size();i++){
    merge(tr[pos][i].u,tr[pos][i].v+n),merge(tr[pos][i].v,tr[pos][i].u+n);
    if(find(tr[pos][i].u)==find(tr[pos][i].u+n)){
      for(int j=nl;j<=nr;j++)puts("No");
      goto tag;
    }
  }
  if(nl==nr)puts("Yes");
  else{
    int mid=(nl+nr)>>1;
    dfs(pos<<1,nl,mid),dfs(pos<<1|1,mid+1,nr);
  }
  tag:while(top!=temp)del();
}
int main(){
  cin>>n>>m>>k;
  for(int i=1,u,v,l,r;i<=m;i++){
    cin>>u>>v>>l>>r;
    if(++l<=r)add(1,1,k,l,r,(node){u,v});
  }
  return dfs(1,1,k),0;
}

CF1814F

不难想到线段树分治，边的出现时间取决于端点的出现时间，考虑如何维护和 1 连通过的个数。维护每个节点和 1 连通的次数，当递归到 1 节点时，对 1 所在的根节点打一个子树加 1 标记。这个标记可以维护，合并时让 v 减掉 u 的标记，撤销时加上。最后所有边都会撤销，标记会下放到每个节点。

#include<bits/stdc++.h>
using namespace std;
int n,m,l[200005],r[200005],f[200005],sz[200005],tag[200005],st[400005],top;
struct node{
  int u,v;
};
vector<node>tr[800005];
int find(int x){
  return f[x]?find(f[x]):x;
}
bool merge(int u,int v){
  u=find(u),v=find(v);
  if(u==v)return 0;
  if(sz[u]<sz[v])swap(u,v);
  return f[v]=u,sz[u]+=sz[v]+1,tag[v]-=tag[u],st[++top]=v,1; 
}
void del(){
  sz[f[st[top]]]-=sz[st[top]],tag[st[top]]+=tag[f[st[top]]],f[st[top--]]=0;
}
void add(int pos,int nl,int nr,int gl,int gr,node k){
  if(gl<=nl&&nr<=gr){
    tr[pos].push_back(k);
    return;
  }
  int mid=(nl+nr)>>1;
  if(gl<=mid)add(pos<<1,nl,mid,gl,gr,k);
  if(gr>mid)add(pos<<1|1,mid+1,nr,gl,gr,k);
}
void dfs(int pos,int nl,int nr){
  int temp=top;
  for(int i=0;i<tr[pos].size();i++)merge(tr[pos][i].u,tr[pos][i].v);
  if(nl==nr)tag[find(1)]++;
  else{
    int mid=(nl+nr)>>1;
    dfs(pos<<1,nl,mid),dfs(pos<<1|1,mid+1,nr);
  }
  while(top!=temp)del();
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
  for(int i=1,u,v;i<=m;i++)cin>>u>>v,add(1,1,200000,max(l[u],l[v]),min(r[u],r[v]),(node){u,v});
  dfs(1,1,200000);
  for(int i=1;i<=n;i++)if(tag[i])cout<<i<<' ';
  return 0;
}

P12014

维护模小质数幂的多项式，有 trick 是令 x=pU+q，则 \prod(x+a_i)=\prod(pU+q+a_i)。我们将其看作有关 pU 的多项式，维护 U 个多项式，分别将 a_i+q 当做点权，此时每个多项式只用维护 0\sim V-1 次项。

线段树分治，对于每个连通块，维护这 U 个多项式的信息，以及多项式的和。用可撤销并查集维护连通块，加边时合并信息，就是多项式乘法，O(UV^2)。对于修改点权，可以假设初始状态每个多项式都是 1，修改时再乘上。撤销可以在修改时直接存一个信息的副本。O(n\log^2nUV^2)。

#include<bits/stdc++.h>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T&a){
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename ...Args>void in(T&a,Args&...args){
  in(a),in(args...);
}
int n,m,u,v,mod,a[100005],vd[100005],qx[100005],f[100005],sz[100005],top;
map<pair<int,int>,int>ve;
struct poly{
  int a[10][4];
  poly(){
    memset(a,0,sizeof(a));
  }
  poly&operator+=(poly b){
    for(int i=0;i<u;i++)for(int j=0;j<v;j++)a[i][j]=(a[i][j]+b.a[i][j])%mod;
    return *this;
  }
  poly&operator-=(poly b){
    for(int i=0;i<u;i++)for(int j=0;j<v;j++)a[i][j]=(a[i][j]-b.a[i][j]+mod)%mod;
    return *this;
  }
  poly operator*(poly b){
    poly ans;
    for(int i=0;i<u;i++)for(int j=0;j<v;j++)for(int k=0;k<v-j;k++)ans.a[i][j+k]+=a[i][j]*b.a[i][k];
    for(int i=0;i<u;i++)for(int j=0;j<v;j++)ans.a[i][j]%=mod;
    return ans;
  }
  int calc(int x,int ans=0){
    for(int i=v-1;i>=0;i--)ans=(1ll*ans*(x-x%u)+a[x%u][i])%mod;
    return ans;
  }
}p[100005],now;
struct modify{
  int opt,x,y;
};
vector<modify>tr[400005];
struct info{
  modify a;
  poly b;
}st[200005];
int find(int x){
  return f[x]?find(f[x]):x;
}
bool merge(int u,int v){
  u=find(u),v=find(v);
  if(u==v)return 0;
  if(sz[u]<sz[v])swap(u,v);
  return f[v]=u,sz[u]+=sz[v]+1,st[++top]=(info){(modify){0,u,v},p[u]},now-=p[u],now-=p[v],p[u]=p[u]*p[v],now+=p[u],1;
}
void assign(int x,int k){
  poly c;
  x=find(x);
  for(int i=0;i<u;i++)c.a[i][0]=(k+i)%mod,c.a[i][1]=1;
  st[++top]=(info){(modify){1,x,k},p[x]},now-=p[x],p[x]=p[x]*c,now+=p[x];
}
void del(){
  info t=st[top--];
  if(!t.a.opt)sz[t.a.x]-=sz[t.a.y]+1,f[t.a.y]=0,now+=p[t.a.y];
  now-=p[t.a.x],p[t.a.x]=t.b,now+=t.b;
}
void add(int pos,int nl,int nr,int gl,int gr,modify k){
  if(gl>gr)return;
  if(gl<=nl&&nr<=gr){
    tr[pos].push_back(k);
    return;
  }
  int mid=(nl+nr)>>1;
  if(gl<=mid)add(pos<<1,nl,mid,gl,gr,k);
  if(gr>mid)add(pos<<1|1,mid+1,nr,gl,gr,k);
}
void dfs(int pos,int nl,int nr){
  int temp=top;
  for(int i=0;i<tr[pos].size();i++){
    if(tr[pos][i].opt)assign(tr[pos][i].x,tr[pos][i].y);
    else merge(tr[pos][i].x,tr[pos][i].y);
  }
  if(nl==nr){
    if(qx[nl]!=-1)cout<<now.calc(qx[nl])<<'\n';
  }
  else{
    int mid=(nl+nr)>>1;
    dfs(pos<<1,nl,mid),dfs(pos<<1|1,mid+1,nr);
  }
  while(temp!=top)del();
}
int main(){
  memset(qx,-1,sizeof(qx)),in(n,m,u,v),mod=pow(u,v);
  for(int i=1;i<=n;i++){
    in(a[i]),vd[i]=1;
    for(int j=0;j<u;j++)p[i].a[j][0]=1;
    now+=p[i];
  }
  for(int i=1,opt,x,y;i<=m;i++){
    in(opt);
    if(opt==1){
      in(x,y);
      if(x>y)swap(x,y);
      ve[make_pair(x,y)]=i;
    }
    else if(opt==2){
      in(x,y);
      if(x>y)swap(x,y);
      add(1,1,m,ve[make_pair(x,y)],i-1,(modify){0,x,y}),ve.erase(make_pair(x,y));
    }
    else if(opt==3)in(x,y),add(1,1,m,vd[x],i-1,(modify){1,x,a[x]}),vd[x]=i,a[x]=y;
    else in(qx[i]);
  }
  for(map<pair<int,int>,int>::iterator it=ve.begin();it!=ve.end();it++)add(1,1,m,(*it).second,m,(modify){0,(*it).first.first,(*it).first.second});
  for(int i=1;i<=n;i++)add(1,1,m,vd[i],m,(modify){1,i,a[i]});
  return dfs(1,1,m),0;
}

QOJ1878

考虑从 s 开始，此时只保留 \min(c_u,c_v)\geq b_s 的边。我们考虑在 b 的最大值变化之前， \max(b_u,b_v)\leq b_s 的边可以双向走，\min(b_u,b_v)\leq b_s<\max(b_u,b_v) 的只能从较小的走到较大的，假如按 b_s 从大到小求解，一旦 b 的最大值被更新，就可以调用新节点的 ans。

我们只需要维护双向边连通块的 a 的最大值，和连通块邻域的 ans 最大值。上个线段树分治，可撤销并查集维护。有两种修改：并查集连边、单向边用 ans 更新，都扔到栈里存着。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[200005],b[200005],c[200005],temp[400005],cnt,f[200005],sz[200005],top,ans[200005];
bool type;
vector<int>q[400005];
struct edge{
  int u,v,l,r;
  bool type;
};
vector<edge>e;
struct info{
  int u,v,k;
}st[400005];
int find(int x){
  return f[x]?find(f[x]):x;
}
bool merge(int u,int v){
  u=find(u),v=find(v);
  if(u==v)return 0;
  if(sz[u]<sz[v])swap(u,v);
  return f[v]=u,sz[u]+=sz[v]+1,st[++top]=(info){u,v,a[u]},a[u]=max(a[u],a[v]),1;
}
void solve(int nl,int nr,vector<edge>e){
  int temp=top,mid=(nl+nr)>>1;
  vector<edge>t1,t2;
  for(int i=0;i<e.size();i++){
    if(e[i].l<=nl&&nr<=e[i].r){
      if(e[i].type)merge(e[i].u,e[i].v);
      else{
        int u=find(e[i].u);
        st[++top]=(info){u,0,a[u]},a[u]=max(a[u],ans[e[i].v]);
      }
    }
    else{
      if(e[i].l<=mid)t1.push_back(e[i]);
      if(e[i].r>mid)t2.push_back(e[i]);
    }
  }
  if(nl==nr)for(int i=0;i<q[nl].size();i++)ans[q[nl][i]]=a[find(q[nl][i])];
  else solve(mid+1,nr,t2),solve(nl,mid,t1);
  while(top!=temp){
    if(st[top].v)sz[st[top].u]-=sz[st[top].v]+1,f[st[top].v]=0;
    a[st[top].u]=st[top].k,top--;
  }
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cin>>type>>n>>m;
  for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i],temp[i]=b[i],temp[n+i]=c[i];
  sort(temp+1,temp+2*n+1),cnt=unique(temp+1,temp+2*n+1)-temp-1;
  for(int i=1;i<=n;i++)b[i]=lower_bound(temp+1,temp+cnt+1,b[i])-temp,c[i]=lower_bound(temp+1,temp+cnt+1,c[i])-temp,q[b[i]].push_back(i);
  for(int i=1,u,v;i<=m;i++){
    cin>>u>>v;
    if(b[u]>b[v])swap(u,v);
    if(b[v]<=min(c[u],c[v]))e.push_back((edge){u,v,b[v],min(c[u],c[v]),1});
    if(b[u]<b[v])e.push_back((edge){u,v,b[u],min(c[u],b[v]-1),0});
  }
  solve(1,cnt,e);
  if(type)for(int i=1;i<=n;i++)cout<<ans[i]<<(i==n?'\n':' ');
  else cout<<ans[1]<<'\n';
  return 0;
}

整体 DP

整体 DP 即线段树合并维护 DP。这要求有效的位置足够少，比如在树上，每个叶子只有一个有效位置，就可通过线段树合并进行子树合并。

在线段树合并时也可以维护前后缀的信息，在其中一个节点为空时，可以对另一个节点打标记，这样就实现用前后缀信息更新 DP 数组。此处标记只用下传给有效位置。

P4577

考虑用线段树合并替换启发式合并，设 f_{i,j} 表示 i 子树中最小值为 j 的最大点集。则合并两颗子树 u,v 有 f_{u,i}=\max(f_{u,i}+\max_{j=i}^V\{f_{v,j}\},f_{v,i}+\max_{j=i}^V\{f_{u,j}\})。加入 a_u 时有 f_{u,a_u}\gets\max_{j=a_u}^V\{f_{u,j}\}+1。前者可以线段树合并时维护两棵树的后缀 \max，当有一个节点为空时对另一个节点打加法标记。同时在树上维护区间最大值。

#include<bits/stdc++.h>
using namespace std;
int n,a[200005],rt[200005];
vector<int>e[200005];
struct node{
  int v,tag,ls,rs;
};
template<int maxn>struct SMT{
  node tr[maxn];
  int cnt;
  void pushdown(int pos){
    if(tr[pos].ls)tr[tr[pos].ls].tag+=tr[pos].tag,tr[tr[pos].ls].v+=tr[pos].tag;
    if(tr[pos].rs)tr[tr[pos].rs].tag+=tr[pos].tag,tr[tr[pos].rs].v+=tr[pos].tag;
    tr[pos].tag=0;
  }
  void pushup(int pos){
    tr[pos].v=max(tr[tr[pos].ls].v,tr[tr[pos].rs].v);
  }
  void modify(int&pos,int nl,int nr,int g,int k){
    if(!pos)pos=++cnt;
    if(nl==nr){
      tr[pos].v=max(tr[pos].v,k);
      return;
    }
    pushdown(pos);
    int mid=(nl+nr)>>1;
    if(g<=mid)modify(tr[pos].ls,nl,mid,g,k);
    else modify(tr[pos].rs,mid+1,nr,g,k);
    pushup(pos);
  }
  int query(int pos,int nl,int nr,int gl,int gr){
    if(!pos)return 0;
    if(gl<=nl&&nr<=gr)return tr[pos].v;
    pushdown(pos);
    int mid=(nl+nr)>>1,ans=0;
    if(gl<=mid)ans=max(ans,query(tr[pos].ls,nl,mid,gl,gr));
    if(gr>mid)ans=max(ans,query(tr[pos].rs,mid+1,nr,gl,gr));
    return ans;
  }
  int merge(int a,int b,int nl,int nr,int x,int y){
    if(!a&&!b)return 0;
    if(!b)return tr[a].tag+=y,tr[a].v+=y,a;
    if(!a)return tr[b].tag+=x,tr[b].v+=x,b;
    if(nl==nr)return tr[a].v=max(tr[a].v+max(tr[b].v,y),tr[b].v+max(tr[a].v,x)),a;
    pushdown(a),pushdown(b);
    int mid=(nl+nr)>>1;
    tr[a].ls=merge(tr[a].ls,tr[b].ls,nl,mid,max(x,tr[tr[a].rs].v),max(y,tr[tr[b].rs].v));
    tr[a].rs=merge(tr[a].rs,tr[b].rs,mid+1,nr,x,y);
    return pushup(a),a;
  }
};
SMT<10000005>t;
void dfs(int pos){
  int sum=1;
  for(int i=0;i<e[pos].size();i++){
    dfs(e[pos][i]);
    sum+=t.query(rt[e[pos][i]],1,1e9,a[pos],1e9);
    rt[pos]=t.merge(rt[pos],rt[e[pos][i]],1,1e9,0,0);
  }
  t.modify(rt[pos],1,1e9,a[pos],sum);
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=2,f;i<=n;i++)cin>>f,e[f].push_back(i);
  return dfs(1),cout<<t.tr[rt[1]].v<<'\n',0;
}

P5298

设 f_{i,j} 表示 i 的权值是第 j 大的概率，则 f_{i,j}=f_{ls,j}(\sum_{k=1}^{j-1}pf_{rs,k}+\sum_{k=j+1}^m(1-p)f_{rs,k})+f_{rs,j}(\sum_{k=1}^{j-1}pf_{ls,k}+\sum_{k=j+1}^m(1-p)f_{ls,k})。

考虑整体 DP。线段树维护 f 和区间和，在线段树合并过程中，可以维护出当前 f_{ls,j} 和 f_{rs,j} 的系数。当其中一棵树没有节点时，可以对另一个节点代表的区间乘上系数，打乘法 tag 即可。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,p[300005],tr[300005][2],temp[300005],cnt,rt[300005],d[300005],ans;
struct node{
  int ls,rs,v,tag;
};
template<int maxn>struct SMT{
  node tr[maxn];
  int cnt=0;
  void pushdown(int pos){
    if(tr[pos].tag!=1){
      if(tr[pos].ls)tr[tr[pos].ls].tag=1ll*tr[tr[pos].ls].tag*tr[pos].tag%mod,tr[tr[pos].ls].v=1ll*tr[tr[pos].ls].v*tr[pos].tag%mod;
      if(tr[pos].rs)tr[tr[pos].rs].tag=1ll*tr[tr[pos].rs].tag*tr[pos].tag%mod,tr[tr[pos].rs].v=1ll*tr[tr[pos].rs].v*tr[pos].tag%mod;
      tr[pos].tag=1;
    }
  }
  void pushup(int pos){
    tr[pos].v=(tr[tr[pos].ls].v+tr[tr[pos].rs].v)%mod;
  }
  void modify(int&pos,int nl,int nr,int g,int k){
    if(!pos)pos=++cnt,tr[pos].ls=tr[pos].rs=tr[pos].v=0,tr[pos].tag=1;
    if(nl==nr){
      tr[pos].v=k;
      return;
    }
    pushdown(pos);
    int mid=(nl+nr)>>1;
    if(g<=mid)modify(tr[pos].ls,nl,mid,g,k);
    else modify(tr[pos].rs,mid+1,nr,g,k);
    pushup(pos);
  }
  int query(int pos,int nl,int nr,int g){
    if(!pos)return 0;
    if(nl==nr)return tr[pos].v;
    pushdown(pos);
    int mid=(nl+nr)>>1;
    if(g<=mid)return query(tr[pos].ls,nl,mid,g);
    else return query(tr[pos].rs,mid+1,nr,g);
  }
  int merge(int a,int b,int nl,int nr,int x,int y,int p){
    if(!b)return tr[a].tag=1ll*tr[a].tag*x%mod,tr[a].v=1ll*tr[a].v*x%mod,a;
    if(!a)return tr[b].tag=1ll*tr[b].tag*y%mod,tr[b].v=1ll*tr[b].v*y%mod,b;
    pushdown(a),pushdown(b);
    int mid=(nl+nr)>>1,xl=tr[tr[a].ls].v,xr=tr[tr[a].rs].v,yl=tr[tr[b].ls].v,yr=tr[tr[b].rs].v;
    tr[a].ls=merge(tr[a].ls,tr[b].ls,nl,mid,(x+1ll*(mod+1-p)*yr%mod)%mod,(y+1ll*(mod+1-p)*xr%mod)%mod,p);
    tr[a].rs=merge(tr[a].rs,tr[b].rs,mid+1,nr,(x+1ll*p*yl%mod)%mod,(y+1ll*p*xl%mod)%mod,p);
    return pushup(a),a;
  }
};
SMT<10000005>t;
void dfs(int pos){
  if(!tr[pos][0])t.modify(rt[pos],1,cnt,p[pos],1);
  else if(!tr[pos][1])dfs(tr[pos][0]),rt[pos]=rt[tr[pos][0]];
  else dfs(tr[pos][0]),dfs(tr[pos][1]),rt[pos]=t.merge(rt[tr[pos][0]],rt[tr[pos][1]],1,cnt,0,0,p[pos]);
}
int main(){
  cin>>n;
  for(int i=1,f;i<=n;i++){
    cin>>f;
    if(!tr[f][0])tr[f][0]=i;
    else tr[f][1]=i;
  }
  for(int i=1;i<=n;i++){
    cin>>p[i];
    if(!tr[i][0]&&!tr[i][1])temp[++cnt]=p[i];
  }
  sort(temp+1,temp+cnt+1),cnt=unique(temp+1,temp+cnt+1)-temp-1;
  for(int i=1;i<=n;i++)p[i]=!tr[i][0]&&!tr[i][1]?lower_bound(temp+1,temp+cnt+1,p[i])-temp:796898467ll*p[i]%mod;
  dfs(1);
  for(int i=1;i<=cnt;i++)d[i]=t.query(rt[1],1,cnt,i),ans=(ans+1ll*i*temp[i]%mod*d[i]%mod*d[i]%mod)%mod;
  return cout<<ans<<'\n',0;
}

P6773

树形 DP。考虑如何设计状态。对于每个节点作为限制的下端，可以只保留上端中深度最深的，因为其他限制被完全包含。当 DP 到某个节点时，我们只关心下端在子树内，且上端最深的未满足的限制。可以设 f_{i,j} 表示 i 子树中下端在 i 子树内的未满足限制上端最大深度为 j 的方案数，j=0 表示所有限制都已满足。

转移时合并 u 和子树 v，分讨 (u,v) 状态。当 f(u,v)=1，v 子树内都被满足任意，u 取 i，v 任意；否则 u,v 的最大值为 i。则 f_{u,i}\gets\sum_{j=0}^{dep_u}f_{u,i}f_{v,j}+\sum_{j=0}^if_{u,i}f_{v,j}+\sum_{j=0}^{i-1}f_{u,j}f_{v,i}。

这个过程可以整体 DP，线段树合并时维护 f_u,f_v 的前缀和，打乘法 tag 即可。初始状态为只有深度最深的上端点处有值 1。

#include<bits/stdc++.h>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T&a){
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename ...Args>void in(T&a,Args&...args){
  in(a),in(args...);
}
const int mod=998244353;
int n,m,dep[500005],maxd[500005],rt[500005];
vector<int>e[500005];
struct node{
  int ls,rs,v,tag=1;
};
template<int maxn>struct SMT{
  node tr[maxn];
  int cnt;
  void pushdown(int pos){
    if(tr[pos].ls)tr[tr[pos].ls].tag=1ll*tr[tr[pos].ls].tag*tr[pos].tag%mod,tr[tr[pos].ls].v=1ll*tr[tr[pos].ls].v*tr[pos].tag%mod;
    if(tr[pos].rs)tr[tr[pos].rs].tag=1ll*tr[tr[pos].rs].tag*tr[pos].tag%mod,tr[tr[pos].rs].v=1ll*tr[tr[pos].rs].v*tr[pos].tag%mod;
    tr[pos].tag=1;
  }
  void pushup(int pos){
    tr[pos].v=(tr[tr[pos].ls].v+tr[tr[pos].rs].v)%mod;
  }
  void modify(int&pos,int nl,int nr,int g,int k){
    if(!pos)pos=++cnt;
    if(nl==nr){
      tr[pos].v=k;
      return;
    }
    pushdown(pos);
    int mid=(nl+nr)>>1;
    if(g<=mid)modify(tr[pos].ls,nl,mid,g,k);
    else modify(tr[pos].rs,mid+1,nr,g,k);
    pushup(pos);
  }
  int query(int pos,int nl,int nr,int gl,int gr){
    if(!pos)return 0;
    if(gl<=nl&&nr<=gr)return tr[pos].v;
    pushdown(pos);
    int mid=(nl+nr)>>1,ans=0;
    if(gl<=mid)ans=(ans+query(tr[pos].ls,nl,mid,gl,gr))%mod;
    if(gr>mid)ans=(ans+query(tr[pos].rs,mid+1,nr,gl,gr))%mod;
    return ans;
  }
  int merge(int a,int b,int nl,int nr,int x,int y){
    if(!a&&!b)return 0;
    if(!b)return tr[a].tag=1ll*tr[a].tag*y%mod,tr[a].v=1ll*tr[a].v*y%mod,a;
    if(!a)return tr[b].tag=1ll*tr[b].tag*x%mod,tr[b].v=1ll*tr[b].v*x%mod,b;
    if(nl==nr)return y=(y+tr[b].v)%mod,tr[a].v=(1ll*tr[a].v*y%mod+1ll*tr[b].v*x%mod)%mod,a;
    pushdown(a),pushdown(b);
    int mid=(nl+nr)>>1,tx=tr[tr[a].ls].v,ty=tr[tr[b].ls].v;
    tr[a].ls=merge(tr[a].ls,tr[b].ls,nl,mid,x,y);
    tr[a].rs=merge(tr[a].rs,tr[b].rs,mid+1,nr,(x+tx)%mod,(y+ty)%mod);
    return pushup(a),a;
  }
};
SMT<10000005>t;
void dfs(int pos,int fa){
  dep[pos]=dep[fa]+1;
  for(int i=0;i<e[pos].size();i++)if(e[pos][i]!=fa)dfs(e[pos][i],pos);
}
void dfs1(int pos,int fa){
  t.modify(rt[pos],0,n,maxd[pos],1);
  for(int i=0;i<e[pos].size();i++)if(e[pos][i]!=fa)dfs1(e[pos][i],pos),rt[pos]=t.merge(rt[pos],rt[e[pos][i]],0,n,0,t.query(rt[e[pos][i]],0,n,0,dep[pos]));
}
int main(){
  in(n);
  for(int i=1,u,v;i<n;i++)in(u,v),e[u].push_back(v),e[v].push_back(u);
  dfs(1,0),in(m);
  for(int i=1,u,v;i<=m;i++)in(u,v),maxd[v]=max(maxd[v],dep[u]);
  return dfs1(1,0),cout<<t.query(rt[1],0,n,0,0)<<'\n',0;
}

猫树

线段树可以将区间拆分成 O(\log n) 个节点。我们尝试换一种方式将区间拆分成 O(1) 个节点：对线段树的每个节点，做 [l,mid] 的后缀和与 (mid+1,r] 的前缀和。

假如查询 [l,r]，向上找到节点 [l,l],[r,r] 的 LCA，这个节点代表的区间包含 l,r 且 l,r 在这个节点的中点两侧。这就可以用一个前缀和与一个后缀和合并出来。

这个 LCA 可以 O(1)。将数组补成 2 的幂，则这是一个满二叉树，可以位运算找出 LCA。

复杂度为 O(n\log n)-O(1)。对于一些加入元素的复杂度小于合并复杂度的信息，可以优化复杂度。

SP1043

假如用线段树维护，每个节点要维护区间和、最大子段和、最大前缀、最大后缀。但是用猫树只用维护最大子段和与最大前缀或后缀。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[65541],d,v1[65541][20],v2[65541][20];
void build(int n,int a[]){
  d=__lg(n-1)+1;
  for(int i=1;i<=d;i++){
    for(int l=1,r=1<<i;r<=1<<d;l+=1<<i,r+=1<<i){
      int mid=l+(1<<(i-1))-1;
      v1[mid][i]=v2[mid][i]=a[mid],v1[mid+1][i]=v2[mid+1][i]=a[mid+1];
      for(int j=mid-1,t1=max(a[mid],0),t2=a[mid];j>=l;j--){
        t1+=a[j],t2+=a[j];
        v1[j][i]=max(v1[j+1][i],t1),v2[j][i]=max(v2[j+1][i],t2),t1=max(t1,0);
      }
      for(int j=mid+2,t1=max(a[mid+1],0),t2=a[mid+1];j<=r;j++){
        t1+=a[j],t2+=a[j];
        v1[j][i]=max(v1[j-1][i],t1),v2[j][i]=max(v2[j-1][i],t2),t1=max(t1,0);
      }
    }
  }
}
int query(int l,int r){
  if(l==r)return a[l];
  int p=__lg((l-1)^(r-1))+1;
  return max(v2[l][p]+v2[r][p],max(v1[l][p],v1[r][p])); 
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  build(n,a),cin>>m;
  for(int i=1,l,r;i<=m;i++)cin>>l>>r,cout<<query(l,r)<<'\n';
  return 0;
}

单侧递归线段树

在线段树上维护复杂信息时，我们可以在子树里面查询信息、二分，以一只 log 的代价 pushup。

P4198

单侧递归线段树模板。问题是查询 \frac{h_i}i 的严格前缀最大值个数。考虑在线段树上这个信息怎么 pushup，我们需要查右子树在当前值是左子树最大值的情况下前缀最大值的个数。

发现这个信息是可以在右子树里二分出来的。若查询的 k 大于等于左子树最大值，递归到右子树。否则右子树的选法照常（注意这里右子树的前缀最大值是在考虑整个当前区间的基础上，所以是 cnt_{pos}-cnt_{ls}），递归到左子树。这样一次 pushup 是 O(\log n) 的，总复杂度 O(n\log^2n)。

另一种写法是维护右子树在左子树的基础上的前缀最大值个数，查询时调用一次 pushup。这样避免了减法。

#include<bits/stdc++.h>
using namespace std;
int n,m;
double a[100005];
template<typename T>struct node{
  T v,maxn;
};
template<typename T,int maxn>struct SMT{
  node<T>tr[maxn];
  int calc(int pos,int nl,int nr,T k){
    if(nl==nr)return tr[pos].maxn>k;
    int mid=(nl+nr)>>1;
    if(tr[pos<<1].maxn<=k)return calc(pos<<1|1,mid+1,nr,k);
    else return calc(pos<<1,nl,mid,k)+tr[pos].v-tr[pos<<1].v;
  }
  void pushup(int pos,int nl,int nr){
    int mid=(nl+nr)>>1;
    tr[pos].v=tr[pos<<1].v+calc(pos<<1|1,mid+1,nr,tr[pos<<1].maxn);
    tr[pos].maxn=max(tr[pos<<1].maxn,tr[pos<<1|1].maxn);
  }
  void modify(int pos,int nl,int nr,int g,T k){
    if(nl==nr){
      tr[pos].v=1,tr[pos].maxn=k;
      return;
    }
    int mid=(nl+nr)>>1;
    if(g<=mid)modify(pos<<1,nl,mid,g,k);
    else modify(pos<<1|1,mid+1,nr,g,k);
    pushup(pos,nl,nr);
  }
};
SMT<double,400005>t;
int main(){
  cin>>n>>m;
  for(int i=1,x,y;i<=m;i++)cin>>x>>y,t.modify(1,1,n,x,1.0*y/x),cout<<t.tr[1].v<<'\n';
  return 0;
}

AT_jsc2019_final_h

拿个 set 维护同色的上一个数，则左端点在 R 时，右端点不能是 \max(l,\max_{i=l}^Rpre_i) 与更左，问题变为查询区间前缀最大值的和。

考虑单侧递归线段树，我们查询之前的前缀最大值是 k，当前区间的前缀最大值之和。若 k 大于等于左子树最大值，左子树贡献 k(mid-l+1)，递归到右子树。否则右子树贡献 v_{pos}-v_{ls}，递归到左子树。查询和 pushup 类似，依次把区间并起来即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005];
set<int>s[500005];
template<typename T>struct node{
  T v,maxn;
};
template<typename T,int maxn>struct SMT{
  node<T>tr[maxn];
  long long calc(int pos,int nl,int nr,T k){
    if(nl==nr)return max(k,tr[pos].maxn);
    int mid=(nl+nr)>>1;
    if(tr[pos<<1].maxn<=k)return (mid-nl+1)*k+calc(pos<<1|1,mid+1,nr,k);
    else return calc(pos<<1,nl,mid,k)+tr[pos].v-tr[pos<<1].v;
  }
  void pushup(int pos,int nl,int nr){
    int mid=(nl+nr)>>1;
    tr[pos].v=tr[pos<<1].v+calc(pos<<1|1,mid+1,nr,tr[pos<<1].maxn);
    tr[pos].maxn=max(tr[pos<<1].maxn,tr[pos<<1|1].maxn);
  }
  void modify(int pos,int nl,int nr,int g,T k){
    if(nl==nr){
      tr[pos].v=tr[pos].maxn=k;
      return;
    }
    int mid=(nl+nr)>>1;
    if(g<=mid)modify(pos<<1,nl,mid,g,k);
    else modify(pos<<1|1,mid+1,nr,g,k);
    pushup(pos,nl,nr);
  }
  node<T>query(int pos,int nl,int nr,int gl,int gr,node<T>now){
    if(gl<=nl&&nr<=gr){
      now.v+=calc(pos,nl,nr,now.maxn);
      now.maxn=max(now.maxn,tr[pos].maxn);
      return now;
    }
    int mid=(nl+nr)>>1;
    if(gl<=mid)now=query(pos<<1,nl,mid,gl,gr,now);
    if(gr>mid)now=query(pos<<1|1,mid+1,nr,gl,gr,now);
    return now;
  }
};
SMT<long long,2000005>t;
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cin>>n>>m;
  for(int i=0;i<n;i++)s[i].insert(0);
  for(int i=1;i<=n;i++)cin>>a[i],t.modify(1,1,n,i,*s[a[i]].rbegin()),s[a[i]].insert(i);
  for(int i=1,opt,x,y;i<=m;i++){
    cin>>opt>>x>>y,x++;
    if(opt)cout<<1ll*(x+y)*(y-x+1)/2-t.query(1,1,n,x,y,(node<long long>){0,x-1}).v<<'\n';
    else{
      set<int>::iterator it=s[a[x]].find(x),pre;
      it=s[a[x]].erase(it),pre=it;
      if(it!=s[a[x]].end())t.modify(1,1,n,*it,*--pre);
      a[x]=y,it=s[a[x]].upper_bound(x),pre=it;
      if(it!=s[a[x]].end())t.modify(1,1,n,*it,x);
      t.modify(1,1,n,x,*--pre),s[a[x]].insert(x);
    }
  }
  return 0;
}

CF1340F

我们考虑在线段树上维护这个信息。首先，如果出现一对相向的不同种括号，如 (]，一定不合法。此时，一个区间内没匹配上的括号形如一段右括号接一段左括号，称为左串和右串。

合并的时候，我们拿左子树的右串和右子树的左串消，长度小的那边要完全匹配上，哈希维护，我们要查左串的某前缀/右串的某后缀的哈希值。

发现，因为我们要求一定能消，我们往子树里单侧递归，是能确定该前缀/后缀的位置的。以左串的某前缀为例，若长度不超过左子树的左串就往左递归。否则用左次数的左串，拼上右子树的左串消掉右子树的右串后的某前缀。

发现查询时有问题，我们合并时可能往左子树或右子树递归，但区间合并后就不是节点了。但是我们可以在一个节点合并左子树的后缀和右子树的前缀，仍然能单侧递归。一个问题是可能出现节点本身不合法，但其前/后缀可能合法。因此对标记为不合法的串仍然维护其左串/右串。O(n\log^2n)。

#include<bits/stdc++.h>
using namespace std;
const unsigned long long base=1145141;
int n,m,cnt;
unsigned long long p[100005];
struct hash_node{
  int l;
  unsigned long long h;
};
struct node{
  hash_node l,r;
  bool fail;
}a[100005],tr[400005];
unsigned long long querypre(int pos,int k){
  if(!k)return 0;
  if(tr[pos].l.l==k)return tr[pos].l.h;
  if(tr[pos<<1].l.l>=k)return querypre(pos<<1,k);
  else return tr[pos<<1].l.h*p[k-tr[pos<<1].l.l]+querypre(pos<<1|1,k-tr[pos<<1].l.l+tr[pos<<1].r.l)-tr[pos<<1].r.h*p[k-tr[pos<<1].l.l];
}
unsigned long long querysuf(int pos,int k){
  if(!k)return 0;
  if(tr[pos].r.l==k)return tr[pos].r.h;
  if(tr[pos<<1|1].r.l>=k)return querysuf(pos<<1|1,k);
  else return tr[pos<<1|1].r.h*p[k-tr[pos<<1|1].r.l]+querysuf(pos<<1,k-tr[pos<<1|1].r.l+tr[pos<<1|1].l.l)-tr[pos<<1|1].l.h*p[k-tr[pos<<1|1].r.l];
}
node merge(int pos,node ls,node rs){
  node now=(node){ls.l,rs.r,ls.fail||rs.fail};
  if(ls.r.l<rs.l.l){
    now.l.l=rs.l.l-ls.r.l+ls.l.l;
    if(ls.r.h==querypre(pos<<1|1,ls.r.l))now.l.h=ls.l.h*p[rs.l.l-ls.r.l]+rs.l.h-ls.r.h*p[rs.l.l-ls.r.l];
    else now.fail=1;
  }
  else if(ls.r.l>rs.l.l){
    now.r.l=ls.r.l-rs.l.l+rs.r.l;
    if(rs.l.h==querysuf(pos<<1,rs.l.l))now.r.h=rs.r.h*p[ls.r.l-rs.l.l]+ls.r.h-rs.l.h*p[ls.r.l-rs.l.l];
    else now.fail=1;
  }
  else if(ls.r.h!=rs.l.h)now.fail=1;
  return now;
}
void pushup(int pos){
  tr[pos]=merge(pos,tr[pos<<1],tr[pos<<1|1]);
}
void build(int pos,int nl,int nr,node a[]){
  if(nl==nr)tr[pos]=a[nl];
  else{
    int mid=(nl+nr)>>1;
    build(pos<<1,nl,mid,a),build(pos<<1|1,mid+1,nr,a),pushup(pos);
  }
}
void modify(int pos,int nl,int nr,int g,node k){
  if(nl==nr){
    tr[pos]=k;
    return;
  }
  int mid=(nl+nr)>>1;
  if(g<=mid)modify(pos<<1,nl,mid,g,k);
  else modify(pos<<1|1,mid+1,nr,g,k);
  pushup(pos);
}
node query(int pos,int nl,int nr,int gl,int gr){
  if(gl<=nl&&nr<=gr)return tr[pos];
  int mid=(nl+nr)>>1;
  if(gr<=mid)return query(pos<<1,nl,mid,gl,gr);
  if(gl>mid)return query(pos<<1|1,mid+1,nr,gl,gr);
  return merge(pos,query(pos<<1,nl,mid,gl,gr),query(pos<<1|1,mid+1,nr,gl,gr));
};
int main(){
  ios::sync_with_stdio(0),cin.tie(0),p[0]=1,cin>>n>>m;
  for(int i=1;i<=n;i++)p[i]=p[i-1]*base;
  for(int i=1,t;i<=n;i++)cin>>t,a[i]=t>0?(node){(hash_node){0,0},(hash_node){1,t},0}:(node){(hash_node){1,-t},(hash_node){0,0},0};
  build(1,1,n,a),cin>>m;
  for(int i=1,opt,x,y;i<=m;i++){
    cin>>opt>>x>>y;
    if(opt==1)modify(1,1,n,x,y>0?(node){(hash_node){0,0},(hash_node){1,y},0}:(node){(hash_node){1,-y},(hash_node){0,0},0});
    else{
      node temp=query(1,1,n,x,y);
      puts(!temp.fail&&!temp.l.l&&!temp.r.l?"Yes":"No");
    }
  }
  return 0;
}

P6781

类似 CF1340F，拿个平衡树维护，未匹配括号是一段右括号接一段左括号。合并时我们拿左子树的左括号消右子树的右括号，问题变为查未匹配左括号的一段前缀/右括号的一段后缀。单侧递归，若时左子树的左括号消完了，递归到右子树；若查询长度不超过左子树的左括号消之后的长度，递归到左子树；否则可以对每个节点记一下对消之后的部分，减去长度后递归到右子树。

一个小问题是 \operatorname{nand} 的性质很差，无结合律。我们可以对每个位维护一个置换，这样就有结合律，具体来说，维护全 0 和全 1 的数变成了什么，可以位运算合并。O(n+m\log^2n)（建树是 T(n)+T(\frac n2)+O(n\log n)=O(n) 的）。

#include<bits/stdc++.h>
using namespace std;
char buf1[2097152],*ip1=buf1,*ip2=buf1;
inline int getc(){
  return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++;
}
template<typename T>void in(T&a){
  T ans=0;
  char c=getc();
  for(;c<'0'||c>'9';c=getc());
  for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0';
  a=ans;
}
template<typename T,typename ...Args>void in(T&a,Args&...args){
  in(a),in(args...);
}
int n,m,rt;
bool a[2000005];
unsigned int b[2000005],y;
struct info{
  int l;
  unsigned int f0,f1,maxn;
  info(){
    l=f0=maxn=0,f1=-1u;
  }
  info(int a,unsigned int b,unsigned int c,unsigned int d){
    l=a,f0=b,f1=c,maxn=d;
  }
};
inline info calc(info a,info b){
  return info(a.l+b.l,(~a.f0&b.f0)|(a.f0&b.f1),(~a.f1&b.f0)|(a.f1&b.f1),max(a.maxn,b.maxn));
}
struct node{
  int tr[2],sz;
  info l,mid,r;
  bool type;
};
template<int maxn>struct WBLT{
  node tr[maxn];
  int cnt,st[maxn],top;
  int newnode(){
    int pos=top?st[top--]:++cnt;
    return tr[pos]=node(),pos;
  }
  info querypre(int pos,int k){
    int ls=tr[pos].tr[0],rs=tr[pos].tr[1];
    if(!k)return info();
    if(k==tr[pos].r.l)return tr[pos].r;
    if(tr[ls].r.l<=tr[rs].l.l)return querypre(rs,k);
    else if(k<=tr[pos].mid.l)return querypre(ls,k);
    else return calc(tr[pos].mid,querypre(rs,k-tr[pos].mid.l));
  }
  info querysuf(int pos,int k){
    int ls=tr[pos].tr[0],rs=tr[pos].tr[1];
    if(!k)return info();
    if(k==tr[pos].l.l)return tr[pos].l;
    if(tr[rs].l.l<=tr[ls].r.l)return querysuf(ls,k);
    else if(k<=tr[pos].mid.l)return querysuf(rs,k);
    else return calc(querysuf(ls,k-tr[pos].mid.l),tr[pos].mid);
  }
  void pushup(int pos){
    int ls=tr[pos].tr[0],rs=tr[pos].tr[1];
    tr[pos].sz=tr[ls].sz+tr[rs].sz,tr[pos].l=tr[ls].l,tr[pos].r=tr[rs].r;
    if(tr[ls].r.l<tr[rs].l.l)tr[pos].mid=querysuf(rs,tr[rs].l.l-tr[ls].r.l),tr[pos].l=calc(tr[pos].l,tr[pos].mid);
    else tr[pos].mid=querypre(ls,tr[ls].r.l-tr[rs].l.l),tr[pos].r=calc(tr[pos].mid,tr[pos].r);
  }
  void build(int&pos,int nl,int nr,bool a[],unsigned int b[]){
    pos=newnode();
    if(nl==nr){
      tr[pos].sz=1,tr[pos].type=a[nl];
      if(a[nl])tr[pos].r=info(1,-1u,~b[nl],b[nl]);
      else tr[pos].l=info(1,-1u,~b[nl],b[nl]);
    }
    else{
      int mid=(nl+nr)>>1;
      build(tr[pos].tr[0],nl,mid,a,b),build(tr[pos].tr[1],mid+1,nr,a,b),pushup(pos);
    }
  }
  int merge(int a,int b){
    if(!a||!b)return a^b;
    if(tr[b].sz<(tr[a].sz+tr[b].sz)>>2){
      int x=tr[a].tr[0],y=tr[a].tr[1],z,w;
      if(tr[x].sz>=(tr[a].sz+tr[b].sz)>>2)return tr[a].tr[1]=merge(y,b),pushup(a),a;
      else return z=tr[y].tr[0],w=tr[y].tr[1],st[++top]=a,st[++top]=y,merge(merge(x,z),merge(w,b));  
    }
    else if(tr[a].sz<(tr[a].sz+tr[b].sz)>>2){
      int x=tr[b].tr[1],y=tr[b].tr[0],z,w;
      if(tr[x].sz>=(tr[a].sz+tr[b].sz)>>2)return tr[b].tr[0]=merge(a,y),pushup(b),b;
      else return z=tr[y].tr[1],w=tr[y].tr[0],st[++top]=b,st[++top]=y,merge(merge(a,w),merge(z,x));  
    }
    int pos=newnode();
    return tr[pos].tr[0]=a,tr[pos].tr[1]=b,pushup(pos),pos;
  }
  void split(int pos,int k,int&a,int&b){
    if(!tr[pos].tr[0]){
      if(k)a=pos,b=0;
      else a=0,b=pos;
      return;
    }
    st[++top]=pos;
    if(tr[tr[pos].tr[0]].sz<k)split(tr[pos].tr[1],k-tr[tr[pos].tr[0]].sz,a,b),a=merge(tr[pos].tr[0],a);
    else split(tr[pos].tr[0],k,a,b),b=merge(b,tr[pos].tr[1]);
  }
  void modify(int pos,int x,unsigned int k){
    if(!tr[pos].tr[0]){
      tr[pos].type^=1;
      if(tr[pos].type)tr[pos].l=info(),tr[pos].r=info(1,-1u,~k,k);
      else tr[pos].l=info(1,-1u,~k,k),tr[pos].r=info();
      return;
    }
    if(x<=tr[tr[pos].tr[0]].sz)modify(tr[pos].tr[0],x,k);
    else modify(tr[pos].tr[1],x-tr[tr[pos].tr[0]].sz,k);
    pushup(pos);
  }
  unsigned int query(int&rt,int l,int r,int a=0,int b=0,int c=0){
    info ans;
    return split(rt,l-1,a,b),split(b,r-l+1,b,c)，ans=calc(tr[b].l,tr[b].r),rt=merge(merge(a,b),c),ans.f1^ans.maxn;
  }
};
WBLT<4000005>t;
int main(){
  in(n,m);
  for(int i=1;i<=n;i++)in(a[i],b[i]);
  t.build(rt,1,n,a,b);
  for(int i=1,opt,l,r;i<=m;i++){
    in(opt);
    if(opt==1)in(l,y),t.modify(rt,l,y);
    else if(opt==2)in(l,r),cout<<t.query(rt,l,r)<<'\n';
    else if(opt==3){
      int a,b,c;
      in(l,r),t.split(rt,l-1,a,b),t.split(b,r-l+1,b,c),rt=t.merge(t.merge(a,c),b);
    }
  }
  return 0;
}