CF1858B The Walkway
降智题，但是这种题放B着实有点恶心
考虑每两个相邻点对\(x\),\(y\)对于答案的贡献，显然是\(\frac{s_y-s_x-1}{d}\)
然后每次枚举删除的点\(i\)，减去\((i-1,i)\),\((i+1,i)\)的贡献，再加上\((i-1,i+1)\)的贡献就是可能的答案
但是实现的时候细节很多，主要是两个端点不好处理，一种比较简单的实现方法是将\(1-d\)和\(n+1\)加入点集再特判即可
\(code\):
点击查看代码
#include<bits/stdc++.h>
using namespace std;
template <class T>
void read(T &x){
x=0;char c=getchar();bool f=0;
while(!isdigit(c)) f=c=='-',c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x=f? (-x):x;
}
#define ll long long
const int MAXN=2e5+5;
int T,n,m,d,s[MAXN];
int calc(int x,int y){
return (s[y]-s[x]-1)/d;
}
int main(){
read(T);
while(T--){
read(n);read(m);read(d);
for (int i=1;i<=m;i++) read(s[i]);
s[++m]=1-d,s[++m]=n+1;
sort(s+1,s+1+m);
int ans=0;
for (int i=2;i<=m;i++){
ans+=(s[i]-s[i-1]-1)/d;
}
ans+=m-2;
int mn=0x3f3f3f3f;
int cnt=0;
for (int i=2;i<m;i++){
int cur=calc(i-1,i+1)-calc(i-1,i)-calc(i,i+1);
if (cur<mn){
mn=cur;
cnt=1;
}
else if (cur==mn) cnt++;
}
printf("%d %d\n",ans+mn-1,cnt);
}
}
CF1858 E1. Rollbacks (Easy Version)
赛后听神加哥讲完后还是感觉非常套路的。。。
对于这种带有回退的问题，考虑建出树形结构，每次加入一个点时直接新建节点往下走并预处理\(k\)级祖先，删除时直接往上跳\(k\)级祖先，回退时用之前加入和删除时栈中记录的在树中的位置回溯，询问直接挂在树上。最后一次\(dfs\)即是答案。
对于\(E2\)强制在线，发现对每个询问其实能产生贡献的只有它到根节点的一条链，直接维护这条链上的信息即可。但是懒得写了
点击查看代码
#include<bits/stdc++.h>
using namespace std;
template <class T>
void read(T &x){
x=0;char c=getchar();bool f=0;
while(!isdigit(c)) f=c=='-',c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x=f? (-x):x;
}
const int MAXN=1e6+5;
int m,qcnt;
int ans[MAXN];
struct Query{
char op;
int x,id;
}q[MAXN];
vector <int> G[MAXN];
vector <int> Q[MAXN];
int tot,u,a[MAXN],fa[MAXN][24];
void init(int u,int f){
fa[u][0]=f;
for (int i=1;i<24;i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
}
int kth(int u,int k){
for (int i=0;i<24;i++){
if (k&(1<<i)) u=fa[u][i];
}
return u;
}
int st[MAXN],top;
int bucket[MAXN],res;
void dfs(int u){
for (const auto &x:Q[u]) ans[x]=res;
for (const auto &v:G[u]){
if (++bucket[a[v]]==1) res++;
dfs(v);
if (--bucket[a[v]]==0) res--;
}
}
void solve(){
u=1;tot=1;
for (int i=1;i<=m;i++){
if (q[i].op=='+'){
st[++top]=u;
++tot;
G[u].push_back(tot);
a[tot]=q[i].x;
init(tot,u);
u=tot;
}
else if (q[i].op=='-'){
st[++top]=u;
u=kth(u,q[i].x);
}
else if (q[i].op=='!'){
u=st[top--];
}
else Q[u].push_back(q[i].id);
}
dfs(1);
}
int main(){
read(m);
for (int i=1;i<=m;i++){
char op[5];
scanf("%s",(op+1));
q[i].op=op[1];
if (op[1]=='+'||op[1]=='-') read(q[i].x);
if (op[1]=='?') ++qcnt,q[i].id=qcnt;
}
solve();
for (int i=1;i<=qcnt;i++) printf("%d\n",ans[i]);
}