AT_abc477_f [ABC477F] Count Cells in a Window原题链接[ABC477F] Count Cells in a Window分析一眼秒的扫描线……扫描线的本质还是枚举一个另外一个直接扔到线段树上当然本题可以写树状数组……正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN200005;intn,m,q;structcol{intid;intl,r;}a[N];inttot;structask{intid,l,r,val;}b[N2];booloperator(constasktmp1,constasktmp2){returntmp1.ltmp2.l;}structBIT{intc[N];voidadd(intx,intval){for(intix;im;ii(-i))c[i]val;}intquery(intx){intres0;for(intix;i;i-i(-i))resc[i];returnres;}}T1,T2;voidmodify(intl,intr,intval){T1.add(l,val);T1.add(r1,-val);T2.add(l,val*l);T2.add(r1,-val*(r1));}intquery(intx){return(x1)*T1.query(x)-T2.query(x);}intans[N];signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnmq;for(inti1;in;i){cina[i].la[i].r;a[i].idi;}for(inti1,A,B,C,D;iq;i){cinABCD;b[tot]{i,B,D,1};b[tot]{i,A-1,D,-1};b[tot]{i,B,C-1,-1};b[tot]{i,A-1,C-1,1};}sort(b1,btot1);intcur0;for(inti1;itot;i){while(curb[i].l){cur;modify(a[cur].l,a[cur].r,1);}if(b[i].r0b[i].l0){ans[b[i].id]b[i].val*query(b[i].r);}}for(inti1;iq;i){coutans[i]\n;}}AT_arc156_b [ARC156B] Mex on Blackboard原题链接[ARC156B] Mex on Blackboard分析从某些角度而言我们需要知道a aa序列的所有子序列可以组成多少mex ⁡ \operatorname{mex}mex假设这个个数是c n t cntcnt那么答案似乎就是c n t k cnt^kcntk那么前一个怎么求呢排序是必要的……然后a i ≤ 2 × 10 5 a_i\le 2\times 10^5ai​≤2×105直接遍历似乎就可以了这么容易不不不你会发现我们每次都会把新的mex ⁡ \operatorname{mex}mex加进去。那我似乎可以进行DP了我们设d p k k , m e x dp_{kk,mex}dpkk,mex​表示我们现在进行到了第k k kkkk轮这一轮我们要往黑板上写的是m e x mexmex的方案数……转移类似于从前一个转移而且要把这次选满复杂度估计不低于O ( n 3 ) O(n^3)O(n3)。那咋做啊我们发现其实是另外一个分支我们发现如果现在写的是x xx且x xx是出现过的最大的那么我们需要把[ 0 , x ] [0,x][0,x]全都写上。假设我们需要c n t cntcnt次才能将其全部写上那么还剩下k − c n t k-cntk−cnt次。那么这个的方案数就是C k − c n t x x C_{k-cntx}^{x}Ck−cntxx​。我们枚举值域即可。正解#includebits/stdc.h#defineintlonglong#definemod998244353usingnamespacestd;constintN1000005;intn,k,a[N];intfac[N],inv[N];intqpow(inta,intb){intres1;while(b){if(b1)resres*a%mod;aa*a%mod;b1;}returnres;}intC(intn,intm){if(n0||m0||nm)return0;returnfac[n]*inv[n-m]%mod*inv[m]%mod;}intvis[N];signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnk;for(inti1;in;i){cina[i];vis[a[i]];}fac[0]1;for(inti1;iN;i){fac[i]fac[i-1]*i%mod;}inv[N-1]qpow(fac[N-1],mod-2);for(intiN-2;i0;i--){inv[i]inv[i1]*(i1)%mod;}intans0,cnt0;for(inti0;iN-5;i){if(!vis[i])cnt;if(vis[i1])continue;if(cntk)break;ans(ansC(k-cnti,i))%mod;}coutans;}凭啥这个能过