luogu P4229 某位歌姬的故事

题面传送门
如果做过这个dp套路的话感觉这题到不了黑？
显然可以先离散，然后求出分出来每一段的最大值。
因为一段的最大值中这个最大值没法放到更小的地方去，所以只能放在最大值为这个值的位置。
容易得到一段长度为\(Len\)的位置，要求最大值为\(A\)的方案数为\(A^{Len}-(A-1)^{Len}\)
然后剩下的就是套路，对于每种最大值统一处理，设\(dp_{i,j}\)为到了第\(i\)个位置，最早的限制在\(j\)，然后分当前段是否放最大值就可以转移。
时间复杂度\(O(TQ^2)\)，似乎可以做到\(O(TQ\log Q)\)但是没必要。
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N (1000+5)
#define M (400000+5)
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;
int T,n,m,k,x,y,z,Ns[N],H,A[N],Q[N];ll dp[N],Ans,N1,N2;
I ll mpow(ll x,int y=mod-2){ll Ans=1;while(y) y&1&&(Ans=Ans*x%mod),y>>=1,x=x*x%mod;return Ans;}
struct Ques{int l,r,w;}S[N];I bool cmp(Ques x,Ques y){return x.w=S[i].l&&A[S[i].l]^S[i].w) S[i].l++;while(S[i].r>=S[i].l&&A[S[i].r]^S[i].w) S[i].r--;if(S[i].rk) Ans=Ans*mpow(k,Ns[i+1]-Ns[i])%mod;printf("%lld\n",(Ans+mod)%mod);
}
int main(){
	freopen("1.in","r",stdin);
	scanf("%d",&T);while(T--) Solve();
}