【考试总结】2022-04-12
史莱姆A
设 \(f_i\) 表示前 \(i\) 个元素进行划分得到的 \(f\) 函数之和，转移枚举最后一段划分在哪里
根据 \(a_i\le 10\) 觉得部分可以发现每次转移将 \(\rm mex\) 相同的一起做是减少冗余的一个方式
但是显然可以再给力一些，使用线段树容易在挪动右端点时维护每个左端点为起点时这段的 \(\rm mex\) ，把 \(f\) 值挂到叶子上那么就是区间求和，也能应付 \(\rm mex\) 的修改
被卡常可以将单点修改写成 \(\rm zkw\) 的形式
Code Display
const int mod=998244353;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int mul(int x,int y){return x*y-x*y/mod*mod;}
const int N=1e6+10;
int a[N],n,Q,app[N];
struct node{
int mex,l,r;
bool operator <(const node &a)const{return mexnow;
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
struct segment_tree{
int Mn[N<<2];
inline void push_up(int p){Mn[p]=min(Mn[ls],Mn[rs]);}
inline void modify(int pos,int v,int p=1,int l=0,int r=n){
if(l==r) return Mn[p]=v,void();
int mid=(l+r)>>1;
if(pos<=mid) modify(pos,v,lson);
else modify(pos,v,rson);
return push_up(p);
}
inline int erf(int tar,int v,int p=1,int l=0,int r=n){
if(Mn[p]>tar) return -1;
if(l==r) return l; int mid=(l+r)>>1;
if(v<=l){
if(Mn[ls]<=tar) return erf(tar,v,lson);
return erf(tar,v,rson);
}
if(v>mid) return erf(tar,v,rson);
int res=erf(tar,v,lson);
if(~res) return res; return erf(tar,v,rson);
} //larger than v,backer than tar
}lst;
struct Segment_Tree{
int sum[N<<2],val[N<<2],id[N],cov[N<<2];
inline void build(int p,int l,int r){
cov[p]=-1;
if(l==r) return id[l]=p,void(); int mid=(l+r)>>1;
build(lson); build(rson);
return ;
}
inline void push_cov(int p,int v){
sum[p]=mul(val[p],cov[p]=v);
return ;
}
inline void push_down(int p){
if(~cov[p]){
push_cov(ls,cov[p]);
push_cov(rs,cov[p]);
cov[p]=-1;
} return ;
}
inline void push_up(int p){
val[p]=val[ls]+val[rs];
sum[p]=sum[ls]+sum[rs];
return ;
}
inline int query(int ed,int p=1,int l=1,int r=n){
if(r<=ed) return sum[p];
int mid=(l+r)>>1; push_down(p);
if(ed<=mid) return query(ed,lson);
return query(ed,lson)+query(ed,rson);
}
int st,ed,v;
inline void give_cov(int p=1,int l=1,int r=n){
if(st<=l&&r<=ed) return push_cov(p,v);
int mid=(l+r)>>1; push_down(p);
if(st<=mid) give_cov(lson);
if(ed>mid) give_cov(rson);
return push_up(p);
}
inline void g_cov(int l,int r,int V){
st=l; ed=r; v=V;
give_cov();
}
inline void modify(int pos,int v){
int p=id[pos];
val[id[pos]]=v;
while(p>>=1) push_up(p);
}
}seg;
#undef ls
#undef rs
#undef lson
#undef rson
int dp[N];
signed main(){
freopen("a.in","r",stdin); freopen("a.out","w",stdout);
n=read(); rep(i,1,n) a[i]=read();
seg.build(1,1,n);
seg.modify(1,1);
auto ins=[&](int mex,int l,int r){
auto iter=now.lower_bound({mex,0,0});
if(iter==now.end()){
now.insert({mex,l,r});
return ;
}
int L=iter->l,R=iter->r;
if(iter->mex==mex) now.erase(iter),now.insert({mex,L,r});
else now.insert({mex,l,r});
};
int qcnt=0;
for(int i=1;i<=n;++i){
if(a[i]<=n) app[a[i]]=i,lst.modify(a[i],i);
auto iter=now.lower_bound({a[i],0,0});
if(iter!=now.end()){
if(iter->mex==a[i]){
int L=iter->l,R=iter->r,lastv=iter->mex;
now.erase(iter);
while(L<=R){
++qcnt;
int mex=lst.erf(R,lastv+1),pos=max(app[mex]+1,L);
if(pos<=R){
ins(mex,pos,R);
seg.g_cov(pos,R,mex);
}
lastv=mex;
R=app[mex];
}
}
}
seg.g_cov(i,i,!a[i]);
ins(!a[i],i,i);
dp[i]=seg.query(i)%mod;
if(i
史莱姆B
有一些性质可以加以挖掘：
-
\(a\le b\le c,a\oplus c\ge \min(a\oplus b,b\oplus c)\)
-
\(a\le b,b-a\le a\oplus b\)
此时我们发现 \(S\) 中元素从小到达排序之后只有相邻的元素作为 \((i,j)\) 时才会对答案产生贡献
从 \([0,2^V)\) 枚举 \(x\)，称一个 \(x\) 是“对答案有贡献的” 当且仅当所有 \(y 都满足 \((i+y)\oplus (j+y)>(x+i)\oplus (j+x)\) ，那么对于一对 \((i,j)\) ，对答案有贡献的 \(x\) 只有 \(\Theta(V)\) 个
同时这些 \(x\) 属于 满足让 \(i+x\) 或者 \(j+x\) 的后 \(t\le [1,V]\) 位为 \(0\) 的最小可行数 构成的集合中
其实简单微调 \(x\leftarrow x+k\) ，那么如果另一个数字不产生更高的进位那么一定会更大
所以可以枚举所有 \(t\) 得到可行 \(x\)，由于只有加入数字的操作，那么可以使用 std::set 来维护所有的三元组 \((i,j,x)\) 使得权值在 \(x\) 增加时减小
Code Display
set vals;
map ans;
int V,n;
inline void insert(int x,int y){
auto add=[&](const int x,const int y){
auto iter=ans.upper_bound(x);
if(iter==ans.begin()) ans[x]=y;
else{
--iter;
if(iter->sec<=y) return ;
if(iter->fir==x) iter->sec=y,++iter;
else ++iter,ans[x]=y;
while(iter!=ans.end()){
if(y>iter->sec) break;
++iter;
ans.erase(prev(iter));
}
}
return ;
};
add(0,x^y);
for(int i=1;i<=V;++i){
int z=(1ll<sec);
}else{
int x=read();
vals.insert(x);
auto iter=vals.find(x);
if(iter!=vals.begin()){
insert(*iter,*prev(iter));
}
if(iter!=prev(vals.end())){
insert(*iter,*next(iter));
}
}
}
return 0;
}
史莱姆C
考虑类似 \(\rm LOJ\) 贪玩蓝月 一题的重构思想来维护整个过程，那么直接用 \([0,K-2]\) 来表示当前栈中元素，栈大小不够的时候直接暴力 \(\rm Prim/Kruskal\)
根据 \(\rm Subtask \ 4\) 可以发现需要维护 \([L,0),[0,K-2],[K-1,R]\) 三部分的最小生成树，每次查询进行合并
注意这时候不能使用 \(\rm LCT\) 来维护整个最小生成树，必须分开维护，最后合并。因为这里和线段树分治不同，删边的时候会到达之前没有到达过的状态
本题做法是直接在左右两个部分生成树上面维护 \([0,K-2]\) 元素的虚树，虚树上边权表示真正生成树上路径上的权值最大值
此时并不容易进行加删点，所以对于某个 \(L\) 维护边集为 \([L,0)\) 的出边且关键点为 \([L,L+K-1]\cup [0,K-2]\) 的虚树即可
新加入节点时将 新点连出去的边和上次边界上的虚树边集 使用求出来新的最小生成树，然后再在当前得到的树上 \(\rm DFS\) 来删掉不是关键的点
具体而言，每个点维护是否已经在虚树上/不在的话所在存在关键点的链的链底和链上边权最大值，转移时如果出现链那么让 边集（最小生成树除去虚树）的总权值加上较小者并保留较大者
如果存在分叉则这段链一定在虚树里面，保留较大者并让权值加上较小者
最后计算答案时也是三部分归并
Code Display
inline bool in(int x,int L,int R){return x>=L&&x<=R;}
namespace qwq{
std::mt19937 eng;
void init(int Seed){eng.seed(Seed);}
int readW(){return uniform_int_distribution(0,1000000000)(eng);}
}
const int N=1e6+10;
int anc[N],n,Q,K;
inline int find(int x){return anc[x]==x?x:anc[x]=find(anc[x]);}
vector >G[N];
int down[N],val[N];
int wei[N][23];
int indl,indr,curl,curr,L,R;
struct edge{
int u,v,w; edge(){u=v=w=0;}
edge(int U,int V,int W){u=U; v=V; w=W;}
bool operator <(const edge &E)const{return wtcnt[lst]||(indic1<=curcnt&&curE[indic1]curr) swap(curl,curr);
dfs(x,0,x);
sort(vt[x]+1,vt[x]+tcnt[x]+1);
return ;
}
bool Reb=1;
inline void rebuild(){
Reb=1;
if(R-L=L;--i) insert(i,1);
for(int i=indr+1;i<=R;++i) insert(i,-1);
return ;
}
int vtecnt;
signed main(){
freopen("c.in","r",stdin); freopen("c.out","w",stdout);
qwq::init(read()); K=read(); Q=read();
L=R=indl=indr=Q+1;
int lst=-1,lans=-1;
while(Q--){
int opt=read();
if(opt==1){
++L;
if(L>indl) rebuild();
}
if(opt==2){
--R;
if(R
相关