【考试总结】2022-02-20
货币
设 \(f_r\) 表示 \(r\) 为右端点时的最大左端点（如果没有则为 \(+\infty\)）表达式是 \(f_r=\min\{p|next_p>r\}\)，
使用 std::set 启发式维护所有点的 \(next\)，考虑当某个 \(next_i\) 从 \(x\) 变成 \(y\) 时 \(f_r\) 的变化，找到原来满足 \(f_a=x\) 的 \(a\in[l,r]\)，不难发现有且仅有 \(a\in [l,r]\) 的 \(f_a\) 会发生变化
根据实际含义 \(a\in [x,next_x)\) 中的 \(f_a=x\) 在 \(next_x\) 改变之后会变成同样的一个值，那么这时候可以迭代更新 \(f_a\)
具体实现的时候维护区间 \(next\) 的大值之后线段树上二分就能快速得到 \(f_a\) 的数值和需要更改的确切区间
注意 \(f_a\) 是单调不降的，同时在修改的过程中不同 段的合并 也只会产生 \(\Theta(n)\) 次，也就是说让增加的部分和后面一部分相等
而段的分裂是付出 \(\Theta(\log)\) 的复杂度就会造成新段产生的，所以时间复杂度 \(\Theta(n\log^2n)\)
一种可能的实现是大标号的集合往小标号的集合合并来增加合法右端点数量
Code Display
const int N=3e5+10;
int n,Q,typ,lans,Mn;
set nds[N];
struct DSU{
int fa[N];
inline void init(){rep(i,1,n) fa[i]=i; return ;}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
}T;
int mx[N<<2],nxt[N];
#define ls p<<1
#define rs p<<1|1
inline void Modify(int pos,int v,int p=1,int l=0,int r=n+1){
if(l==r) return nxt[l]=mx[p]=v,void(); int mid=(l+r)>>1;
if(pos<=mid) Modify(pos,v,ls,l,mid);
else Modify(pos,v,rs,mid+1,r);
mx[p]=max(mx[ls],mx[rs]); return ;
}
inline int Query(int st,int ed,int p=1,int l=0,int r=n+1){
if(ed>1;
if(ed<=mid) return Query(st,ed,ls,l,mid);
if(st>mid) return Query(st,ed,rs,mid+1,r);
return max(Query(st,ed,ls,l,mid),Query(st,ed,rs,mid+1,r));
}
inline int Find(int val,int p=1,int l=0,int r=n+1){
if(l==r) return l; int mid=(l+r)>>1;
if(mx[ls]>val) return Find(val,ls,l,mid);
else return Find(val,rs,mid+1,r);
}
#undef ls
#undef rs
inline void solve(int pos,int val){
int Rbound=nxt[pos],tmp=0;
Modify(pos,val);
int rig=max(val,Query(0,pos-1));
while(tmp<=n&&nxt[tmp]<=Rbound){
tmp=Find(rig);
ckmin(Mn,rig-tmp+1);
rig=nxt[tmp];
}
return ;
}
signed main(){
freopen("currency.in","r",stdin); freopen("currency.out","w",stdout);
Mn=n=read(); Q=read(); typ=read();
for(int i=1;i<=n;++i) Modify(i,2e5),nds[i].insert(i);
Modify(0,n),Modify(2e5,2e5);
T.init();
while(Q--){
int u=(read()+lans*typ-1)%n+1,v=(read()+lans*typ-1)%n+1;
u=T.find(u); v=T.find(v);
if(u==v){
print(lans=Mn);
continue;
}
if(u>v) swap(u,v);
if(nds[u].size()::iterator it=nds[u].find(t);
if(it!=nds[u].begin()){
--it;
solve(*it,t);
++it;
}
if(it!=prev(nds[u].end())){
++it;
solve(t,*it);
}
}
nds[v].clear();
T.fa[v]=u;
int pter=nxt[0];
while(nds[pter].size()==0) --pter;
solve(0,pter); //furtherest first apperance
print(lans=Mn);
}
return 0;
}
比赛
如果满足 \(0
设 \(f_i\) 表示如果变量 \(x\) 走到 \(i\) 的时候满足 \(x=i-a_i\) 那么 \(i\) 是否操作，本质上就是用上面的树 \(\rm DP\)，如果操作那么 \(f_i=1\)
如果 \(f_0=1\) 答案是 \(0\)，否则是 \(\min\{p|f_{p}=1,a[p]=p\}\)，所以可以使用 std::set 维护所有 \(\rm DP\) 值是 \(1\) 的儿子
考虑修改 \(a_i\) 会给一条链上的点翻转 \(\rm DP\) 值，那么可以使用 LCT 维护森林，模拟 \(\rm Link-Cut\) 的过程即可，二分的条件也是是不是存在虚儿子的 \(\rm DP\) 值为 \(1\)
同时如果二分的时候修改的链延伸到了 \(0\) 或者 \(a[p]=p\) 的点，根据 \(\rm splay\) 上的后继更改 set 即可
这里比较主要的细节如下
-
断边 \((x,x-a[x])\) 的时候要先
access(x) -
注意
access时候 被更改的rs[x]不一定是 \(x\) 的后继，需要找后继 -
跳轻边修改信息的时候，原来的轻儿子不是 \(x\)，而是 \(x\) 所在 \(\rm splay\) 上的最浅点
Code Display
const int N=3e5+10;
setcurson;
int n,Q,a[N],dp[N];
int ls[N],rs[N],fa[N],img[N],si[N],revdp[N];
inline bool isroot(int x){return (ls[fa[x]]!=x&&rs[fa[x]]!=x);}
inline void push_up(int x){
si[x]=si[ls[x]]+si[rs[x]]+img[x];
return ;
}
inline void push_down(int x){
if(revdp[x]){
if(ls[x]) dp[ls[x]]^=1,revdp[ls[x]]^=1;
if(rs[x]) dp[rs[x]]^=1,revdp[rs[x]]^=1;
revdp[x]=0;
}
return ;
}
inline void rotate(int x){
int y=fa[x],z=fa[y]; if(!isroot(y)) if(ls[z]==y) ls[z]=x; else rs[z]=x;
if(ls[y]==x) ls[y]=rs[x],fa[rs[x]]=y,rs[x]=y;
else rs[y]=ls[x],fa[ls[x]]=y,ls[x]=y;
fa[y]=x; fa[x]=z;
ls[0]=rs[0]=fa[0]=0;
return push_up(y),push_up(x);
}
int stk[N],top;
inline void splay(int x){
int y=x; stk[top=1]=y;
while(!isroot(y)) stk[++top]=y=fa[y];
while(top) push_down(stk[top--]);
while(!isroot(x)){
int y=fa[x],z=fa[y];
if(!isroot(y)) rotate(((ls[y]==x)^(ls[z]==y))?x:y);
rotate(x);
} return ;
}
inline void access(int x){
for(int y=0;x;x=fa[y=x]){
splay(x);
int e=rs[x]; while(ls[e]) push_down(e),e=ls[e];
if(y){
splay(y);
int tmp=y;
while(ls[tmp]) push_down(tmp),tmp=ls[tmp];
img[x]-=dp[tmp];
}
if(e) img[x]+=dp[e];
rs[x]=y;
if(e) splay(e);
push_up(x);
} return ;
}
vector G[N];
inline void dfs(int x){
dp[x]=0;
for(auto t:G[x]){
dfs(t),dp[x]|=dp[t],img[x]+=dp[t];
}
dp[x]^=1;
return ;
}
inline void Answer(){
if(curson.size()) assert(dp[1]==0),print((*curson.begin())-1);
else print(0);
return ;
}
signed main(){
freopen("match.in","r",stdin); freopen("match.out","w",stdout);
n=read(); Q=read();
rep(i,1,n){
a[i]=read();
if(a[i]&&a[i]+1<=i) G[fa[i]=i-a[i]].push_back(i);
}
memset(dp,-1,sizeof(dp)); dp[0]=0;
for(int i=1;i<=n;++i) if(dp[i]==-1) dfs(i);
for(auto t:G[1]) if(dp[t]) curson.insert(t);
Answer();
while(Q--){
int x=read()+1,y=read();
if(a[x]==y){Answer(); continue;}
if(curson.count(x)) curson.erase(curson.find(x));
if(a[x]&&a[x]+1<=x){
//exist father
int Fa=x-a[x];
access(x);
access(x-a[x]); splay(x-a[x]);
splay(x);
if(dp[x]){
img[Fa]--,push_up(Fa);
if(!img[Fa]){
int now=x-a[x],tar=Fa;
while(now){
push_down(now);
if(!si[rs[now]]&&!img[now]) tar=now,now=ls[now];
else now=rs[now];
}
splay(tar);
dp[tar]^=1;
if(rs[tar]) revdp[rs[tar]]^=1,dp[rs[tar]]^=1;
if(tar>1&&a[tar]+1==tar){
if(dp[tar]) curson.insert(tar);
else if(curson.count(tar)) curson.erase(curson.find(tar));
}else if(tar==1){
if(dp[1]) curson.clear();
else{
splay(1);
if(rs[1]){
int e=rs[1];
while(ls[e]) push_down(e),e=ls[e];
curson.insert(e);
}
}
}
}
} fa[x]=0;
}
a[x]=y;
if(a[x]&&a[x]+1<=x){
//Get a New father
int Fa=x-a[x];
access(Fa); splay(Fa);
splay(x);
if(dp[x]){
if(img[Fa]) img[Fa]++,push_up(Fa);
else{
int now=x-a[x],tar=Fa;
while(now){
push_down(now);
if(!si[rs[now]]&&!img[now]) tar=now,now=ls[now];
else now=rs[now];
}
splay(tar);
dp[tar]^=1;
if(rs[tar]) revdp[rs[tar]]^=1,dp[rs[tar]]^=1;
if(tar>1&&a[tar]+1==tar){
if(dp[tar]) curson.insert(tar);
else if(curson.count(tar)) curson.erase(curson.find(tar));
}else if(tar==1){
if(dp[tar]) curson.clear();
else{
splay(1);
if(rs[1]){
int e=rs[1];
while(ls[e]) push_down(e),e=ls[e];
curson.insert(e);
}
}
}
splay(Fa);
img[Fa]++; push_up(Fa);
}
if(Fa==1) curson.insert(x);
} fa[x]=Fa;
}
Answer();
}
return 0;
}
字符串
如果固定一个根，考虑如何判断是不是存在合法方案
考虑将边划分成若干等权类，每个等权类内部使用相同的边权
不难发现在确定根的情况下找到每个点的父亲，这样子每个点在 fail 树父亲 在 trie 树上返祖边和这个点本身的返祖边权值相同，可以使用并查集缩起来
求出来等权类之后如果某个点两个出边在一个等权类就不合法了
逐个枚举根判断可以得到一个复杂度为 \(\Theta(n^2)\) 的做法
那么考虑根究竟可以是什么样子的节点：
找到 trie 树和 fail 树边的交集，根据实际含义发现交集中点数大于 \(1\) 的连通块个数一定为 \(1\)
这是因为根的所有出边一定在交集中，所以一定存在点数大于 \(1\) 的连通块；而找到真正的根后发现，连通块中的每个节点 \(x\) 的根链对应一个长度为 \(dep_x\) 的全等串，或者理解为 存在长度为 \(n-1\) 的 \(\rm border\) 的字符串
那么和根不连通非孤点连通块一定不满足实际含义
由于有且仅有全等串存在长度为 \(len-1\) 的 \(\rm border\)，那么非根节点一定在交树上度数小于 \(2\)，这时如果存在一个点度数超过 \(2\) 那么可以直接判定其为根
如果交树形成了一条链，那么找其中每个点 \(x\) trie 树上的邻居 \(nei\) 在 fail 树上的邻居 \(t\)（断句方式已由空格标识），如果存在 \(t\) 也在链上，那么说明根和 \(t\) 在链上的距离不超过 \(1\)
（其实只有两种情况：\(t\) 直接是 根 或是 根的非 \(x\) 向儿子）
枚举至多三个点判断即可
Code Display
const int N=3e5+10;
int n;
struct Graph{
vector g[N];
map,int>mp;
int ecnt,val[N];
inline void insert(int u,int v){
g[u].push_back(v); g[v].push_back(u);
if(u>v) swap(u,v);
mp[make_pair(u,v)]=++ecnt;
return ;
}
inline int query(int x,int y){
if(x>y) swap(x,y);
return mp.count(make_pair(x,y))?mp[make_pair(x,y)]:0;
}
int fa[N];
inline void get_fa(int x,int fat){
fa[x]=fat;
for(auto t:g[x]) if(t!=fat) get_fa(t,x);
return ;
}
inline bool check(int x,int fat){
set app;
for(auto t:g[x]) if(fat!=t&&!check(t,x)) return 0;
for(auto t:g[x]) if(t!=fat){
int id=query(x,t);
if(app.count(val[id])) return 0;
app.insert(val[id]);
}
return 1;
}
}trie,fail;
vector cap[N];
bool mark[N];
struct DSU{
int fa[N];
inline void init(){rep(i,1,n) fa[i]=i;}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y){return fa[find(x)]=find(y),void();}
}dsu;
inline bool Construct(int x){
dsu.init();
trie.get_fa(x,0);
fail.get_fa(x,0);
rep(i,1,n) if(i^x){
int a1=i,b1=trie.fa[i];
int a2=fail.fa[i],b2=trie.fa[a2];
if(a1&&b1&&a2&&b2){
int id1=trie.query(a1,b1);
int id2=trie.query(a2,b2);
dsu.merge(id1,id2);
}
}
int ecnt=0;
rep(i,1,n-1) if(dsu.find(i)==i) trie.val[i]=++ecnt;
rep(i,1,n-1) trie.val[i]=trie.val[dsu.find(i)];
if(!trie.check(x,0)) return 0;
print(x); putchar('\n');
rep(i,1,n-1) print(trie.val[i]); putchar('\n');
return 1;
}
signed main(){
freopen("string.in","r",stdin); freopen("string.out","w",stdout);
n=read();
for(int i=1;i2) Construct(i),exit(0);
rep(i,1,n) mark[i]=cap[i].size();
rep(i,1,n) if(mark[i]){
for(auto x:trie.g[i]) if(!mark[x]){
for(auto t:fail.g[x]) if(mark[t]){
if(Construct(t)) exit(0);
for(auto y:cap[t]) if(Construct(y)) exit(0);
assert(0);
}
}
}
return 0;
}