Loj #2331. 「清华集训 2017」某位歌姬的故事

IA 是一名会唱歌的女孩子。

IOI2018 就要来了，IA 决定给参赛选手们写一首歌，以表达美好的祝愿。这首歌一共有 \(n\) 个音符，第 \(i\) 个音符的音高为 \(h_i\)。IA 的音域是 \(A\)，她只能唱出 \(1\sim A\) 中的正整数音高。因此 \(1\le h_i\le A\)。

在写歌之前，IA 需要确定下这首歌的结构，于是她写下了 \(Q\) 条限制，其中第 \(i\) 条为：编号在 \(l_i\) 到 \(r_i\) 之间的音符的最高音高为 \(m_i\)。在确定了结构之后，她就可以开始写歌了。不过她还是想知道，一共有多少种可能的歌曲满足她的所有限制？她听说你还有 9 个月就要去 IOI 了，于是希望你帮她计算一下这个值。

输入格式

从标准输入读入数据。

输入的第一行包含一个整数 \(T(T\le 20)\)，代表测试数据的组数。

每组数据的第一行包含三个正整数 \(n,Q,A\)。接下来 \(Q\) 行，每行三个整数 \(l_i,r_i,m_i\)，表示一条限制。保证 \(1\le l_i\le r_i\le n, 1\le m_i\le A\)。

输出格式

输出到标准输出。

输出文件只有一行，表示可能的歌曲数目。这个数可能很大，请将答案模 \(998244353\) 输出。

数据范围与提示

$n \leq 9\times 10^8 $ $Q \leq 500 $ $A \leq 9\times 10^8 $

首先我们将坐标离散化。也就是对于所有区间\([l,r]\)，我们将\(l,l+1,r,r+1\)离散。

然后将所有询问按\(m_i\)排序。我们发现当询问\(i\)与询问\(j\)的区间有交，如果\(m_i<m_j\)，那么交的部分全部分配给\(i\)。这样，\(m\)不同的区间就没有交了。

接着考虑做法。因为我们可以很容易算出区间最大值\(\leq\)某个值的答案，所以考虑容斥。我们设\(f_{S}\)表示\(\{S\}\)集合中的询问都不满足的答案。如果要求不满足询问\((l,r,m)\)，那么区间\([l,r]\)内的元素要\(\leq m-1\)。最终答案就是：

\[ ans=\sum_{S}(-1)^{|S|}f_S \]

我们发现，如果所有区间的\(m\)不同，那么很好做，因为即使降低了某些询问的上限，也不会改变相交区间的分配情况。于是对于\(m\)相同的情况，我们考虑\(DP\)

我们将\(m\)相同的询问按左端点排序，设\(f_{i,j}\)表示满足了\(DP\)了前\(i\)个询问，降低了上限的询问中最右端点为\(j\)的答案。考虑加入第\(i\)个询问的时候就与\(j\)判断一下就知道\(i\)还可以控制的区间有多少了。\(DP\)的时候还要带着容斥系数\(DP\)。

代码：

#include
    
     #define ll long long#define Q 505using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}const ll mod=998244353;ll ksm(ll t,ll x) {    ll ans=1;    for(;x;x>>=1,t=t*t%mod)        if(x&1) ans=ans*t%mod;    return ans;}int T;int n,q,A;vector
     
      disc;int len[Q<<2];int tot;struct query {    int l,r,mx;    bool operator <(const query &a)const {        if(mx!=a.mx) return mx
      
       j) New=pre[s[i].r]-pre[max(j,s[i].l-1)];            (f[i][max(s[i].r,j)]+=(mod-1)*f[i-1][j]%mod*ksm(inv,New))%=mod;        }    }    ll ans=0;    for(int i=0;i