赛时只做出 6 道题，没见过莫队套分块的 trick 导致落败。
A
模拟。
B
等同于找一个 A 的最短的前缀使得所有 1 到 M 的数字都出现过，扫一遍找这个位置就好了。注意有答案为 0 的情况。
代码
read(n),read(m);
for(int i = 1;i <= n;i ++){
read(a[i]);
if(!cnt[a[i]]) x ++;
cnt[a[i]] ++;
if(x == m){
printf("%d\n",n - i + 1);
return 0;
}
}
printf("0");
return 0;
C
我们枚举 j，令 f_j=\sum\limits_{i=1}^{j-1} A_iA_j，题目所求即为 \sum\limits_{j=1}^nf_j。
根据乘法分配律，f_j=\sum\limits_{i=1}^{j-1} A_iA_j=A_j\times \sum\limits_{i=1}^{j-1} A_i。后面那一项就是前缀和 S_{j-1}，所以求出前缀和数组模拟即可。时间复杂度 O(N)。
代码
read(n);
for(int i = 1;i <= n;i ++){
read(a[i]);
s[i] = s[i - 1] + a[i];
ans += a[i] * s[i - 1];
}
printf("%lld",ans);
return 0;
D
如果只求每一个 d(i,j)，我们可以跑一次多源广搜，起点是所有的 E 处，时间复杂度 O(HW)。
然后我们需要知道每个格子前往最近的 E 要往哪个方向走，本质上就是要知道 d(i,j) 的值是从哪个方向的格子传过来的，所以广搜的时候顺便记录每个格子的最短路从哪个方向来。时间复杂度 O(HW)。
代码
d = {{-1,0},{0,-1},{0,1},{1,0}};
memset(dis,0x3f,sizeof(dis)),read(h),read(w);
for(int i = 1;i <= h;i ++) scanf("%s",s[i] + 1);
for(int i = 1;i <= h;i ++) for(int j = 1;j <= w;j ++) if(s[i][j] == 'E') dis[i][j] = 0,q.push({i,j});//广搜起点
while(q.size()){//广搜
auto [x,y] = q.front();q.pop();
for(int i = 0;i < 4;i ++){
int dx = x + d[i][0],dy = y + d[i][1];
if(dx && dy && dx <= h && dy <= w && s[dx][dy] == '.' && dis[dx][dy] > dis[x][y] + 1)
dis[dx][dy] = dis[x][y] + 1,pre[dx][dy] = i,q.push({dx,dy});//记录最短路和来的方向
}
}
for(int i = 1;i <= h;i ++){
for(int j = 1;j <= w;j ++){
if(s[i][j] == '.') printf("%c",arw[pre[i][j]]);
else printf("%c",s[i][j]);
}
printf("\n");
}
return 0;
E
数学题。
考虑我们先把苹果和香蕉放成一排，苹果是只能放在香蕉左边的，现在序列形如 AAAA...ACCCC...C。
然后我们考虑放葡萄对橘子的影响，由于橘子要在葡萄左边，所以会影响橘子摆放的只有“最左边的葡萄放在哪里”。
我们先放葡萄，枚举“最左边的葡萄左边有多少个水果”，令此值为 i，那么最左边的葡萄右边有 A+C-i 个其他水果，要把这些水果插入葡萄之间的 D 个空隙里。求方案数。
考虑隔板法经典转化，N 个位置放 M 个，每个位置不一定要放 \rightarrow N 个位置放 N+M 个，每个位置一定要放。而这又相当于在 N+M 个物品中间放 N-1 个隔板去划分放在什么位置，两个物品中间只能放一个隔板，因此方案数是 \begin{pmatrix}N+M-1\\N-1\end{pmatrix}，放葡萄这个问题是一样的，方案数是 \begin{pmatrix}A+C+D-i-1\\D-1\end{pmatrix}。
然后在此基础上放橘子，橘子要在左边 i 个苹果和香蕉的中间和两边放，即在 i+1 个位置放 B 个东西，和上面做一样的转化，方案数为 \begin{pmatrix}B+i\\i\end{pmatrix}。
i\in[A,A+C]，答案为 \sum\limits_{i=A}^{A+C}\begin{pmatrix}A+C+D-i-1\\D-1\end{pmatrix}\times\begin{pmatrix}B+i\\i\end{pmatrix}，需要预处理阶乘及逆元，时间复杂度 O(A+B+C+D)。
代码
long long qp(long long a,long long b){if(!b) return 1;long long c = qp(a,b >> 1);c = c * c % MOD;if(b & 1) c = c * a % MOD;return c;}
//快速幂
long long C(long long n,long long m){return fac[n] * inv[n - m] % MOD * inv[m] % MOD;}
//组合数调用函数
fac[0] = 1;
for(int i = 1;i <= 3000000;i ++) fac[i] = fac[i - 1] * i % MOD;inv[3000000] = qp(fac[3000000],MOD - 2);for(int i = 3000000;i;i --) inv[i - 1] = inv[i] * i % MOD;
//预处理阶乘与逆元
read(a),read(b),read(c),read(d);
for(int i = a;i <= a + c;i ++) ans = (ans + C(a + c + d - i - 1,d - 1) * C(b + i,i)) % MOD;
printf("%lld",ans);
return 0;
F
考虑怎么样的线段 (A_i,B_i) 会与线段 (C_j,D_j) 有交，发现它们有交当且仅当 A_i 和 B_i 中有一者在 C_j 和 D_j 中间，而另一个不在。如果我们把 (A_i,B_i) 看作是一个点，一次询问就相当于在问 x<C_j,C_j<y<D_j 或 C_j<x<D_j,y>D_j 的点有多少个，实际上是 离线二维数点问题，可以用归并排序、树状数组或线段树来实现。时间复杂度 O((M+Q)\log N)。
代码
void upd(int x){for(;x <= 2 * n;x += x & -x) tre[x] ++;}//树状数组修改
int Qry(int x){int rtn = 0;for(;x;x -= x & -x) rtn += tre[x];return rtn;}//树状数组查询
read(n),read(m);
for(int i = 1;i <= m;i ++) read(a[i]),read(b[i]),es.emplace_back(a[i],b[i]);
sort(es.begin(),es.end());
read(q);
for(int i = 1;i <= q;i ++){
read(c[i]),read(d[i]);
qry.emplace_back(c[i],c[i],d[i],1,i);
qry.emplace_back(d[i],d[i],2 * n,1,i);
qry.emplace_back(c[i],d[i],2 * n,-1,i);
}
sort(qry.begin(),qry.end());
for(auto [t,l,r,f,w] : qry){
while(it < m && es[it].first <= t) upd(es[it ++].second);
ans[w] += f * (Qry(r) - Qry(l - 1));
}
for(int i = 1;i <= q;i ++) printf("%d\n",ans[i]);
return 0;
G
很有意思的一道题。就是有点卡常。
考虑怎么算一个长为 x 的数列 B 重排能排成多少种样式：当所有 B_i 互不相同时，显然方案为 x!。当其中有一个数重复出现 y 次时，这些数的内部排列会造成 y! 种相同的情况在前面的 x! 种中被视作不同情况，此时方案数为 \frac{x!}{y!}。简单归纳证明得：若一个数 i 在 B 中出现次数为 \text{cnt}_i，则 B 重新排列后的方案数为 \frac{x!}{\prod\limits_{i=1}^N(\text{cnt}_i!)}。
考虑给 \text{cnt}_i 做分块维护，按数字分成 B 块，记录每个数字的 \text{cnt}_i 的同时记录每个块的 \sum \text{cnt}_i 和 \frac{1}{\prod(\text{cnt_i}!)} （模意义下的），对于一次修改（某个数字出现次数 \pm1 ），可以在预处理阶乘及其逆元后 O(1) 修改对应块的信息，而对应的一次查询 (L,R,X)，计算答案只需要把值域 [1,X-1) 的分块维护的两个信息分别整合，信息点有 O(\frac{n}{B}) 个整块和 O(B) 个不在块内的散点，信息加一起，单次询问的复杂度是 O(\frac{n}{B}+B)。取 B=\sqrt{N} 达到平衡，询问复杂度为 O(\sqrt{N})。
考虑莫队维护，给询问的 (L,R) 做莫队排序，均摊要增删 A_i O((N+Q)\sqrt{N}) 次，查询 Q 次的复杂度是 O(Q\sqrt{N})，总时间复杂度 O((N+Q)\sqrt{N})。
代码
long long qp(long long a,long long b){if(!b) return 1ll;long long c = qp(a,b >> 1);c = c * c % MOD;if(b & 1) c = c * a % MOD;return c;}
//快速幂
pre();//处理 N 以下阶乘及逆元
void upd(int x,int f){//x 的出现次数增加 f 造成的影响
int bx = b[x];
snv[bx] = snv[bx] * fct[cnt[x]] % MOD;//去除原先 cnt[x]! 的逆元
cnt[x] += f,sc[bx] += f;
snv[bx] = snv[bx] * inv[cnt[x]] % MOD;//乘回新的 cnt[x]! 的逆元
}
read(n),read(q);
B = 500,cB = (n - 1) / B + 1;
for(int i = 1;i <= cB;i ++) bl[i] = br[i - 1] + 1,br[i] = i * B,snv[i] = 1;
br[cB] = n;
for(int i = 1;i <= cB;i ++) for(int j = bl[i];j <= br[i];j ++) b[j] = i;
for(int i = 1;i <= n;i ++) read(a[i]);
for(int i = 1;i <= q;i++) read(ia),read(ib),read(ic),qry.emplace_back(ia,ib,ic,i);
sort(qry.begin(),qry.end(),[](tuple<int,int,int,int>x,tuple<int,int,int,int>y){
if(b[get<1>(x)] != b[get<1>(y)]) return get<1>(x) < get<1>(y);
if(b[get<1>(x)] & 1) return get<0>(x) < get<0>(y);
return get<0>(x) > get<0>(y);
});//莫队给询问排序
L = 1,R = 0;
for(auto [l,r,x,w] : qry){
while(L > l) upd(a[-- L],1);
while(R < r) upd(a[++ R],1);
while(L < l) upd(a[L ++],-1);
while(R > r) upd(a[R --],-1);//调整 [L,R] 至询问处
int bx = b[x],tmp = 0;
x --;
for(int i = 1;i < bx;i ++) tmp += sc[i];
for(int i = bl[bx];i <= x;i ++) tmp += cnt[i];
ans[w] = fct[tmp];//如果所有元素都不重复出现，那么有 tmp! 种结果
for(int i = 1;i < bx;i ++) ans[w] = ans[w] * snv[i] % MOD;//去除重复元素导致的影响
for(int i = bl[bx];i <= x;i ++) ans[w] = ans[w] * inv[cnt[i]] % MOD;
}
for(int i = 1;i <= q;i ++) printf("%lld\n",ans[i]);
return 0;
撒花