传送门
解题思路： 【loj#2331. 「清华集训 2017」某位歌姬的故事【动态规划】】将序列离散化后，可以给每个点确定一个取值的上界，那么每一种上届的贡献是独立的，分别求出再相乘即可。
对于一种上界ww ，把对应的点和限制提出，那么对于每个右端点，唯一有用的限制就是左端点最靠右的，记为 L[i]L [ i ] ，再设f[i][j]f [ i ] [ j ]表示到第ii个点，最后一个ww在jj的方案数转移即可。
由于要离散化，所以细节比较多。
#include
#define ll long long
using namespace std;
int getint()
{
int i=0,f=1;
char c;
for(c=getchar();
(c!='-')&&(c<'0'||c>'9');
c=getchar());
if(c=='-')c=getchar(),f=-1;
for(;
c>='0'&&c<='9';
c=getchar())i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
const int N=1005,INF=1e9,mod=998244353;
int T,n,m,A,mx,num,p[N],w[N],t[N],a[N],L[N],f[N][N];
ll ans;
struct data{int l,r,w;
}q[N];
ll Pow(ll x,int y)
{
ll res=1;
for(;
y;
y>>=1,x=x*x%mod)
if(y&1)res=res*x%mod;
return res;
}
void calc(int W)
{
num=0;
for(int i=1;
i<=n;
i++)if(a[i]==W)
t[++num]=i,L[num]=0,memset(f[num],0,sizeof(f[num]));
for(int i=1;
i<=m;
i++)if(q[i].w==W)
{
if(!num){ans=-1;
return;
}
int l=lower_bound(t+1,t+num+1,q[i].l)-t;
int r=lower_bound(t+1,t+num+1,q[i].r)-t-1;
L[r]=max(L[r],l);
}
f[0][0]=1;
for(int i=1;
i<=num;
i++)
{
ll v1=Pow(W,p[t[i]+1]-p[t[i]]),v2=Pow(W-1,p[t[i]+1]-p[t[i]]);
for(int j=0;
j=L[i])f[i][j]=(f[i][j]+f[i-1][j]*v2)%mod;
f[i][i]=(f[i][i]+f[i-1][j]*(v1+mod-v2))%mod;
}
}
ll res=0;
for(int i=0;
i<=num;
i++)res=(res+f[num][i])%mod;
ans=ans*res%mod;
}
void solve()
{
n=getint(),m=getint(),A=getint();
mx=num=0;
for(int i=1;
i<=m;
i++)
{
q[i].l=getint(),q[i].r=getint()+1,q[i].w=getint();
p[++num]=q[i].l,p[++num]=q[i].r,w[++mx]=q[i].w;
}
p[++num]=1,p[++num]=n+1,sort(p+1,p+num+1),n=unique(p+1,p+num+1)-p-1;
sort(w+1,w+mx+1),mx=unique(w+1,w+mx+1)-w-1;
for(int i=1;
i<=n;
i++)a[i]=INF;
for(int i=1;
i<=m;
i++)
{
q[i].l=lower_bound(p+1,p+n+1,q[i].l)-p;
q[i].r=lower_bound(p+1,p+n+1,q[i].r)-p;
for(int j=q[i].l;
j 
