[Contest on 2022.4.12] 我又来水博客了
这场比赛的题目名真的太不走心了。
\(\cal T_1\) 史莱姆 \(\rm A\)
\(\mathbb{Description}\)
史莱姆有一串长度为 \(n\) 的彩灯，其中第 \(i\) 盏彩灯的颜色为 \(a_i\).
史莱姆将这串彩灯剪成若干段并装饰在房间里，每一段彩灯的美丽度为这段彩灯的颜色形成的集合的 \(\rm mex\)。由于彩灯之间的奇特相互作用，整个房间的美丽度为每段彩灯的美丽度的积。史莱姆想知道所有剪彩灯的方案的美丽度之和是多少。答案对 \(998244353\) 取模。
\(n\le 10^6,0\le a_i\le n\).
\(\mathbb{Solution}\)
首先可以想到 \(dp_i=\sum dp_j\cdot \text{mex}(j+1,i)\)，然后我就死了：先开始想 \(\rm mex\) 有易撤销的性质，所以考虑用贡献法，将 \(dp_j\) 乘上系数贡献到后面的 \(\mathtt{dp}\) 值，但问题是 \(\text{mex}(j+1,i)\) 显然在 \(j\) 增加的时候会改变，无法维护（虽说修改时是区间赋值，但事实上这个操作并没有区间乘/加好做）。
既然区间赋值不好做，我们能否考虑将 \(\rm mex\) 相同的 \(\mathtt{dp}\) 值分类处理呢？显然对于右端点固定的 \(\rm mex\) 值是单调不升的，每个 \(\rm mex\) 值就统治了一段区间 \([L_i,R_i]\). 假设加入 \(a_i\)，我们找到 \(a_i\) 对应的区间 \([L,R]\)，显然只有这一段区间的 \(\rm mex\) 值会受到影响：先找到 \([R,i]\) 的 \(\rm mex\)，设其为 \(k\)，我们找到 \(i\) 之前第一个值为 \(k\) 的位置 \(p\)，那么 \([p+1,R]\) 的 \(\rm mex\) 就都更改为 \(k\)，然后接着递归下去即可。
一个需要注意的点是 \(dp_j\) 和 \(\text{mex}(j+1,i)\) 的下标相差 \(1\)，方便的方法是直接令 \(dp_1=1\)，也就是将 \(\mathtt{dp}\) 值整体右移了一位。
时间复杂度？考虑每次至多删除一种 \(\rm mex\) 值，而总共有 \(n+1\) 种 \(\rm mex\) 值，所以是 \(\mathcal O(n\log n)\) 的。
\(\mathbb{Code}\)
#include
#define print(x,y) write(x),putchar(y)
template
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' || s<'0')
f |= (s=='-');
while(s>='0' && s<='9')
x = (x<<1)+(x<<3)+(s^48),
s = getchar();
return f?-x:x;
}
template
inline void write(T x) {
static int writ[50],tp=0;
if(x<0) putchar('-'),x=-x;
do writ[++tp] = x-x/10*10, x/=10; while(x);
while(tp) putchar(writ[tp--]^48);
}
# include
using namespace std;
const int maxn = 1e6+5;
const int mod = 998244353;
inline int dec(int x,int y) { return x-y<0?x-y+mod:x-y; }
inline int inc(int x,int y) { return x+y>=mod?x+y-mod:x+y; }
int L[maxn],R[maxn],node[maxn],las[maxn];
int n,a[maxn],dp[maxn],ans,mn[maxn<<2];
void build(int o,int l,int r) {
if(l==r) return node[l]=o, void();
int mid = l+r>>1;
build(o<<1,l,mid); build(o<<1|1,mid+1,r);
}
void modify(int p,int k) {
mn[p=node[p]] = k;
while(p>>=1) mn[p] = min(mn[p<<1],mn[p<<1|1]);
}
int ask(int o,int l,int r,int p) {
if(l==r) return r; int mid = l+r>>1;
return mn[o<<1] \(\cal T_2\)
\(\mathbb{Description}\)
\(\mathbb{Solution}\)
\(\mathbb{Code}\)
\(\cal T_3\) 史莱姆 \(\rm C\)
\(\mathbb{Description}\)
史莱姆有一张无向图，最开始图仅有 \(0\) 号节点。现在有 \(n\) 次操作，每次操作为以下 \(5\) 种之一（不妨假设每次操作前这张图的节点编号区间为 \([l,r]\)）：
- 删去 \(l\) 号节点，并删去 \(l\) 号节点连接的所有边；
- 删去 \(r\) 号节点，并删去 \(r\) 号节点连接的所有边；
- 增加 \(l-1\) 号节点，并连接 \(\min\{k-1,r-l+1\}\) 条边，第 \(i\) 条边连接 \(l-1,l-1+i\)，边有边权；
- 增加 \(r+1\) 号节点，并连接 \(\min\{k-1,r-l+1\}\) 条边，第 \(i\) 条边连接 \(r+1,r+1-i\)，边有边权。
- 对当前图询问最小生成树的边权和。
输入保证任意时刻 \(l\le r\).
\(2\le k\le 10, n\le 5\cdot 10^5\).
\(\mathbb{Solution}\)
不会正解，所以写了一发 \(\rm lct\)，结果草过去了 /xk.
\(\mathbb{Code}\)
# include
# include
# define print(x,y) write(x), putchar(y)
template
inline T read(const T sample) {
T x=0; char s; bool f=0;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template
inline void write(T x) {
static int writ[50], w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp]=x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}
# include