洛谷 5111 zhtobu3232 的线段树

让我想起了一道十分有趣的 ZJOI 题呢~

问题相当于是给定一棵线段树，其中某些结点有标记，统计不用标记的结点能拼出的区间数。
（并不能把一个结点拆成左右儿子用）

这种东西既然是在线段树上做，那么显然要维护可以拼出的前后缀数。
那么一个结点的贡献应该为左儿子的后缀数乘右儿子的前缀数。
然后注意去掉或补上一些这个方式会忽略的情况。

还是比较简单的题？
动态开点，如果某个点是空的那么贡献直接为 (len+12)，len 是长度。
注意空点也要记可以拼出的前后缀数（都等于 len）。

代码：

#include <cstdio>
using namespace std;
const long long N = 1e14;
const int M = 1e5;
const int mod = 998244353;
const int inv = 499122177;
long long n;
int m;
struct node
{
    int tag;
    int suf,pre;
    int ls,rs;
} seg[250 * M + 10];
int rt,seg_tot;
void update(long long l,long long r,int &p,long long tl,long long tr)
{
    int &tot = seg_tot;
    !p && (p = ++tot);
    if(l <= tl && tr <= r)
    {
        seg[p].tag = 1;
        return ;
    }
    long long mid = tl + tr >> 1;
    l < mid && (update(l,r,seg[p].ls,tl,mid),1);
    r > mid && (update(l,r,seg[p].rs,mid,tr),1);
}
int query(int &p,long long tl,long long tr)
{
    int &tot = seg_tot;
    if(tl + 1 == tr)
        return (seg[p].suf = seg[p].pre = !seg[p].tag);
    if(!p)
    {
        p = ++tot,seg[p].suf = seg[p].pre = (tr - tl) % mod;
        return (long long)((tr - tl) % mod) * ((tr - tl + 1) % mod) % mod * inv % mod;
    }
    long long mid = tl + tr >> 1;
    int ret = 0;
    ret = (ret + query(seg[p].ls,tl,mid)) % mod,
    ret = (ret + query(seg[p].rs,mid,tr)) % mod,
    ret = (ret + (long long)seg[seg[p].ls].suf * seg[seg[p].rs].pre % mod) % mod,
    ret = (ret - (seg[p].tag && !seg[seg[p].ls].tag && !seg[seg[p].rs].tag) + mod) % mod,
    ret = (ret + (!seg[p].tag && (seg[seg[p].ls].tag || seg[seg[p].rs].tag))) % mod,
    seg[p].pre = (seg[seg[p].ls].pre + (!seg[seg[p].ls].tag) * (seg[seg[p].rs].pre - !seg[seg[p].rs].tag + mod) % mod + !seg[p].tag) % mod,
    seg[p].suf = (seg[seg[p].rs].suf + (!seg[seg[p].rs].tag) * (seg[seg[p].ls].suf - !seg[seg[p].ls].tag + mod) % mod + !seg[p].tag) % mod;
    return ret;
}
int main()
{
    scanf("%lld%d",&n,&m);
    for(long long l,r;m;--m)
        scanf("%lld%lld",&l,&r),update(--l,r,rt,0,n);
    printf("%d\n",query(rt,0,n));
}