纪念一下场切题。
题意：给定一棵（分点不一定为中点）的线段树，给定若干个询问区间，问有多少个线段树上结点的集合，知道了这些结点对应的区间和就可以知道任何一个询问区间的和。
从询问区间开始考虑。会发现可以把所有 \(a_i\) 分成若干个集合，只要知道每个集合的和就可以知道所有询问区间的和。具体地，“被覆盖情况”相同的 \(a_i\) 是在同一个集合中的。特别的，可能有一些 \(a_i\) 没有被任何询问区间覆盖，这些 \(a_i\) 分到一个集合，它们的和可以不用求出。这个集合具体的分法可以用一个哈希处理，给每个区间赋一个权值，区间中每个点加上这个权值，就可以认为权值相同的点属于一个集合。
再考虑到线段树上的区间。可以认为我们标记了一些节点，知道了它们对应区间的和。同样的，通过上面的分类方法可以把所有 \(a_i\) 拆成若干个集合，知道了每个集合的和（以及有一个集合不知道）。进一步地，利用这个树形结构，会发现“祖先中自下而上第一个标记结点”相同的 \(a_i\) 是分在同一个集合里的。
考虑两组分类的关系。我们需要满足询问，所以第一种分类方式中不同集合的两个 \(a_i\) 在第二种分类方式中不能分在同一集合。也就是说第一组集合进一步拆分得到了第二组集合。容易发现这个条件是充要的。
下面来考虑一下特殊性质。特殊性质相当于第一种分类方式有 \(n\) 个集合 \(\{1\},\{2\},\cdots,\{n\}\)，它们的和都需要知道。从刚才说明的第二种分类的判断方法入手，考虑做一个树形 DP，自下而上确定。根据刚才的充要条件，对某个点 \(u\)，确定了它的子树的选择情况后，子树内的所有 \(a_i\) 至多有一个的分类（即第一个祖先）还没有确定。 那么就可以设 \(f_u\) 表示子树 \(u\) 内所有 \(a_i\) 的分类都确定的方案数，\(g_u\) 表示子树 \(u\) 内有一个 \(a_i\) 的分类还没有确定的方案数。设 \(u\) 的左右儿子分别为 \(ls,rs\)，有
\[f_{u}=2f_{ls}f_{rs}+f_{ls}g_{rs}+g_{ls}f_{rs} \]\[g_{u}=f_{ls}g_{rs}+g_{ls}f_{rs} \]初始值是对于叶子结点 \(v\)，\(f_v=g_v=1\)。答案是 \(f_{1}\)。这样就可以通过特殊性质。
再来处理一般情况。容易把刚才的性质推广：一棵子树完全确定后，至多有一类结点的分类（第一个祖先）还没有确定。那么就可以设计一个二维DP：\(dp_{u,i}\) 表示子树 \(u\) 内的方案确定后，第 \(i\) 个集合的点的分类还没有确定。特别地，\(i=0\) 表示都已经确定，\(i=1\) 表示这一类的和可以不用求，也就是它们可以没有“第一个标记的祖先”。转移为
\[dp_{u,i}=dp_{ls,0}dp_{rs,i}+dp_{ls,i}dp_{rs,0}+dp_{ls,i}dp_{rs,i} \]\[dp_{u,0}=2dp_{ls,0}dp_{rs,0}+\sum dp_{u,i} \]初始值是对于叶子结点 \(v\)，如果它在第 \(i\) 类，有 \(dp_{v,0}=dp_{v,i}=1\)。答案是 \(dp_{1,0}+dp_{1,1}\)。直接做这个 DP，复杂度是 \(O(n\times\min(n,m))\)，结合特殊性质可以获得 \(85\) 分。
最后 \(15\) 分，只需要记录 \(dp_u\) 中每个非零数，做启发式合并即可。具体的，需要维护一个乘法标记，以及 \(\sum_{i\neq 0} dp_{u,i}\)。使用 map 实现，时间复杂度是 \(O(n\log^2 n)\)。
中间有一步除法，可能遇到除以 \(0\) 的情况，所以需要特殊处理（是容易的）。场上当然没有考虑到，不过良心出题人 jiangly 在 WC 的数据里并没有卡，赞美良心出题人！
代码是赛后补的。
#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
const int N=4e5+5,P=998244353;
int qpow(int a,int b=P-2){
int c=1;
for(;b;b>>=1,a=1ll*a*a%P)
if(b&1)c=1ll*c*a%P;
return c;
}
int n,m,tot=1,h[2][N],typ[N];
struct node{int ls,rs,l,r;}tr[N];
void build(int p,int l,int r){
tr[p].l=l;tr[p].r=r;
if(l==r)return;
int mid;scanf("%d",&mid);
tr[p].ls=++tot;build(tot,l,mid);
tr[p].rs=++tot;build(tot,mid+1,r);
}
vector<pair<int,int> > vec;
map<int,int> dp[N];int to[N],mul[N],sum[N];
int main(){
scanf("%d%d",&n,&m);build(1,1,n);
for(int i=1,l,r;i<=m;i++){
scanf("%d%d",&l,&r);++l;++r;
int v0=rnd()%P,v1=rnd()%P;
h[0][l]=(h[0][l]+v0)%P;h[0][r]=(h[0][r]+P-v0)%P;
h[1][l]=(h[1][l]+v1)%P;h[1][r]=(h[1][r]+P-v1)%P;
}
for(int i=1;i<=n;i++){
h[0][i]=(h[0][i]+h[0][i-1])%P;
h[1][i]=(h[1][i]+h[1][i-1])%P;
vec.push_back({h[0][i],h[1][i]});
}
vec.push_back({0,0});sort(vec.begin(),vec.end());
for(int i=1;i<=n;i++)typ[i]=lower_bound(vec.begin(),vec.end(),
make_pair(h[0][i],h[1][i]))-vec.begin()+1;
for(int i=2*n-1;i>=1;i--){
if(!tr[i].ls){
dp[i][0]=dp[i][typ[tr[i].l]]=1;
to[i]=i;mul[i]=sum[i]=1;continue;
}
int x=to[tr[i].ls],y=to[tr[i].rs];
if(dp[x].size()<dp[y].size())swap(x,y);
int vl=dp[x][0],vr=dp[y][0];to[i]=x;
mul[x]=1ll*mul[x]*mul[y]%P*vr%P;
dp[x][0]=(vl+vl)%P;
for(auto it:dp[y]){
int c=it.first,f=it.second;
if(c==0)continue;int&g=dp[x][c];
int tmp=1ll*f*(g+vl)%P*qpow(vr)%P;
g=(g+tmp)%P;sum[x]=(sum[x]+tmp)%P;
}
dp[x][0]=(dp[x][0]+sum[x])%P;
}
int ans=(dp[to[1]][0]+dp[to[1]][1])%P;
ans=1ll*ans*mul[to[1]]%P;
printf("%d\n",ans);
return 0;
}