题解 P5111 【zhtobu3232的线段树】
mrsrz
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：
```cpp
#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;
}
```