洛谷P4229 某位歌姬的故事题解

题意：

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\) 输出。

数据范围：

\(0\le n,A \le 9\times 10^{8},~ 0 \le Q \le 500\) 。

没完全懂，待研究。咕咕咕。。

首先可以把端点离散化一下，则以下可以认为 \(n,Q\) 同阶。

设 \(\mathtt{mx[i]}\) 表示第 \(i\) 个位置的元素可以达到的最大值。

这可以通过对覆盖当前位置的每个限制暴力取 \(\min\) 得到。

对于一个限制 \((l_i,r_i,m_i)\) ，显然只有区间 \([l_i,r_i]\) 中，\(\mathtt{mx[x]}=m_i\) 的位置 \(x\) 可能使得限制满足。

因为当 \(\mathtt{mx[x]}<m_i\) 时，说明这个位置被一个更紧的限制卡住了；

当 \(\mathtt{mx[x]} > m_i\) 时，说明区间 \(i\) 根本没有覆盖到 \(x\) 。这说明 \(\mathtt{mx[]}\) 取值不同的位置互不影响。

考虑枚举 \(\mathtt{mx[x]}\) 的值 \(k\) ，将 \(\mathtt{mx[x]}=k\) 的下标 \(x\) 拿出来dp。

则限制转化为： \([l_i,r_i]\) 中存在一个元素顶到 \(k\) 的上界。

设 \(f_{i,j}\) 表示填了前 \(i\) 个位置，最后一个顶到 \(k\) 的位置是 \(j\) 时的方案数。

转移时枚举一个新的位置 \(i\) ，预先维护出所有右端点为 \(i\) 的区间中左端点的最大值进行转移即可。

时间复杂度 \(\mathcal{O}(TQ^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void mul(int &x,int y) { x = x * y % mod; }
void add(int &x,int y) { x = (x + y % mod) % mod; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename A, typename ...B>
        void read(A &x, B &...y) { return read(x), read(y...); }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define Fi first
#define Se second
#define N ((int)(1e3+15))

int n,Q,A,ans=1,len;
int L[N],R[N],m[N],p[N];
int f[N][N],mx[N],lim[N],idx[N];
vector<int> vec; vector<pii> opt;
int qpow(int a,int b)
{
    int ans = 1, base = a % mod;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = ans * base % mod;
        base = base * base % mod;
    }return ans;
}
void clear()
{
    memset(mx,0x3f,sizeof(mx));
    vec.clear(); opt.clear(); ans = 1;
}
int exist(int m,int s)
{ return (qpow(m,s) - qpow(m-1, s) + mod) % mod; }
int siz(int x) { return vec[x] - vec[x-1]; }
int getid(int x)
{ return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1; }
int calc(int m,int l,int r)
{
    int res = 0, o = 0; f[0][0] = 1;
    for(int i=1; i<=len; i++) if(mx[i] == m) idx[++o] = i;
    for(int i = l, _l, _r; i<=r; i++)
    {
        _l = *lower_bound(idx + 1, idx + 1 + o, L[p[i]]);
        _r = *(lower_bound(idx + 1, idx + 1 + o, R[p[i]]) - 1);
        up(lim[_r], _l);
    }
    for(int i=1; i<=len; i++) up(lim[i], lim[i-1]);
    for(int i=1; i<=o; i++)
        for(int j=0; j<idx[i]; j++)
        {
            add(f[i][idx[i]], f[i-1][j] * exist(m, siz(idx[i])) % mod);
            if(lim[idx[i]] <= j) f[i][j] = f[i-1][j] * qpow(m-1, siz(idx[i])) % mod;
        }
    for(int i=1; i<=idx[o]; i++) add(res, f[o][i]);
    for(int i=0; i<=len; i++) lim[i] = 0;
    for(int i=1; i<=o; i++)
        for(int j=0; j<=idx[i]; j++) f[i][j] = 0;
    return res;
}
void work()
{
    clear(); read(n,Q,A);
    for(int i=1; i<=Q; i++)
    {
        read(L[i], R[i], m[i]); ++R[i];
        opt.push_back({L[i], 1}); opt.push_back({R[i], -1});
        vec.push_back(L[i]); vec.push_back(R[i]); p[i] = i;
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end()); len = vec.size();
    for(int i=1; i<=Q; i++)
    {
        L[i] = getid(L[i]); R[i] = getid(R[i]);
        for(int j = L[i]; j < R[i]; j++) down(mx[j], m[i]);
    }
    sort(p + 1, p + 1 + Q, [](int x,int y) { return m[x] < m[y]; });
    for(int l = 1, r; l<=Q; l = r + 1)
    {
        for(r = l; r < Q && m[p[r+1]] == m[p[l]]; ++r);
        mul(ans, calc(m[p[l]], l, r));
    }
    sort(opt.begin(), opt.end()); int cur = 0, pre = 1;
    for(int l = 0, r; l < opt.size(); l = r + 1)
    {
        if(!cur) mul(ans, qpow(A, opt[l].Fi - pre));
        r = l; cur += opt[l].Se;
        while(r+1 < opt.size() && opt[r+1].Fi == opt[l].Fi) cur += opt[++r].Se;
        pre = opt[l].Fi;
    }
    mul(ans, qpow(A, n - pre + 1)); write(ans); pc('\n');
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _Q; read(_Q); while(_Q--) work();
    return 0;
}