省选模拟18
A. 货币
考虑对每个右端点维护出最小的左端点在哪 记为 \(f_r\)
那么 \(f_r=\min(i|nxt_i>r)\) ，其中 \(nxt_i\) 表示和 \(i\) 颜色相同的下一个位置
颜色合并可以用启发式合并，插入时修改每一个的 \(nxt\)
考虑 \(u\) 影响的一系列点， \(f_i=u\) 不难发现这样的区间连续
于是可以用一颗线段树二分出影响的区间
根据定义 \(f_r=\min(i|nxt_i>r)\) ，\(i\) 到 \(nxt_i\) 之间的左端点一定都是 \(i\)
可以直接区间赋值，暴力修改影响的区间即可
查询 \(f_i\) 的值也可以用一颗线段树二分查出
Code
#include
//#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define lson rt<<1
#define rson rt<<1|1
#define rint signed
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,q,T,ans;
int nxt[100010],pre[100010];
int fa[100010];
setS[100010],mn;
set::iterator iter;
namespace seg1{
struct seg{int mx;}st[100010*4];
inline void pushup(int rt){st[rt].mx=max(st[lson].mx,st[rson].mx);}
void build(int rt,int l,int r){
if(l==r) return st[rt].mx=n+1,void();
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(rt);
}
int query(int rt,int l,int r,int k){
if(k>st[rt].mx) return n+1;if(l==r) return l;
int mid=(l+r)>>1;
if(st[lson].mx>k) return query(lson,l,mid,k);
else return query(rson,mid+1,r,k);
}
void upd(int rt,int l,int r,int pos,int k){
if(l==r) return st[rt].mx=k,void();
int mid=(l+r)>>1;
if(pos<=mid) upd(lson,l,mid,pos,k);
else upd(rson,mid+1,r,pos,k);
pushup(rt);
}
}
namespace seg2{
struct seg{int mx,mn,tag;}st[100010*4];
inline void pushup(int rt){st[rt].mn=min(st[lson].mn,st[rson].mn);st[rt].mx=max(st[lson].mx,st[rson].mx);}
inline void pushdown(int rt,int l,int r){
int mid=(l+r)>>1;
if(st[rt].tag){
st[lson].mn=min(st[lson].mn,l-st[rt].tag+1);
st[lson].mx=max(st[lson].mx,st[rt].tag);
st[lson].tag=max(st[lson].tag,st[rt].tag);
st[rson].mn=min(st[rson].mn,mid+1-st[rt].tag+1);
st[rson].mx=max(st[rson].mx,st[rt].tag);
st[rson].tag=max(st[rson].tag,st[rt].tag);
st[rt].tag=0;
}
}
void build(int rt,int l,int r){
st[rt].mx=1,st[rt].mn=l;if(l==r) return ;
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
}
int query(int rt,int l,int r,int k){
if(l==r){if(st[rt].mx>1;pushdown(rt,l,r);
if(st[lson].mx>=k) return query(lson,l,mid,k);
else return query(rson,mid+1,r,k);
}
void upd(int rt,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
st[rt].tag=max(k,st[rt].tag);
return st[rt].mx=max(st[rt].mx,k),st[rt].mn=min(st[rt].mn,l-k+1),void();
}
int mid=(l+r)>>1;pushdown(rt,l,r);
if(L<=mid) upd(lson,l,mid,L,R,k);
if(R>mid) upd(rson,mid+1,r,L,R,k);
pushup(rt);
}
int qmn(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R) return st[rt].mn;
int mid=(l+r)>>1,res=n;pushdown(rt,l,r);
if(L<=mid) res=min(res,qmn(lson,l,mid,L,R));
if(R>mid) res=min(res,qmn(rson,mid+1,r,L,R));
return res;
}
}
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
inline void upd(int x,int y){
nxt[x]=y;if(!pre[y]) pre[y]=x,mn.erase(y);
seg1::upd(1,1,n,x,y);
int l=seg2::query(1,1,n,x),r=seg2::query(1,1,n,x+1)-1,pos;
while(l<=r){
pos=seg1::query(1,1,n,l);
seg2::upd(1,1,n,l,min(r,nxt[pos]-1),pos);
l=nxt[pos];
}
}
inline void merge(int x,int y){
x=getfa(fa[x]),y=getfa(fa[y]);
if(x==y) return ;
if(S[x].size()>S[y].size()) swap(x,y);fa[x]=y;
for(auto L:S[x]){
S[y].insert(L);
iter=S[y].find(L);if(iter!=S[y].begin()){iter--;upd(*iter,L);}
iter=++S[y].find(L);if(iter!=S[y].end()){upd(L,*iter);}
}
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("currency.in", "r", stdin);
freopen("currency.out", "w", stdout);
n=read(),q=read(),T=read();
for(int i=1;i<=n;i++) S[i].insert(i),mn.insert(i),fa[i]=i,nxt[i]=n+1;
seg1::build(1,1,n);seg2::build(1,1,n);
for(int i=1,x,y;i<=q;i++){
x=(read()+ans*T-1)%n+1;
y=(read()+ans*T-1)%n+1;
merge(x,y);
printf("%d\n",ans=seg2::qmn(1,1,n,*mn.rbegin(),n));
}
return 0;
}
B. 比赛
只会暴力修改
C. 字符串
不难发现 \(Fail\) 树空串代表的节点每个子树的颜色都相同，不同子树颜色一定不同
于是只用检验合不合法
一种不会证明的 \(O(n)\) 做法是在 \(Trie\) 树上 \(bfs\) 检验
同一节点儿子的颜色一定都不同，而且在 \(Fail\) 树上的深度不能高于儿子的深度 \(-1\)
另一种没有实现的 \(O(n)\) 可以直接在 \(Fail\) 树上 \(dfs\)
并且枚举在 \(Trie\) 树上的儿子，看看祖先链上第一个有颜色为 \(c\) 的儿子是不是那个儿子在 \(Fail\) 树上的父亲
加入的时候修改，回溯的时候撤销修改就行
Code
#include
//#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,rt;
int q[300010],h,t;
int c[300010],col,jud[300010];
int deg[300010];
bool vis[300010];
mapmp[300010];
struct E{int x,y;}L[300010];
namespace Trie{
int dep[300010],mxd;
int head[300010],ver[600010],to[600010],tot;
inline void add(int x,int y){ver[++tot]=y;to[tot]=head[x];head[x]=tot;}
void dfs(int x,int fa,int depth){
dep[x]=depth;
for(int i=head[x];i;i=to[i]){
int y=ver[i];if(y==fa) continue;
dfs(y,x,depth+1);
}
}
}
namespace Fail{
int dep[300010],fa[300010],mxd;
int head[300010],ver[600010],to[600010],tot;
inline void add(int x,int y){ver[++tot]=y;to[tot]=head[x];head[x]=tot;}
void dfs(int x,int fath,int depth){
fa[x]=fath,dep[x]=depth;
for(int i=head[x];i;i=to[i]){
int y=ver[i];if(y==fath) continue;
dfs(y,x,depth+1);
}
}
}
inline bool bfs(int S){
col=0;for(int i=1;i<=n;i++) c[i]=0,jud[i]=0,vis[i]=0;
q[h=t=1]=S;
while(h<=t){
int x=q[h++];vis[x]=1;
for(int i=Trie::head[x];i;i=Trie::to[i]){
int y=Trie::ver[i];if(vis[y]) continue;
if(Fail::fa[y]!=S&&jud[Fail::fa[y]]==x) return false;jud[Fail::fa[y]]=x;
//if(Fail::fa[y]!=S&&!c[Fail::fa[y]]) return false;
if(Fail::fa[y]!=S&&Fail::dep[x]y) swap(x,y);mp[x][y]=1;}
for(int i=1,x,y;iy) swap(x,y);if(mp[x].find(y)!=mp[x].end()) deg[x]++,deg[y]++;}
for(int i=1;i<=n;i++) if(deg[i]>=3) rt=i;
if(rt){
Trie::dfs(rt,0,1);Fail::dfs(rt,0,1);
bfs(rt);printf("%d\n",rt);
for(int i=1,x,y;iTrie::dep[y]) printf("%d ",c[x]);
else printf("%d ",c[y]);
}exit(0);
}else{
int C=0;
for(int i=1,x;i<=n;i++) if(deg[i]==1||deg[i]==2){
rt=i;
Trie::dfs(rt,0,1);Fail::dfs(rt,0,1);
if(bfs(rt)){
printf("%d\n",rt);cerr<Trie::dep[y]) printf("%d ",c[x]);
else printf("%d ",c[y]);
}exit(0);
}
}
}
return 0;
}