Loj #2331. 「清华集训 2017」某位歌姬的故事
IA 是一名会唱歌的女孩子。
IOI2018 就要来了，IA 决定给参赛选手们写一首歌，以表达美好的祝愿。这首歌一共有 (n) 个音符，第 (i) 个音符的音高为 (h_i)。IA 的音域是 (A)，她只能唱出 (1sim A) 中的正整数音高。因此 (1le h_ile A)。
在写歌之前，IA 需要确定下这首歌的结构，于是她写下了 (Q) 条限制，其中第 (i) 条为：编号在 (l_i) 到 (r_i) 之间的音符的最高音高为 (m_i)。在确定了结构之后，她就可以开始写歌了。不过她还是想知道，一共有多少种可能的歌曲满足她的所有限制？她听说你还有 9 个月就要去 IOI 了，于是希望你帮她计算一下这个值。
输入格式
从标准输入读入数据。
输入的第一行包含一个整数 (T(Tle 20))，代表测试数据的组数。
每组数据的第一行包含三个正整数 (n,Q,A)。接下来 (Q) 行，每行三个整数 (l_i,r_i,m_i)，表示一条限制。保证 (1le l_ile r_ile n, 1le m_ile A)。
输出格式
输出到标准输出。
输出文件只有一行，表示可能的歌曲数目。这个数可能很大，请将答案模 (998244353) 输出。
数据范围与提示
$n leq 9 imes 10^8 $ $Q leq 500 $ $A leq 9 imes 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)。最终答案就是：
我们发现，如果所有区间的(m)不同，那么很好做，因为即使降低了某些询问的上限，也不会改变相交区间的分配情况。于是对于(m)相同的情况，我们考虑(DP)
我们将(m)相同的询问按左端点排序，设(f_{i,j})表示满足了(DP)了前(i)个询问，降低了上限的询问中最右端点为(j)的答案。考虑加入第(i)个询问的时候就与(j)判断一下就知道(i)还可以控制的区间有多少了。(DP)的时候还要带着容斥系数(DP)。
代码：
#include<bits/stdc++.h>
#define ll long long
#define Q 505
using 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<int>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<a.mx;
if(l!=a.l) return l<a.l;
return r<a.r;
}
bool operator ==(const query &a)const {
return l==a.l&&r==a.r&&mx==a.mx;
}
}s[Q];
int tag[Q<<2];
int pre[Q<<2];
ll f[Q<<2][Q<<2];
ll DP(int L,int R) {
pre[0]=0;
for(int i=1;i<tot;i++)
pre[i]=pre[i-1]+(tag[i]?0:len[i]);
ll inv=ksm(s[L].mx,mod-2)*(s[L].mx-1)%mod;
f[L][0]=1;
f[L][s[L].r]=(mod-ksm(inv,pre[s[L].r]-pre[s[L].l-1]))%mod;
for(int i=L+1;i<=R;i++) {
for(int j=0;j<tot;j++) {
if(!f[i-1][j]) continue ;
(f[i][j]+=f[i-1][j])%=mod;
int New=0;
if(s[i].r>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<tot;i++) (ans+=f[R][i])%=mod;
return ans;
}
int main() {
T=Get();
while(T--) {
memset(f,0,sizeof(f));
disc.clear();
n=Get(),q=Get(),A=Get();
for(int i=1;i<=q;i++) {
s[i].l=Get(),s[i].r=Get(),s[i].mx=Get();
disc.push_back(s[i].l);
disc.push_back(s[i].r);
}
disc.push_back(0);
disc.push_back(1);
disc.push_back(n);
sort(disc.begin(),disc.end());
for(int i=0,x=disc.size();i<x;i++)
if(disc[i]+1<=n) disc.push_back(disc[i]+1);
sort(disc.begin(),disc.end());
disc.resize(unique(disc.begin(),disc.end())-disc.begin());
tot=disc.size();
for(int i=0;i<tot;i++)
if(i<tot-1) len[i]=disc[i+1]-disc[i];
else len[i]=1;
for(int i=1;i<=q;i++) {
s[i].l=lower_bound(disc.begin(),disc.end(),s[i].l)-disc.begin();
s[i].r=lower_bound(disc.begin(),disc.end(),s[i].r)-disc.begin();
}
sort(s+1,s+1+q);
q=unique(s+1,s+1+q)-s-1;
memset(tag,0,sizeof(tag));
ll ans=1;
for(int i=1;i<=q;i++) {
int j=i;
while(j<q&&s[j+1].mx==s[i].mx) j++;
ll tem=DP(i,j)%mod;
int sum=0;
for(int k=i;k<=j;k++) {
for(int p=s[k].l;p<=s[k].r;p++) {
if(!tag[p]) sum+=len[p];
tag[p]=1;
}
}
ans=ans*tem%mod*ksm(s[i].mx,sum)%mod;
i=j;
}
for(int i=1;i<tot;i++) if(!tag[i]) ans=ans*ksm(A,len[i])%mod;
cout<<ans<<"
";
}
return 0;
}