让我想起了一道十分有趣的 ZJOI 题呢~
问题相当于是给定一棵线段树，其中某些结点有标记，统计不用标记的结点能拼出的区间数。
（并不能把一个结点拆成左右儿子用）
这种东西既然是在线段树上做，那么显然要维护可以拼出的前后缀数。
那么一个结点的贡献应该为左儿子的后缀数乘右儿子的前缀数。
然后注意去掉或补上一些这个方式会忽略的情况。
还是比较简单的题？
动态开点，如果某个点是空的那么贡献直接为 \(\binom{\mathrm{len}+1}{2}\)，\(\mathrm{len}\) 是长度。
注意空点也要记可以拼出的前后缀数（都等于 \(\mathrm{len}\)）。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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));
}