P10120 『STA - R4』冰红茶

Genius_Star · 2024-02-02 09:34:29 · 题解

思路：

考虑线段树维护：

每次操作 1 时：

• 将 [l,r] 区间内喝“热带风味冰红茶”最后连续喝的数量覆盖为 0。

• 将 [l,r] 区间内喝“原味冰红茶”最后连续喝的数量增加 k。

• 将 [1,l-1] 区间内喝“原味冰红茶”最后连续喝的数量覆盖为 0。

• 将 [r+1,n] 区间内喝“原味冰红茶”最后连续喝的数量覆盖为 0。

• 将 [1,l-1] 区间内喝“热带风味冰红茶”最后连续喝的数量增加 k。

• 将 [r+1,n] 区间内喝“热带风味冰红茶”最后连续喝的数量增加 k。

每次操作 2 时：

• 如果 [l,r] 的 sum 为 0（即都死完了），退出。

• 如果 [l,r] 的 \max(Max_1,Max_2)<k，则这个区间最大的都没有连续喝 k 瓶相同口味的冰红茶，退出。

• 否则线段树一直分，跳到单点为止，直接修改。

每次操作 3 时：

• 输出 root 的 sum 即可。

时间复杂度 O(n \log n)。

常数略大，谨慎使用。

提交记录 666ms。

细节：

对于区间覆盖标记 tag_1 和 tag_2，下传时也要将儿子的 tag_3 和 tag_4 两个加法标记给清空。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll N=200200;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
ll n,q,op,l,r,v;
struct Node{
    ll l,r;
    ll sum;
    ll Max1,Max2;
    ll tag1,tag2;
    ll tag3,tag4;
}X[N<<2];
void pushup(ll k){
    X[k].sum=X[k<<1].sum+X[k<<1|1].sum;
    X[k].Max1=max(X[k<<1].Max1,X[k<<1|1].Max1);
    X[k].Max2=max(X[k<<1].Max2,X[k<<1|1].Max2);
}
void push_down(ll k){
    if(X[k].tag1!=-1){
        X[k<<1].tag3=X[k<<1|1].tag3=0;
        X[k<<1].tag1=X[k<<1|1].tag1=X[k].tag1;
        X[k<<1].Max1=X[k<<1|1].Max1=X[k].tag1;
        X[k].tag1=-1;
    }
    if(X[k].tag2!=-1){
        X[k<<1].tag4=X[k<<1|1].tag4=0;
        X[k<<1].tag2=X[k<<1|1].tag2=X[k].tag2;
        X[k<<1].Max2=X[k<<1|1].Max2=X[k].tag2;
        X[k].tag2=-1;
    }
    if(X[k].tag3){
        X[k<<1].tag3+=X[k].tag3;
        X[k<<1|1].tag3+=X[k].tag3;
        X[k<<1].Max1+=X[k].tag3;
        X[k<<1|1].Max1+=X[k].tag3;
        X[k].tag3=0;
    }
    if(X[k].tag4){
        X[k<<1].tag4+=X[k].tag4;
        X[k<<1|1].tag4+=X[k].tag4;
        X[k<<1].Max2+=X[k].tag4;
        X[k<<1|1].Max2+=X[k].tag4;
        X[k].tag4=0;        
    }
}
void build(ll k,ll l,ll r){
    X[k].l=l,X[k].r=r;
    X[k].tag1=X[k].tag2=-1;
    if(l==r){
        X[k].sum=1;
        return ;
    }
    ll mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    pushup(k);
}
void updata1(ll k,ll l,ll r,ll v){
    if(r<l)
      return ;
    if(X[k].l==l&&r==X[k].r){
        X[k].tag3=0;
        X[k].tag1=X[k].Max1=v;
        return ;
    }
    push_down(k);
    ll mid=(X[k].l+X[k].r)>>1;
    if(r<=mid)
      updata1(k<<1,l,r,v);
    else if(l>mid)
      updata1(k<<1|1,l,r,v);
    else{
        updata1(k<<1,l,mid,v);
        updata1(k<<1|1,mid+1,r,v);
    }
    pushup(k);
}
void updata2(ll k,ll l,ll r,ll v){
    if(r<l)
      return ;
    if(X[k].l==l&&r==X[k].r){
        X[k].tag4=0;
        X[k].tag2=X[k].Max2=v;
        return ;
    }
    push_down(k);
    ll mid=(X[k].l+X[k].r)>>1;
    if(r<=mid)
      updata2(k<<1,l,r,v);
    else if(l>mid)
      updata2(k<<1|1,l,r,v);
    else{
        updata2(k<<1,l,mid,v);
        updata2(k<<1|1,mid+1,r,v);
    }
    pushup(k);
}
void updata3(ll k,ll l,ll r,ll v){
    if(r<l)
      return ;
    if(X[k].l==l&&r==X[k].r){
        X[k].tag3+=v; 
        X[k].Max1+=v;
        return ;
    }
    push_down(k);
    ll mid=(X[k].l+X[k].r)>>1;
    if(r<=mid)
      updata3(k<<1,l,r,v);
    else if(l>mid)
      updata3(k<<1|1,l,r,v);
    else{
        updata3(k<<1,l,mid,v);
        updata3(k<<1|1,mid+1,r,v);
    }
    pushup(k);
}
void updata4(ll k,ll l,ll r,ll v){
    if(r<l)
      return ;
    if(X[k].l==l&&r==X[k].r){
        X[k].tag4+=v; 
        X[k].Max2+=v;
        return ;
    }
    push_down(k);
    ll mid=(X[k].l+X[k].r)>>1;
    if(r<=mid)
      updata4(k<<1,l,r,v);
    else if(l>mid)
      updata4(k<<1|1,l,r,v);
    else{
        updata4(k<<1,l,mid,v);
        updata4(k<<1|1,mid+1,r,v);
    }
    pushup(k);
}
void Find(ll k,ll l,ll r,ll v){
    if(max(X[k].Max1,X[k].Max2)<v||!X[k].sum)
      return ;
    if(X[k].l==X[k].r){
        X[k].sum=0;
        return ;
    }
    push_down(k);
    ll mid=(X[k].l+X[k].r)>>1;
    if(r<=mid)
      Find(k<<1,l,r,v);
    else if(l>mid)
      Find(k<<1|1,l,r,v);
    else{
        Find(k<<1,l,mid,v);
        Find(k<<1|1,mid+1,r,v);
    }
    pushup(k);
}
int main(){
//  freopen("A.in","r",stdin);
    n=read(),q=read();
    build(1,1,n);
    while(q--){
        op=read();
        if(op==1){
            l=read(),r=read(),v=read();
            updata2(1,l,r,0);
            updata1(1,1,l-1,0);
            updata1(1,r+1,n,0);
            updata3(1,l,r,v);
            updata4(1,1,l-1,v);
            updata4(1,r+1,n,v);
        }
        else if(op==2){
            l=read(),r=read(),v=read();
            Find(1,l,r,v);
        }
        else{
            write(X[1].sum);
            putchar('\n');
        }
    }
    return 0;
}