[DS记录]P5111 zhtobu3232的线段树

**题意** ： 给定一棵区间 $[0,n)$ 生成的线段树。 给出 $m$ 个区间 $[l,r)$ ，将这些区间在线段树上拆分得到的节点打上标记。 求有多少个 $[l,r)$ 满足 $0\leq l<r\leq n$ 且在线段树上拆分得到的节点都没有标记。 答案对 $998244353$ 取模。 $n\leq 10^{14},m\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 首先使用动态开点线段树将所有被标记的点求出。时空复杂度为 $O(m\log n)$。 观察怎样的区间 $[L,R)$ 才会拆分到节点 $[l,r)$。 记节点 $[l,r)$ 的父亲为节点 $[l',r')$ ，则充要条件为 $[L,R)\supseteq [l,r)$ 且 $[L,R)\nsupseteq [l',r')$。 观察这个集合的形状，将其画到二维平面上，如图 ：  最终不合法的部分会是形如图片右侧的若干矩形的并集。 可以用扫描线求出这个并集大小，复杂度为 $O(m\log^2n)$。 然而这个做法还有很多性质没有利用，在平面上进一步观察性质是可行的，但是太累。我们换种做法。 对于节点 $u=[l,r)$ ： - 记 $pre[u]$ 表示有多少个 $i$ 使得 $[l,i)$ 的拆分是好的。 - 记 $suf[u]$ 表示有多少个 $i$ 使得 $[i,r)$ 的拆分是好的。 边界 ： - 若该节点子树内无标记，则 $pre[u]=suf[u]=r-l$ ，答案加上 $(r-l+1)(r-l)/2$。 - 若该节点为有标记的叶节点，则 $pre[u]=suf[u]=0$。 对于其余情况，计算所有跨过中点的 $u$ 的子区间的贡献，则为 $suf[{\rm lson}]\times pre[{\rm rson}]$。 然而这里有个特殊情况，区间 $[l,r)$ 只会恰好拆分到节点 $u$ （我们错误地将其拆成 ${\rm lson},{\rm rson}$），需要单独计算。 - 若 $u$ 有标记，且 ${\rm lson},{\rm rson}$ 均无标记，则 $[l,r)$ 是不合法的却算成了合法的，答案减一。 - 若 $u$ 无标记，且 ${\rm lson},{\rm rson}$ 某一个有标记，则 $[l,r)$ 是合法的却算成了不合法的，答案加一。 接下来看 $pre,suf$ 的计算方法，只介绍 $pre$ ，$suf$ 同理。 首先， ${\rm lson}$ 的 $pre[{\rm lson}]$ 个区间一定是可行的。 若 ${\rm lson}$ 没有标记，那么 ${\rm rson}$ 的 $pre[{\rm rson}]$ 个区间也是可行的，否则都不可行。 同样需要特殊考虑 $[l,r)$。具体实现见代码。 复杂度 $O(m\log n)$。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxM 100500 using namespace std; const int mod=998244353; struct Node{bool fl;int l,r;ll pre,suf;}a[MaxM*105]; int tn;ll wfl,wfr; void add(ll l,ll r,int &u) { if (!u)u=++tn; if (wfl<=l&&r<=wfr){a[u].fl=1;return ;} ll mid=(l+r)>>1; if (wfl<mid)add(l,mid,a[u].l); if (mid<wfr)add(mid,r,a[u].r); } int ans; void dfs(ll l,ll r,int u) { if (!u){ans=(ans+((r-l+1)%(mod*2))*((r-l)%(mod*2))/2)%mod;return ;} if (l+1==r){ans+=(a[u].pre=a[u].suf=!a[u].fl);return ;} ll mid=(l+r)>>1; dfs(l,mid,a[u].l);dfs(mid,r,a[u].r); ll sl=a[u].l ? a[a[u].l].suf : mid-l ,pl=a[u].l ? a[a[u].l].pre : mid-l ,sr=a[u].r ? a[a[u].r].suf : r-mid ,pr=a[u].r ? a[a[u].r].pre : r-mid; ans=(ans+(sl%mod)*(pr%mod))%mod; int fl=0; if (!a[a[u].l].fl&&!a[a[u].r].fl&&a[u].fl)fl=-1; if ((a[a[u].l].fl||a[a[u].r].fl)&&!a[u].fl)fl=1; ans+=fl; a[u].pre=pl+(a[a[u].l].fl ? 0 : pr)+fl; a[u].suf=sr+(a[a[u].r].fl ? 0 : sl)+fl; } ll n;int m; int main() { scanf("%lld%d",&n,&m); int rt=0; for (int i=1;i<=m;i++){ scanf("%lld%lld",&wfl,&wfr);wfl--; add(0,n,rt); }dfs(0,n,rt); printf("%d",(ans+mod)%mod); return 0; } ```