[ARC182A] Chmax Rush!一个比较糖的做法。考虑如果第i ii次操作选择向左进行操作则对于j i jiji且V j V i V_jV_iVj​Vi​的操作j jj一定有P j P i P_jP_iPj​Pi​否则无论第j jj次操作向左还是向右第i ii次操作都无法向左走且对于这些操作j jj我们要求他们必须向右进行操作。于是有一个很糖的 DP设d p i , j , 0 / 1 dp_{i,j,0/1}dpi,j,0/1​表示考虑前i ii个操作所有V ≥ j V \ge jV≥j的操作全部向左/全部向右的方案数。时间复杂度O ( N Q ) O(NQ)O(NQ)。#includebits/stdc.husingnamespacestd;constintmod998244353;intn,q,cnt0;structjs{intp,v,id,vv;}a[5005];boolcmp(js x,js y){returnx.vvy.vv;}boolcmpp(js x,js y){returnx.idy.id;}intdp[5005][5005][2],dpp[5005];inttree[5005],tr[5005];intlowbit(intx){returnx(-x);}voidupdate(intx,inty){for(intix;icnt;ilowbit(i))tree[i]max(tree[i],y),tr[i]min(tr[i],y);}intquery(intx){intres0;for(intix;i;i-lowbit(i))resmax(res,tree[i]);returnres;}intqu(intx){intres1e95;for(intix;i;i-lowbit(i))resmin(res,tr[i]);returnres;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnq;for(inti1;iq;i){cina[i].pa[i].vv;a[i].idi;}sort(a1,a1q,cmp);for(inti1;iq;i)if(i1||a[i].vv!a[i-1].vv)cnt,a[i].vcnt;elsea[i].vcnt;sort(a1,a1q,cmpp);memset(tr,127,sizeof(tr));dpp[0]1;for(inti0;icnt;i)dp[0][i][0]dp[0][i][1]1;for(inti1;iq;i){a[i].vcnt-a[i].v1;if(query(a[i].v-1)a[i].p)dpp[i](dpp[i]dp[i-1][a[i].v-1][0])%mod;if(qu(a[i].v-1)a[i].p)dpp[i](dpp[i]dp[i-1][a[i].v-1][1])%mod;for(intj0;jcnt;j)if(ja[i].v){if(query(a[i].v-1)0||query(j)0)dp[i][j][0]dpp[i];elseif(query(a[i].v-1)a[i].p)dp[i][j][0](dp[i][j][0]dp[i-1][a[i].v-1][0])%mod;if(query(a[i].v-1)0||query(j)0)dp[i][j][1]dpp[i];elseif(qu(a[i].v-1)a[i].p)dp[i][j][1](dp[i][j][1]dp[i-1][a[i].v-1][1])%mod;}else{if(query(a[i].v-1)0){dp[i][j][0]dp[i-1][j][0];dp[i][j][1]dp[i-1][j][1];}}update(a[i].v,a[i].p);}coutdpp[q];return0;}