洛谷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;
}