题解归档 - cf915E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf915E
• 本地来源：problems/cf915E/idea.md
• 题目链接：https://codeforces.com/contest/915/problem/E
• 原始标题：CF915E Physical Education Lessons

思路

CF915E Physical Education Lessons

Catalog：Segment Tree Beats · lib_target: 数据结构(线段树beats).cpp

题意

$n$ 天（初始均为工作日），$q$ 次操作：将 $[l,r]$ 整体赋值为 非工作日（$k=1$）或工作日（$k=2$），覆盖历史状态。每次操作后输出当前工作日总数。

$n \le 10^9$，$q \le 3\cdot 10^5$。

做法

坐标压缩

值域 $10^9$ 不能直接建树。收集所有 $l$、$r+1$ 以及 $1,n+1$，排序去重后得到至多 $2q+2$ 个断点。相邻断点之间是一段长度可能 $>1$ 的同质区间，线段树维护区间上的赋值与区间和（和 = 赋值 $\times$ 长度）。

区间 $i$ 对应天数 $[xs[i],\, xs[i+1]-1]$。查询 $[l,r]$ 映射为树上下标：

• L = lower_bound(xs, l)
• R = lower_bound(xs, r+1) - 1

本题实现：赋值懒标记线段树

$k\in\{0,1\}$ 的区间赋值 + 全局和，用 lazy=-1/0/1 的线段树即可，$O(q\log q)$。覆盖时须同时写 sum=val*len；勿每轮对根全树 pushdown（会 TLE）。

Catalog 关联：Segment Tree Beats

同一题也可用 beats 维护 $0/1$ 数组：非工作日 chmin(0)，工作日 chmax(1)，利用 beats 在「区间最小值/最大值」上的摊还 $O(\log n)$ 更新。通用 beats 模板见 lib/数据结构(线段树beats).cpp（维护 mx/mx2/cmx 与 mn/mn2/cmn，支持区间 chmin/chmax + 区间和）。

注意：beats 版坐标下标须与 build(1, xlen-1) 一致；右端点用 lbpos(r+1)-1 而非 lbpos(r)。

复杂度

• 时间：$O(q\log q)$
• 空间：$O(q)$

对拍

brute.cpp 直接模拟数组；gen.cpp 随机 $n\le 200,\, q\le 80$。stress.py -n 500 通过。

代码

来源：problems/cf915E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:50:50
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1200005;
ll n,q,i,j,k,l,r,zc,pd,cur,dq,cnt,ans,xlen;
ll xs[maxn+5],ql[maxn+5],qr[maxn+5],qk[maxn+5];
struct tnode{
    ll l,r,len,sum,lazy;
};
tnode t[4*maxn+5];
ll lbpos(ll x){
    return lower_bound(xs+1,xs+xlen+1,x)-xs;
}
void pushdown(ll root){
    if(t[root].lazy==-1) return;
    t[root].sum=t[root].lazy*t[root].len;
    if(t[root].l!=t[root].r){
        t[root*2].lazy=t[root].lazy;
        t[root*2+1].lazy=t[root].lazy;
    }
    t[root].lazy=-1;
}
void pushup(ll root){
    pushdown(root*2),pushdown(root*2+1);
    t[root].sum=t[root*2].sum+t[root*2+1].sum;
    t[root].len=t[root*2].len+t[root*2+1].len;
}
void build(ll root,ll l,ll r){
    t[root].l=l,t[root].r=r;
    t[root].lazy=-1;
    if(l==r){
        t[root].len=xs[l+1]-xs[l];
        t[root].sum=t[root].len;
    }
    else{
        ll mid=(l+r)/2;
        build(root*2,l,mid),build(root*2+1,mid+1,r);
        pushup(root);
    }
}
void tset(ll root,ll l,ll r,ll val){
    pushdown(root);
    if(l==t[root].l and r==t[root].r){
        t[root].lazy=val;
        t[root].sum=val*t[root].len;
        return;
    }
    ll mid=(t[root].l+t[root].r)/2;
    if(r<=mid) tset(root*2,l,r,val);
    else{
        if(l>mid) tset(root*2+1,l,r,val);
        else tset(root*2,l,mid,val),tset(root*2+1,mid+1,r,val);
    }
    pushup(root);
}
int main(){
    cin>>n>>q;
    xlen=0;
    xs[++xlen]=1;
    xs[++xlen]=n+1;
    for(i=1;i<=q;i++){
        cin>>ql[i]>>qr[i]>>qk[i];
        xs[++xlen]=ql[i];
        xs[++xlen]=qr[i]+1;
    }
    sort(xs+1,xs+xlen+1);
    j=1;
    for(i=2;i<=xlen;i++) if(xs[i]!=xs[j]) xs[++j]=xs[i];
    xlen=j;
    build(1,1,xlen-1);
    for(i=1;i<=q;i++){
        l=lbpos(ql[i]);
        r=lbpos(qr[i]+1)-1;
        tset(1,l,r,qk[i]-1);
        cout<<t[1].sum<<"\n";
    }
    return 0;
}