20231025

CF1572F Stations 题解-Segment Tree Beats

吉司机线段树好题！！！CF3400。
传送门

Statement

有 \(n\) 个广播站，第 \(i\) 个广播站高度为 \(h_i\)，范围为 \(w_i\)。初始 \(h_i=0,w_i=i\)。广播站 \(i\) 能向广播站 \(j\) 传递消息，当且仅当 \(i\le j\le w_i\)，且 \(h_i>\max\limits_{k=i+1}^jh_k\)。定义 \(b_i\) 表示能向 \(i\) 传播消息的广播站数量。
接下来有 \(q\) 次操作，分为以下两种类型：

• 给出 \(i,g\)，把 \(h_i\) 变成所有广播站中严格最高的，并且 \(w_i\gets g\)。
• 给出 \(l,r\)，查询 \(\sum_{i=l}^rb_i\)。

\(1\le n,q\le2\times10^5\)。

Solution

看题后感觉毫无思路，

\(b_i\) 是非常难维护的，于是我们考虑先维护 \(w_i\)。

发现每一次变成最高的操作就是对于 \(i\) 单点修改，

再把 \(1 \sim i-1\) 区间内的所有 \(w_i\) 的值与 \(i-1\) 取 \(\min\) ，

这个操作可以直接用吉司机线段树维护。

而再来考虑如何处理 \(b_i\) ，对于每一次修改，

发现我们每次取 \(\min\) 的时候是把 \([i,mx]\) 区间内的 \(b_i\) 减去 \(cnt_{mx}\) ，

于是这个操作可以再用一棵线段树维护即可。

思路非常妙啊，在不好直接维护答案时我们考虑再维护一维。

实现比较简单，也没有什么细节，就差不多时两个模板和一块儿了。

直接一发过了~

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll inf=2e9;
const int N=2e5+5;
int n,q;

namespace SGT{
  struct sgt{
  	ll sum,tag;
  }tr[N<<2];
  
  #define mid ((l+r)>>1)
  #define lc p<<1
  #define rc p<<1|1
  #define lson l,mid,lc
  #define rson mid+1,r,rc
  
  void pu(int p){tr[p].sum=tr[lc].sum+tr[rc].sum;}
  
  void pd(int l,int r,int p){
  	if(!tr[p].tag) return; 
  	tr[lc].sum+=1ll*(mid-l+1)*tr[p].tag;
  	tr[rc].sum+=1ll*(r-mid)*tr[p].tag;
  	tr[lc].tag+=tr[p].tag;
  	tr[rc].tag+=tr[p].tag;
  	tr[p].tag=0;
  }
  
  void update(int l,int r,int p,int x,int y,ll val){
  	if(x>y) return;
  	//cout<<"SGT::update:"<<l<<' '<<r<<' '<<p<<' '<<x<<' '<<y<<' '<<val<<endl;
  	if(x<=l&&y>=r){
  	  tr[p].sum+=1ll*(r-l+1)*val;
	  tr[p].tag+=val;
	  return;	
	}
	pd(l,r,p);
	if(x<=mid) update(lson,x,y,val);
	if(y>mid) update(rson,x,y,val);
	pu(p);
  }
  
  ll query(int l,int r,int p,int x,int y){
    if(x<=l&&y>=r) return tr[p].sum;
    pd(l,r,p);
    ll res=0;
    if(x<=mid) res+=query(lson,x,y);
    if(y>mid) res+=query(rson,x,y);
    return res;
  }
  
  void build(int l,int r,int p){
    if(l==r){
      tr[p].sum=1;
      tr[p].tag=0;
      return;
	}
	build(lson);build(rson);
	pu(p);
  } 
  
  #undef mid
  #undef lc
  #undef rc
  #undef lson
  #undef rson
}

namespace STB{
  struct sgt{
    int mx,se,tag1,tag2,cnt;
  }tr[N<<2];
  #define mid ((l+r)>>1)
  #define lson l,mid,p<<1
  #define rson mid+1,r,p<<1|1
  #define lc p<<1
  #define rc p<<1|1
  
  void pu(int p){
  	tr[p].mx=max(tr[lc].mx,tr[rc].mx);
  	if(tr[lc].mx==tr[rc].mx){
  	  tr[p].se=max(tr[lc].se,tr[rc].se);
	  tr[p].cnt=tr[lc].cnt+tr[rc].cnt;	
	}
	else if(tr[lc].mx>tr[rc].mx){
	  tr[p].se=max(tr[lc].se,tr[rc].mx);
	  tr[p].cnt=tr[lc].cnt;
	}
	else{
	  tr[p].se=max(tr[lc].mx,tr[rc].se);
	  tr[p].cnt=tr[rc].cnt;
	}
  }
  
  void change(int p,int tag1,int tag2){
	tr[p].mx+=tag1;
  	tr[p].tag1+=tag1;
  	if(tr[p].se!=-inf) tr[p].se+=tag2;
  	tr[p].tag2+=tag2;
  }
  
  void pd(int p){
    if(!tr[p].tag1&&!tr[p].tag2) return;
    int mx=max(tr[lc].mx,tr[rc].mx);
    if(tr[lc].mx==mx) change(lc,tr[p].tag1,tr[p].tag2);
    else change(lc,tr[p].tag2,tr[p].tag2);
    if(tr[rc].mx==mx) change(rc,tr[p].tag1,tr[p].tag2);
    else change(rc,tr[p].tag2,tr[p].tag2);
    tr[p].tag1=tr[p].tag2=0;
  }
  
  void update(int l,int r,int p,int x,int val){
  	if(l==r){
  	  val=val-tr[p].mx;
  	  if(val>0) SGT::update(1,n,1,tr[p].mx+1,tr[p].mx+val,1);
  	  else SGT::update(1,n,1,tr[p].mx+val+1,tr[p].mx,-1);
  	  tr[p].mx+=val;
	  return;	
	}
	pd(p);
	if(x<=mid) update(lson,x,val);
	else update(rson,x,val);
	pu(p);
  }
  
  void cover(int l,int r,int p,int x,int y,int val){
  	if(l>r||x>y||l>y||r<x||tr[p].mx<=val) return;
  	if(x<=l&&y>=r&&tr[p].mx>val&&tr[p].se<val){
  	  int k=tr[p].mx-val;
	  SGT::update(1,n,1,val+1,tr[p].mx,-tr[p].cnt);
	  tr[p].mx-=k;
	  tr[p].tag1-=k;
	  return;	
	}
	pd(p);
	if(x<=mid) cover(lson,x,y,val);
	if(y>mid) cover(rson,x,y,val);
	pu(p);
  }
  
  void build(int l,int r,int p){
  	if(l==r){
  	  tr[p].mx=l;
	  tr[p].se=-inf;
	  tr[p].tag1=tr[p].tag2=0;
	  tr[p].cnt=1;
	  return;	
	}
	build(lson);build(rson);
	pu(p);
  }
  
  #undef mid
  #undef lson
  #undef rson
  #undef lc
  #undef rc
}

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void print(ll x){
  int p[25],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x){
  	p[++tmp]=x%10;
  	x/=10;
  }
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar('\n');
}

int main(){
  /*2023.10.25 H_W_Y CF1572F Stations Segment Tree Beats*/
  n=read();q=read();
  STB::build(1,n,1);SGT::build(1,n,1);
  for(int i=1;i<=q;i++){
  	int op=read(),l=read(),r=read();
  	if(op==1){
  	  STB::update(1,n,1,l,r);
	  STB::cover(1,n,1,1,l-1,l-1);	
	}
	else print(SGT::query(1,n,1,l,r));
  }
  return 0;
}

Conclusion

线段树维护时我们可以先考虑如何维护修改，再将询问和修改的关系找到，用两棵线段树维护。