题解

本题是一道结合区间处理、动态规划和组合计数的综合性问题。

算法思路：

1. 区间处理与离散化：

   • 使用 multiset 维护当前活跃的最小值
   • 根据区间的左右端点 $l[i], r[i]$ 和最小值 $m[i]$ 将整个序列分割成若干段
   • 每一段记录其对应的最小值限制
   • 对区间进行排序和去重，建立离散化映射

2. 动态规划计数：

   • 状态 f[i][j]：考虑前 $i$ 个位置，其中有 $j$ 个位置取最小值时的方案数
   • 对于每个位置，有两种选择：
     • 取最小值：贡献为 $1$ 种方案
     • 取其他值：贡献为 $(m-1)^{len}$ 种方案（$len$ 为区间长度）
   • 使用快速幂计算 $(m-1)^{len}$ 和 $m^{len}$

3. 限制处理：

   • 对于每个查询 $[l, r]$ 要求最小值为 $m$
   • 建立 limit[x] 数组记录位置 $x$ 的最左限制
   • 在DP转移时，检查是否满足所有限制条件

4. 答案合并：

   • 对每个不同的最小值 $m$ 分别计算方案数
   • 最终答案为所有方案数的乘积，模 $998244353$

时间复杂度：$O(q \cdot seg^2)$，其中 $seg$ 为离散化后的区间数量。

//Author:KIT / Shunpower
//Cloud Island & Rain Temperature
//May the force be with you and me.
#include <bits/stdc++.h>
#define ET return 0
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define ull unsigned long long
#define inf INT_MAX
#define uinf INT_MIN
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fr1(i,a,b) for(int i=a;i<=b;i++)
#define fr2(i,a,b) for(int i=a;i>=b;i--)
#define ld long double
#define il inline
using namespace std;
const int N=1e5+10;
namespace Shun{
    int lowbit(int x){
        return x&-x;
    }
    template <typename T>
    inline void read(T &x){
       T s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){
            if(ch=='-'){
                w=0;
            }
            ch=getchar();
        }
       while(ch>='0'&&ch<='9'){
            s=s*10+ch-'0';
            ch=getchar();
       }
       x=(w?s:-s);
    }
    template <typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>9){
            write(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace Shun;
const int mod=998244353;
void add(int &x,int y){
    x+=y;
    if(x>=mod) x-=mod;
}
int tc;
int n,q,a;
multiset <int> s;
map <int,vector<int>> cut;
vector <pair<pii,int>> seg;
void standard_like(){
    sort(seg.begin(),seg.end(),[](pair<pii,int> &x,pair<pii,int> &y){
        return x.fi.se-x.fi.fi>y.fi.se-y.fi.fi;
    });
    while(!seg.empty()){
        if(seg.back().fi.se-seg.back().fi.fi<0) seg.pop_back();
        else break;
    }
    sort(seg.begin(),seg.end());
}
int l[510],r[510],m[510];
int val1[3010],val2[3010];
ll qpow(ll b,int p){
    if(!p) return 1;
    ll d=qpow(b,p>>1);
    if(p&1) return d*d%mod*b%mod;
    else return d*d%mod;
}
int f[3010][3010];
vector <int> pos;
map <int,int> allm;
vector<pair<pii,int>> rmove[510];
int limit[3010];
int calc(int x){
    pos.clear();
    fr1(i,0,(int)seg.size()-1) if(seg[i].se==x) pos.pb(i);
    memset(limit,-1,sizeof limit);
    fr1(i,1,q){
        if(m[i]==x) limit[r[i]]=max(limit[r[i]],l[i]);
    }
    fr1(i,0,pos.size()) fr1(j,0,i) f[i][j]=0;
    f[0][0]=1;
    fr1(i,1,pos.size()){
        int x=pos[i-1];
        fr1(j,0,i-1) add(f[i][j],1ll*f[i-1][j]*val1[x]%mod);
        fr1(j,0,i-1) add(f[i][i],1ll*f[i-1][j]*val2[x]%mod);
        // cout<<x<<"!"<<limit[x]<<endl;
        if(~limit[x]) f[i][0]=0;
        fr1(j,1,i) if(pos[j-1]<limit[x]) f[i][j]=0;
    }
    // cout<<f[1][0]<<' '<<f[1][1]<<endl;
    int ans=0;
    fr1(i,0,pos.size()) add(ans,f[pos.size()][i]);
    return ans;
}
void solve(){
    cut.clear();
    s.clear();
    seg.clear();
    allm.clear();
    cin>>n>>q>>a;
    fr1(i,1,q){
        cin>>l[i]>>r[i]>>m[i];
        allm[m[i]]=1;
        cut[l[i]].pb(m[i]);
        cut[r[i]+1].pb(-m[i]);
    }
    s.insert(a);
    int lst=1;
    for(auto i:cut){
        seg.pb({{lst,i.fi-1},*s.begin()});
        for(auto j:i.se){
            if(j<0) s.erase(s.find(-j));
            else s.insert(j);
        }
        lst=i.fi;
    }
    seg.pb({{lst,n},*s.begin()});
    standard_like();
    int sz=seg.size()-1;
    fr1(i,0,sz){
        seg.pb({{seg[i].fi.fi,seg[i].fi.fi},seg[i].se});
        seg.pb({{seg[i].fi.se,seg[i].fi.se},seg[i].se});
        seg[i].fi.fi++,seg[i].fi.se--;
    }
    standard_like();
    seg.resize(unique(seg.begin(),seg.end())-seg.begin());
    for(auto i:seg) allm[i.se]=1;
    int tot=0;
    for(auto &i:allm){
        tot++;
        i.se=tot;
        rmove[tot].clear();
    }
    // cerr<<tot<<"?"<<endl;
    fr1(i,0,(int)seg.size()-1){
        rmove[allm[seg[i].se]].pb(mp(seg[i].fi,i));
        // cout<<seg[i].fi.fi<<' '<<seg[i].fi.se<<' '<<seg[i].se<<endl;
        val1[i]=qpow(seg[i].se-1,seg[i].fi.se-seg[i].fi.fi+1);
        val2[i]=(qpow(seg[i].se,seg[i].fi.se-seg[i].fi.fi+1)+mod-val1[i])%mod;
        // cout<<val1[i]<<' '<<val2[i]<<endl;
    }
    // cout<<"!"<<seg.size()<<endl;
    fr1(i,1,q){
        l[i]=lower_bound(seg.begin(),seg.end(),mp(mp(l[i],0),0))-seg.begin();
        // cerr<<"?"<<m[i]<<endl;
        if(!allm.count(m[i])) return cout<<"0\n",void();
        int id=allm[m[i]];
        r[i]=lower_bound(rmove[id].begin(),rmove[id].end(),mp(mp(r[i]+1,0),0))-rmove[id].begin();
        // cerr<<m[i]<<' '<<r[i]<<"???"<<rmove[id].size()<<endl;
        r[i]--;
        if(r[i]==-1) return cout<<"0\n",void();
        r[i]=rmove[id][r[i]].se;
        if(r[i]<l[i]) return cout<<"0\n",void();
        // assert(seg[l[i]].fi.fi==seg[l[i]].fi.se);
        // assert(seg[r[i]].fi.fi==seg[r[i]].fi.se);
        // cout<<"!"<<l[i]<<' '<<r[i]<<' '<<m[i]<<endl;
    }
    int res=1;
    // cerr<<allm.size()<<endl;
    for(auto i:allm){
        res=1ll*calc(i.fi)*res%mod;
        // cout<<i.fi<<":"<<res<<endl;
    }
    cout<<res<<'\n';
}
// #define Ltp cute
int main(){
#ifdef Ltp
    freopen("count2.in","r",stdin); 
    // freopen("count.out","w",stdout);   
#endif
    ios::sync_with_stdio(false);
    cin>>tc;
    while(tc--) solve();
    cerr<<clock()<<endl;
    ET;
}
//ALL FOR Zhang Junhao.