赛时差一步做出来 这个dp做法还是很有道理的

原题：P4229 [清华集训 2017] 某位歌姬的故事

首先看到这个题的第一眼我们会认为它很糖，会认为我们只需要离散化，然后对于每一种询问，用$<=c$的情况减去$<c$的情况就是满足这些询问的方案数，然后你就假了hhh。

假在哪里呢？我们发现如果有两个区间要求最大值相同，那么就需要容斥，然后就很复杂。因此我们来想一个更靠谱的东西。

考虑$m=c=2$的数据，要求变成了给定一些区间，每个区间内至少有$1$个$2$的方案数。

于是我们可以设计$dp$。$dp_i$表示处理完前$i$个数，第$i$个数为$2$的方案数。

转移的时候我们枚举下一个$2$在哪里，然后钦定两个$2$中间都是$1$。同时我们需要保证，两个$2$中间不存在一个完整的区间，否则不满足要求。以下为这一部分代码。

dp[0]=1;
		for(int i=0;i<ltt;i++){
			int Lim=inf;
			dp[i]=dp[i]*(qpow(2,ldd[i+1]-ldd[i])-1+mod)%mod;
			for(int j=i+1;j<=ltt;j++){
				Lim=min(Lim,minlim[j]);
				if(Lim<j) break;
				dp[j]=(dp[j]+dp[i])%mod;
			}
		}
		cout<<dp[ltt]<<"\n";

这里$ltt$代表离散化后的数组。复杂度为$O(Tk^2logV)$ 把刷表改成填表能$O(TklogV)$，但是我觉得刷表更好写就写的刷表。

然后我们来考虑多种限制该怎么做。同样的方法不行了，因为原来的一段区间在有多种限制后可能被分成好多段，不容易讨论。

还记得我们一开始怎么想的吗，难做的是同种限制相交，因此，我们只需要对于每一种$c$，把它所对应的限制提出来，再用刚才的$dp$就可以了。

具体地，我们用$minc$记录该位置上最小的限制是什么，然后枚举$c$，提取所有$minc_i=c$以及$c$对应的区间。

这样做是$O(Tk^2logV)$的，还算比较好写。可以通过精细实现以及刚才所说的填表达到$O(TklogV)$，但是我太懒了不想写qwq。

不要忘了判无解。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define mkp make_pair
const int mod=998244353,inf=1e9;
int qpow(int x,int y){
	int sum=1;
	while(y){
		if(y&1) sum=sum*x%mod;
		x=x*x%mod;
		y>>=1;
	}return sum;
} 
int T,n,k,m;
struct QRY{
	int l,r,c;
}qry[101000];
struct LSH{
	int a[101000],tot;
	void add(int x){a[++tot]=x;}
	void build(){sort(a+1,a+tot+1);tot=unique(a+1,a+tot+1)-a-1;}
	int EF1(int x){
		int l=1,r=tot;
		while(l<r){
			int mid=((l+r+1)>>1);
			if(a[mid]<=x) l=mid;
			else r=mid-1;
		}return l;
	}int EF2(int x){
		int l=1,r=tot;
		while(l<r){
			int mid=((l+r)>>1);
			if(a[mid]<x) l=mid+1;
			else r=mid;
		}return l;
	}
}Ll,Lc;
int minc[101000],tag[101000];
int nwc,len[101000],nwn;
int minlim[101000],dp[101000],sumlen[101000];
int solve(){
	for(int i=1;i<=nwn;i++) dp[i]=0;
	dp[0]=1;
	for(int i=0;i<nwn;i++){
		int Lim=inf;
		for(int j=i+1;j<=nwn;j++){
			Lim=min(Lim,minlim[j]);
			if(Lim<j) break;
			int val=qpow(nwc-1,sumlen[j-1]-sumlen[i])*(qpow(nwc,sumlen[j]-sumlen[j-1])-qpow(nwc-1,sumlen[j]-sumlen[j-1])+mod)%mod;
			dp[j]=(dp[j]+dp[i]*val)%mod;
		}
	}return dp[nwn];
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>k>>m;
		Ll.tot=Lc.tot=0; 
		for(int i=1;i<=k;i++){
			cin>>qry[i].l>>qry[i].r>>qry[i].c;
			Ll.add(qry[i].l);
			Ll.add(qry[i].r+1);
			Lc.add(qry[i].c);
		}Ll.add(1);Ll.add(n+1);Lc.add(m);
		
		Ll.build();Lc.build();
		Ll.tot--;for(int i=1;i<=2*k+2;i++) minc[i]=Lc.tot;
		for(int i=1;i<=k;i++){
			qry[i].l=Ll.EF1(qry[i].l);
			qry[i].r=Ll.EF1(qry[i].r);
			qry[i].c=Lc.EF1(qry[i].c);
			for(int j=qry[i].l;j<=qry[i].r;j++) minc[j]=min(minc[j],qry[i].c);
		}
		
		int ans=1,flag=0;
		for(int col=1;col<=Lc.tot;col++){//下意识的认为c是color，所以就这么写了 
			nwn=0;
			for(int i=1;i<=Ll.tot;i++)
				if(minc[i]==col)tag[i]=++nwn,len[nwn]=Ll.a[i+1]-Ll.a[i];
			nwn++;len[nwn]=1;//在最后补一位，方便统计答案。 
			for(int i=1;i<=nwn;i++) minlim[i]=inf,sumlen[i]=sumlen[i-1]+len[i];
			for(int i=1;i<=k;i++){
				if(qry[i].c==col){
					int minn=inf,maxx=-1;
					for(int j=qry[i].l;j<=qry[i].r;j++){
						if(minc[j]==col)minn=min(minn,tag[j]),maxx=max(maxx,tag[j]);
					}
					if(minn==inf){
						flag=1;
						break;//判无解 
					}
					minlim[minn]=min(minlim[minn],maxx);
				}
			}if(flag) break;
			nwc=Lc.a[col];
			ans=ans*solve()%mod;
			
		}
		if(flag) ans=0; 
		cout<<ans<<"\n";
	}
	
	return 0;
}