题目链接
问题分析
吐槽一下这个预处理比DP还长的题……
首先对限制从小到大排序，然后不难发现对于每一种大小限制都是独立的。离散后考虑\(F[i][j]\)表示以\(i\)结尾，上一个音高为限制大小的位置\(j\)的方案种数。不难发现对于一些右端点相同的限制，左端点最右的限制才有效。这样就可以\(n^2\)动规了。
由于要离散化，所以细节很多。
参考程序
程序没有显式的离散化，并且大量使用结构体，所以又慢又长。
#include <bits/stdc++.h>
#define LL long long
using namespace std;void Work();
int main() { int TestCases; scanf( "%d", &TestCases ); for( ; TestCases--; ) Work(); return 0; }const int Mod = 998244353;
const int MaxQ = 510;
struct seg {int Left, Right;seg() {}seg( int _Left, int _Right ) : Left( _Left ), Right( _Right ) {}
};
inline bool Cmp1( const seg X, const seg Y ) { return X.Left < Y.Left || X.Left == Y.Left && X.Right < Y.Right; }
struct query {seg Seg; int High;inline void Read() { scanf( "%d%d%d", &Seg.Left, &Seg.Right, &High ); return; }inline bool operator < ( const query Other ) const { return High < Other.High || High == Other.High && Cmp1( Seg, Other.Seg ); }
};
int Temp1[ MaxQ << 1 ], Temp2[ MaxQ << 1 ];
struct member {int Size, High; seg Seg[ MaxQ << 1 ];inline void Clear() { memset( Seg, 0, sizeof( Seg ) ); Size = High = 0; return; }inline void Import( const query Other ) { Clear(); Size = 1; High = Other.High; Seg[ Size ] = Other.Seg; return; }inline void Add( const query Other ) { Seg[ ++Size ] = Other.Seg; return; }inline void Copy( int Left, int Right ) { if( Left > Right ) return; ++Size; Seg[ Size ].Left = Left; Seg[ Size ].Right = Right; return; }void Unique( member &Goal ) {Goal.Clear(); Goal.High = High; int CoverNum = 0;for( int i = 1; i <= Size; ++i ) Temp1[ i ] = Seg[ i ].Left, Temp2[ i ] = Seg[ i ].Right;sort( Temp1 + 1, Temp1 + Size + 1 ); sort( Temp2 + 1, Temp2 + Size + 1 );int Link1 = 1, Link2 = 1, Last = 0;for( ; Link1 <= Size && Link2 <= Size; ) {if( Temp1[ Link1 ] <= Temp2[ Link2 ] ) {if( CoverNum ) Goal.Copy( Last, Temp1[ Link1 ] - 1 );Last = Temp1[ Link1++ ]; ++CoverNum;} else {if( CoverNum ) Goal.Copy( Last, Temp2[ Link2 ] );Last = Temp2[ Link2++ ] + 1; --CoverNum;}}for( ; Link1 <= Size; ) { if( CoverNum ) Goal.Copy( Last, Temp1[ Link1 ] - 1 ); Last = Temp1[ Link1++ ]; ++CoverNum; }for( ; Link2 <= Size; ) { if( CoverNum ) Goal.Copy( Last, Temp2[ Link2 ] ); Last = Temp2[ Link2++ ] + 1; ++CoverNum; }return;}void Delete( const member Done, member &Collect ) {Collect.Clear(); Collect.High = High;int Link1 = 1, Link2 = 1;for( ; Link1 <= Size && Link2 <= Done.Size; ) {if( Done.Seg[ Link2 ].Left > Seg[ Link1 ].Right ) { Collect.Copy( Seg[ Link1 ].Left, Seg[ Link1 ].Right ); ++Link1; continue;}if( Done.Seg[ Link2 ].Right < Seg[ Link1 ].Left ) { ++Link2; continue; }if( Done.Seg[ Link2 ].Left <= Seg[ Link1 ].Left && Seg[ Link1 ].Right <= Done.Seg[ Link2 ].Right ) { ++Link1; continue; }if( Seg[ Link1 ].Left <= Done.Seg[ Link2 ].Left && Done.Seg[ Link2 ].Right <= Seg[ Link1 ].Right ) {Collect.Copy( Seg[ Link1 ].Left, Done.Seg[ Link2 ].Left - 1 ); Seg[ Link1 ].Left = Done.Seg[ Link2 ].Right + 1;++Link2; continue;}if( Seg[ Link1 ].Left < Done.Seg[ Link2 ].Left ) { Collect.Copy( Seg[ Link1 ].Left, Done.Seg[ Link2 ].Left - 1 ); ++Link1; continue; }if( Seg[ Link1 ].Left > Done.Seg[ Link2 ].Left ) { Seg[ Link1 ].Left = Done.Seg[ Link2 ].Right + 1; ++Link2; continue; }}for( ; Link1 <= Size; ++Link1 ) Collect.Copy( Seg[ Link1 ].Left, Seg[ Link1 ].Right );return;}void Union( member Other ) {member Ans; Ans.Clear();int Link1 = 1, Link2 = 1;for( ; Link1 <= Size && Link2 <= Other.Size; ) {if( Seg[ Link1 ].Left < Other.Seg[ Link2 ].Left ) Ans.Seg[ ++Ans.Size ] = Seg[ Link1++ ];else Ans.Seg[ ++Ans.Size ] = Other.Seg[ Link2++ ];}for( ; Link1 <= Size; ) Ans.Seg[ ++Ans.Size ] = Seg[ Link1++ ];for( ; Link2 <= Other.Size; ) Ans.Seg[ ++Ans.Size ] = Other.Seg[ Link2++ ];Size = 1; Seg[ 1 ] = Ans.Seg[ 1 ];for( int i = 2; i <= Ans.Size; ++i )if( Seg[ Size ].Right + 1 == Ans.Seg[ i ].Left ) Seg[ Size ].Right = Ans.Seg[ i ].Right;else Seg[ ++Size ] = Ans.Seg[ i ];return;}
};
int n, Q, A, Ans;
query Query[ MaxQ ];
member Done, Now, Seperate, Collect;
int F[ MaxQ << 1 ][ MaxQ << 1 ], Before[ MaxQ << 1 ];
inline int FastPow( int a, int x ) { if( x <= 0 ) return 1; int Ans = 1; for( ; x; x >>= 1, a = 1ll * a * a % Mod ) if( x & 1 ) Ans = 1ll * Ans * a % Mod; return Ans; }
inline bool Cmp2( query X, query Y ) { return X.Seg.Right < Y.Seg.Right || X.Seg.Right == Y.Seg.Right && X.Seg.Left < Y.Seg.Left; }
inline int FindGreater( int x ) { for( int i = 1; i <= Collect.Size; ++i ) if( Collect.Seg[ i ].Left >= x ) return i; return Collect.Size + 1; }
inline int FindFewer( int x ) { for( int i = Collect.Size; i >= 1; --i ) if( Collect.Seg[ i ].Right <= x ) return i; return 0LL; }int Dp( int Left, int Right ) {if( Collect.Size == 0 ) return 0LL;sort( Query + Left, Query + Right + 1, Cmp2 );for( int i = Left; i <= Right; ++i ) {Query[ i ].Seg.Left = FindGreater( Query[ i ].Seg.Left );Query[ i ].Seg.Right = FindFewer( Query[ i ].Seg.Right );if( Query[ i ].Seg.Left > Query[ i ].Seg.Right ) return 0LL;}memset( Before, 0, sizeof( Before ) );for( int i = Left; i <= Right; ++i ) Before[ Query[ i ].Seg.Right ] = max( Before[ Query[ i ].Seg.Right ], Query[ i ].Seg.Left );for( int i = 1; i <= Collect.Size; ++i ) Before[ i ] = max( Before[ i ], Before[ i - 1 ] );memset( F, 0, sizeof( F ) );F[ 0 ][ 0 ] = 1;for( int i = 1; i <= Collect.Size; ++i ) {int Fuint = FastPow( Collect.High, Collect.Seg[ i ].Right - Collect.Seg[ i ].Left + 1 );int None = FastPow( Collect.High - 1, Collect.Seg[ i ].Right - Collect.Seg[ i ].Left + 1 );Fuint = ( Fuint - None + Mod ) % Mod;for( int j = 0; j < i; ++j ) {if( j >= Before[ i ] ) F[ i ][ j ] = ( F[ i ][ j ] + 1ll * F[ i - 1 ][ j ] * None % Mod ) % Mod;F[ i ][ i ] = ( F[ i ][ i ] + 1ll * F[ i - 1 ][ j ] * Fuint % Mod ) % Mod;}}int Ans = 0;for( int i = 0; i <= Collect.Size; ++i ) Ans = ( Ans + F[ Collect.Size ][ i ] ) % Mod;return Ans;
}void Work() {scanf( "%d%d%d", &n, &Q, &A );for( int i = 1; i <= Q; ++i ) Query[ i ].Read();sort( Query + 1, Query + Q + 1 );Done.Clear();Ans = 1;for( int i = 1, j; i <= Q; i = j + 1 ) {j = i; Now.Import( Query[ j ] );for( ; j < Q && Query[ j + 1 ].High == Now.High; Now.Add( Query[ ++j ] ) );Now.Unique( Seperate );Seperate.Delete( Done, Collect );Done.Union( Collect );Ans = 1ll * Ans * Dp( i, j ) % Mod;}if( !Done.Size ) Ans = 1ll * Ans * FastPow( A, n ) % Mod; else {Ans = 1ll * Ans * FastPow( A, Done.Seg[ 1 ].Left - 1 ) % Mod;Ans = 1ll * Ans * FastPow( A, n - Done.Seg[ Done.Size ].Right ) % Mod;for( int i = 1; i < Done.Size; ++i ) Ans = 1ll * Ans * FastPow( A, Done.Seg[ i + 1 ].Left - Done.Seg[ i ].Right - 1 ) % Mod;}printf( "%d\n", Ans );return;
}
