自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:07:16，当前版本为作者最后更新于2018-12-23 10:03:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这线段树的写法不怎么优美啊QAQ

以下讨论都是按照题目上的左开右闭线段树来的。

线段树上分治。

首先按照题意模拟，把该删的节点都打上删除标记。动态开点，时间复杂度$O(m\log n)$。

然后在线段树上分治。

令$pre[x]$表示节点$x$表示的区间$(l,r]$中，有多少个$i$使得区间$(l,i]$满足条件。

$suf[x]$表示节点$x$表示的区间$(l,r]$中，有多少个$i$使得区间$(i,r]$满足条件。

$ls[x],rs[x]$分别表示节点$x$的左、右儿子。

按顺序访问每个节点$x$，先考虑如下特殊情况。

1. 若该节点是叶子，且没被删除，则$pre[x]=suf[x]=1$，答案加1。
2. 若该节点是叶子，且被删除了，则$pre[x]=suf[x]=0$，答案减1。
3. 若该节点没被开辟，则节点内的区间任选，答案加$\frac{(r-l+1)(r-l)}{2}$，$pre[x]=suf[x]=r-l$。

对于一般情况，该区间内的贡献就是$pre[ls[x]]\times suf[rs[x]]$。

还有一些特殊情况：

1. 若$x$被删除且$ls[x],rs[x]$均未被删除，则统计答案的时候，$(l,r]$被统计进去了，实际应该不符合条件，因此答案要减1。
2. 若$x$没被删除且$ls[x],rs[x]$中有节点被删除，则统计答案的时候，$(l,r]$没被统计，实际是符合条件的，因此答案要加1。

接下来计算节点$x$的$pre$和$suf$，这里只考虑$pre$。

$ls[x]$的$pre[ls[x]]$个区间一定是可行的。

$rs[x]$的$pre[rs[x]$个区间可行，必须满足$ls[x]$没被删除（因为要补上区间$(l,mid]$）。

若$ls[x]$和$rs[x]$均未被删除，则$(l,r]$区间被计算进去了，先减去这个区间的1。

再单独考虑$x$是否被删除，看是否要加上$(l,r]$区间即可。

于是就有了代码注释中的那个转移。

$suf$则反过来同样方法考虑即可。

这部分的时间复杂度也是$O(m\log n)$的，所以总时间复杂度$O(m\log n)$。

线段树空间开大点即可。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;using std::max;
typedef long long LL;
const int md=998244353,N=201*100000;
int ls[N],rs[N],rt;
bool del[N];
LL n;int pre[N],suf[N];int m,node=0,ans=0;
//pre每个节点前缀可行区间个数，suf后缀 
void split(int&o,LL l,LL r,const LL&L,const LL&R){
    if(!o)o=++node;
    if(L==l&&r==R)del[o]=1;else{
        const LL mid=l+r>>1;
        if(L<mid)split(ls[o],l,mid,L,min(R,mid));
        if(mid<R)split(rs[o],mid,r,max(L,mid),R);
    }
}
inline int CC(LL x){return(x*(x+1)>>1)%md;}
inline void upd(int&x){x+=x>>31&md;}
void query(int&o,LL l,LL r){
    if(l+1==r){//底层 
        ans+=(suf[o]=pre[o]=!del[o]);
        if(ans>=md)ans-=md;
        return;
    }
    if(!o){//没被访问 
        o=++node;
        pre[o]=suf[o]=(r-l)%md;
        upd(ans+=CC((r-l)%md)-md);
        return;
    }
    const LL mid=l+r>>1;
    query(ls[o],l,mid);
    query(rs[o],mid,r);
    upd(ans+=1LL*suf[ls[o]]*pre[rs[o]]%md-md);
    if(del[o]&&!del[ls[o]]&&!del[rs[o]])upd(--ans);//自己被删除，两个儿子没被删除
    if(!del[o]&&(del[ls[o]]||del[rs[o]]))upd(ans=ans+1-md);//自己没被删除，两个儿子至少一个被删除 
    upd(pre[o]=(pre[ls[o]]+!del[o]+(!del[ls[o]])*(pre[rs[o]]-!del[rs[o]]))-md);//前缀=左边的前缀+[整个节点是否可行]+[左边整个节点是否可行]*(右边的前缀-[右边整个节点是否可行]) 
    upd(suf[o]=(suf[rs[o]]+!del[o]+(!del[rs[o]])*(suf[ls[o]]-!del[ls[o]]))-md);//同理 
}
int main(){
    scanf("%lld%d",&n,&m);
    while(m--){
        LL l,r;
        scanf("%lld%lld",&l,&r);
        split(rt,0,n,l-1,r);
    }
    query(rt,0,n);
    printf("%d\n",ans);
    return 0;
}