头像

limie

$\color{green}{xx6nj}$




离线:5小时前


最近来访(1000)
用户头像
Cccccc_ddd
用户头像
宇宙有边
用户头像
垫底抽風
用户头像
acwing_gza
用户头像
yxc的小迷妹
用户头像
Cold_heartless
用户头像
我要AK
用户头像
ㅤ_988
用户头像
征途者
用户头像
风._8
用户头像
yxc
用户头像
violet_garden
用户头像
gsc0618
用户头像
熬夜波比
用户头像
汉之广矣不可泳思
用户头像
理想主义者
用户头像
ghw2008
用户头像
tuffynibbles
用户头像
清风qwq
用户头像
Finn2009

分享 班长题解

limie
17小时前
此题是一个并查集的应用题,也不难,只是有一个不太常用的操作——并查集的换根操作。

观察题目,发现3个操作分别是

  1. 将两个集合合并,并将新集合的代表元素设为第二个集合的代表元素
  2. 将一个集合的代表元素换成另一个
  3. 查询一个集合的代表元素

其中1、3两个操作是可以用并查集轻松实现的(根结点为代表元素即可),但是2操作就不太好做了,这也是本题的重点——换根。
换根意思就是将并查集的根换为另一个节点 废话,字面都能看出来,那如何操作呢?看下面这个图

网页捕获_25-11-2022_233752_.jpeg

看了这个图,换根操作也不难李姐理解了,用代码写出来就是这样的

int pa=find(a);
p[pa]=a,p[a]=a;

剩下代码就留给大家自行补齐

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[100010];
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
void turn_root(int a)
{
    int pa=find(a);
    p[pa]=a,p[a]=a;
}
int main()
{
    int i;
    cin>>n>>m;
    for(i=1;i<=n;i++)p[i]=i;
    while(m--){
        int t,a,b;
        cin>>t>>a;
        if(t==1){
            cin>>b;
            int pa=find(a),pb=find(b);
            p[pa]=pb;
        }
        else if(t==2)turn_root(a);
        else cout<<find(a)<<endl;
    }
}


活动打卡代码 AcWing 2714. 左偏树

limie
1天前

除了树状数组以外的最好写的高级数据结构

#include<bits/stdc++.h>
using namespace std;
int n;
int v[200010],dist[200010],l[200010],r[200010],idx;
int p[200010];
bool cmp(int x,int y)
{
    if(v[x]!=v[y])return v[x]<v[y];
    return x<y;
}
int find(int x)
{
    if(p[x]!= x)p[x]=find(p[x]);
    return p[x];
}
int merge(int x, int y)
{
    if(!x||!y)return x+y;
    if(cmp(y,x))swap(x, y);
    r[x]=merge(r[x],y);
    if(dist[r[x]]>dist[l[x]])swap(l[x],r[x]);
    dist[x]=dist[r[x]]+1;
    return x;
}
int main()
{
    cin>>n;
    v[0]=INT_MAX;
    while(n--){
        int t,x,y;
        cin>>t>>x;
        if(t==1){
            v[++idx]=x;
            dist[idx]=1;
            p[idx]=idx;
        }
        else if(t==2){
            cin>>y;
            x=find(x),y=find(y);
            if(x!=y){
                if(cmp(y,x))swap(x,y);
                p[y]=x;
                merge(x,y);
            }
        }
        else if(t==3)cout<<v[find(x)]<<endl;
        else{
            x=find(x);
            if(cmp(r[x],l[x]))swap(l[x],r[x]);
            p[x]=l[x],p[l[x]]=l[x];
            merge(l[x],r[x]);
        }
    }
}


分享 班长

limie
1天前

题目描述

小L是某学校的一名学生,现在$6$年级,整个$6$年级共有$n$人。他们学校每过一段时间就会对班级进行一些操作,令小L很是头疼。经过一段时间的仔细观察,小L发现操作有$2$种:

  1. 将学生a所在的x班与b所在的y班合并,新班的班长会是y班的班长,表示为1 a b
  2. 将学生a所在班的班长换成a,表示为2 a

小L还发现一开始所有班都只有一人,也就是一开始有$n$个班,现在小L有些疑问,学生$a$所在班的班长是谁?表示为3 a。小L发现自己会做这道题,但是他要准备应付期末考,就只好让请你来回答了,快帮帮他吧!

输入格式

$第一行输入两个整数n,m,表示有n名同学,共有m次操作与询问。$
$接下来m行,每行一个操作命令,如题所述。$

输出格式

对于每个询问,输出一个整数,占一行,表示班长是谁。

数据范围

$n,m<=100000$

输入数据

5 6
1 1 4
1 1 2
2 4
3 1
1 3 5
3 3

输出数据

4
5


活动打卡代码 AcWing 918. 软件包管理器

limie
4天前
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100010];
int h[100010],e[200010],ne[200010],idx;
int id[100010],top[100010],c;
int dep[100010],sz[100010],fa[100010],son[100010];
struct Node{
    int l,r;
    int c0;
    int v;
}tr[400010];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int father,int depth)
{
    dep[u]=depth,sz[u]=1,fa[u]=father;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father)continue;
        dfs1(j,u,depth+1);
        sz[u]+=sz[j];
        if(sz[son[u]]<sz[j])son[u]=j;
    }
}
void dfs2(int u,int t)
{
    id[u]=++c,top[u]=t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa[u]||j==son[u])continue;
        dfs2(j,j);
    }
}
void pushup(int u)
{
    tr[u].c0=tr[u<<1].c0+tr[u<<1|1].c0;
}
void pushdown(int u)
{
    if(tr[u].v){
        if(tr[u].v==1)tr[u<<1].c0=0,tr[u<<1].v=1;
        else tr[u<<1].c0=tr[u<<1].r-tr[u<<1].l+1,tr[u<<1].v=2;
        if(tr[u].v==1)tr[u<<1|1].c0=0,tr[u<<1|1].v=1;
        else tr[u<<1|1].c0=tr[u<<1|1].r-tr[u<<1|1].l+1,tr[u<<1|1].v=2;
        tr[u].v=0;
    }
}
void build(int u,int l,int r)
{
    tr[u]={l,r};
    if(l==r)tr[u].c0=1;
    else{
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int l,int r,int t)
{
    if(l<=tr[u].l&&tr[u].r<=r){
        if(t==1)tr[u].c0=0;else tr[u].c0=tr[u].r-tr[u].l+1;
        tr[u].v=t;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=mid)modify(u<<1,l,r,t);
    if(mid<r)modify(u<<1|1,l,r,t);
    pushup(u);
}
int query(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r)return tr[u].c0;
    int mid=tr[u].l+tr[u].r>>1,s=0;
    pushdown(u);
    if(l<=mid)s=query(u<<1,l,r);
    if(mid<r)s+=query(u<<1|1,l,r);
    return s;
}
void modify_path(int u,int v,int k)
{
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        modify(1,id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    modify(1,id[v],id[u],k);
}
int query_path(int u,int v)
{
    int ans=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        ans+=query(1,id[top[u]],id[u]);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    ans+=query(1,id[v],id[u]);
    return ans;
}
void modify_tree(int u,int k)
{
    modify(1,id[u],id[u]+sz[u]-1,k);
}
int query_tree(int u)
{
    return query(1,id[u],id[u]+sz[u]-1);
}
int main()
{
    int i;
    cin>>n;
    memset(h,-1,sizeof h);
    for(i=2;i<=n;i++){
        int x;
        cin>>x;
        x++;
        add(x,i),add(i,x);
    }
    dfs1(1,-1,1);
    dfs2(1,1);
    build(1,1,n);
    cin>>m;
    while(m--){
        string st;
        int x;
        cin>>st>>x;
        x++;
        if(st[0]=='i'){
            cout<<query_path(1,x)<<endl;
            modify_path(1,x,1);
        }
        else{
            cout<<sz[x]-query_tree(x)<<endl;
            modify_tree(x,2);
        }
    }
}


活动打卡代码 AcWing 2568. 树链剖分

limie
4天前
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m;
LL a[100010];
LL h[100010],e[200010],ne[200010],idx;
LL id[100010],nw[100010],t;
LL d[100010],sz[100010],top[100010],fa[100010],son[100010];
LL tr1[100010],tr2[100010];
void add(LL a,LL b)//加边函数
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
//树链剖分(将树化为线段)
void dfs1(LL u,LL father,LL dep)
{
    d[u]=dep,fa[u]=father,sz[u]=1;
    for(LL i=h[u];~i;i=ne[i]){
        LL j=e[i];
        if(j==father)continue;
        dfs1(j,u,dep+1);
        sz[u]+=sz[j];
        if(sz[son[u]]<sz[j])son[u]=j;
    }
}
void dfs2(LL u,LL to)
{
    id[u]=++t,nw[t]=a[u],top[u]=to;
    if(!son[u])return;
    dfs2(son[u],to);
    for(LL i=h[u];~i;i=ne[i]){
        LL j=e[i];
        if(j==fa[u]||j==son[u])continue;
        dfs2(j,j);
    }
}
//树状数组(更新、修改)
LL lowbit(LL x)
{
    return x&-x;
}
void add_tree(LL x,LL c)
{
    for(LL i=x;i<=t;i+=lowbit(i))tr1[i]+=c,tr2[i]+=x*c;
}
LL ask_tree(LL x)
{
    LL s1=0,s2=0;
    for(LL i=x;i>=1;i-=lowbit(i))s1+=tr1[i],s2+=tr2[i];
    return s1*(x+1)-s2;
}
void modify_segment(LL u,LL v,LL k)
{
    add_tree(u,k),add_tree(v+1,-k);
}
LL query_segment(LL u,LL v)
{
    return ask_tree(v)-ask_tree(u-1);
}
//树链剖分(将路径化为区间)
void modify_path(LL u,LL v,LL k)
{
    while(top[u]!=top[v]){
        if(d[top[u]]<d[top[v]])swap(u,v);
        modify_segment(id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(d[u]<d[v])swap(u,v);
    modify_segment(id[v],id[u],k);
}
void modify_tree(LL u,LL k)
{
    modify_segment(id[u],id[u]+sz[u]-1,k);
}
LL query_path(LL u,LL v)
{
    LL ans=0;
    while(top[u]!=top[v]){
        if(d[top[u]]<d[top[v]])swap(u,v);
        ans+=query_segment(id[top[u]],id[u]);
        u=fa[top[u]];
    }
    if(d[u]<d[v])swap(u,v);
    ans+=query_segment(id[v],id[u]);
    return ans;
}
LL query_tree(LL u)
{
    return query_segment(id[u],id[u]+sz[u]-1);
}
int main()
{
    LL i;
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    memset(h,-1,sizeof h);
    for(i=1;i<n;i++){
        LL a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs1(1,-1,1);
    dfs2(1,1);
    for(i=1;i<=t;i++)modify_segment(i,i,nw[i]);
    cin>>m;
    while(m--){
        LL t,u,v,k;
        cin>>t;
        if(t==1){
            cin>>u>>v>>k;
            modify_path(u,v,k);
        }
        else if(t==2){
            cin>>u>>k;
            modify_tree(u,k);
        }
        else if(t==3){
            cin>>u>>v;
            cout<<query_path(u,v)<<endl;
        }
        else{
            cin>>u;
            cout<<query_tree(u)<<endl;
        }
    }
}



limie
13天前

简要题意

有两串数$A[1 ~ n],B[1 ~ m]$,有两个人小$L和小Q$,给出$q组l1,r1,l2,r2$,对于每组,小L在$A[l1~r1]$中取一数x,小Q在$B[l2~r2]$中取一数y,小L想使xy最大,小Q想使xy最小,求xy

$n,m,q<=10^5$


算法1

(朴素想法) $O(q n logm)$

考虑$A[l1~r1]$中每一个数,建一棵线段树(或ST表),再求出最小值,取最小值的最大输出即可
得分:60

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m,q;
LL a[1010],b[1010];
struct xxx{
    LL l,r;
    LL mn;
}tr[1010][4010];
LL read()
{
    LL s=0,w=1;
    char ch=getchar();
    while('0'>ch||ch>'9')w=ch=='-'?(-w):w,ch=getchar();
    while('0'<=ch&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
void write(LL x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
void pushup(LL x,LL u)
{
    tr[x][u].mn=min(tr[x][u<<1].mn,tr[x][u<<1|1].mn);
}
void build(LL x,LL u,LL l,LL r)
{
    tr[x][u]={l,r};
    if(l==r)tr[x][u].mn=a[x]*b[l];
    else{
        LL mid=l+r>>1;
        build(x,u<<1,l,mid),build(x,u<<1|1,mid+1,r);
        pushup(x,u);
    }
}
LL query(LL x,LL u,LL l,LL r)
{
    if(l<=tr[x][u].l&&tr[x][u].r<=r)return tr[x][u].mn;
    LL mid=tr[x][u].l+tr[x][u].r>>1,mn=LLONG_MAX;
    if(l<=mid)mn=query(x,u<<1,l,r);
    if(mid<r)mn=min(mn,query(x,u<<1|1,l,r));
    return mn;
}
int main()
{
    LL i,j;
    n=read(),m=read(),q=read();
    for(i=1;i<=n;++i)a[i]=read();
    for(i=1;i<=m;++i)b[i]=read();
    for(i=1;i<=n;++i)build(i,1,1,m);
    while(q--){
        LL l1=read(),r1=read(),l2=read(),r2=read(),mx=LLONG_MIN;
        for(i=l1;i<=r1;++i){
            LL mn=query(i,1,l2,r2);
            if(mx<mn)mx=mn;
        }
        write(mx),putchar('\n');
    }
}

算法2

(st表) $O(nlogn)$

此题从博弈论上来讲并不算难题,因为每组最多取两次。
先考虑小Q,若小L取的数$x>=0$,则小Q必然取$B[l2~r2]$中的最小值,若小L取的数$x<0$,则小Q必然取$B[l2~r2]$中的最大值。

接着考虑小L:
1.$x>=0$
则小Q必然取最小,设最小值为mn。
若mn>=0,则小L必然取>=0的最大值(可能不存在),否则小L取>=0的最小值。
2.$x<0$
则小Q必然取最大,设最小值为mx。
若mx>=0,则小L必然取<0的最大值(可能不存在),否则小L取<0的最小值。

如何维护$mn、mx、>=0的最大值,>=0的最小值,<0的最大值,<0的最小值$?
可以用6个ST表,对于不存在的情况记为-INF或INF即可,代码也不难实现,读者请自行完成

时间复杂度

ST表时间复杂度为$O(nlogn)$,总时间复杂度为$O(nlogn+mlogm+qlogn)$,约为$O(nlogn)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1e9+1;
LL n,m,q;
LL a[100010],b[100010];
LL fb1[100010][18],fb2[100010][18],fa11[100010][18],fa12[100010][18],fa21[100010][18],fa22[100010][18];
//fb1:b中的max,fb2:b中的min,fa11:a中>=0的max,fa12:a中>=0的min,fa21:a中<0的max,fa22:a中<0的min 
LL query(LL l,LL r,LL t)
{
    LL k=log2(r-l+1);
    if(t==1)return max(fb1[l][k],fb1[r-(1<<k)+1][k]);
    else if(t==2)return min(fb2[l][k],fb2[r-(1<<k)+1][k]);
    else if(t==3)return max(fa11[l][k],fa11[r-(1<<k)+1][k]);
    else if(t==4)return min(fa12[l][k],fa12[r-(1<<k)+1][k]);
    else if(t==5)return max(fa21[l][k],fa21[r-(1<<k)+1][k]);
    else return min(fa22[l][k],fa22[r-(1<<k)+1][k]);
}
int main()
{
    LL i,j;
    cin>>n>>m>>q;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=m;i++)cin>>b[i];
    for(j=0;j<=16;j++)
        for(i=1;i+(1<<j)-1<=m;i++)
            if(!j)fb1[i][j]=fb2[i][j]=b[i];
            else{
                fb1[i][j]=max(fb1[i][j-1],fb1[i+(1<<j-1)][j-1]);
                fb2[i][j]=min(fb2[i][j-1],fb2[i+(1<<j-1)][j-1]);
            }

    for(j=0;j<=16;j++)
        for(i=1;i+(1<<j)-1<=n;i++)
            if(!j){
                if(a[i]>=0){
                    fa21[i][j]=-INF;
                    fa22[i][j]=INF;
                    fa11[i][j]=fa12[i][j]=a[i];
                }
                else{
                    fa11[i][j]=-INF;
                    fa12[i][j]=INF;
                    fa21[i][j]=fa22[i][j]=a[i];
                }
            }
            else{
                fa11[i][j]=max(fa11[i][j-1],fa11[i+(1<<j-1)][j-1]);
                fa12[i][j]=min(fa12[i][j-1],fa12[i+(1<<j-1)][j-1]);
                fa21[i][j]=max(fa21[i][j-1],fa21[i+(1<<j-1)][j-1]);
                fa22[i][j]=min(fa22[i][j-1],fa22[i+(1<<j-1)][j-1]);
            }

    while(q--){
        LL l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2; 
        LL mxb=query(l2,r2,1),mnb=query(l2,r2,2),ans=LLONG_MIN;
        if(query(l1,r1,3)>=0)ans=max(ans,query(l1,r1,3)*mnb);
        if(query(l1,r1,4)<INF)ans=max(ans,query(l1,r1,4)*mnb);
        if(query(l1,r1,5)>-INF)ans=max(ans,query(l1,r1,5)*mxb);
        if(query(l1,r1,6)<0)ans=max(ans,query(l1,r1,6)*mxb);
        cout<<ans<<endl;
    }
}


活动打卡代码 AcWing 4733. 策略游戏

limie
13天前
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1e9+1;
LL n,m,q;
LL a[100010],b[100010];
LL fb1[100010][18],fb2[100010][18],fa11[100010][18],fa12[100010][18]
,fa21[100010][18],fa22[100010][18];
//fb1:b中的max,fb2:b中的min,fa11:a中>=0的max,fa12:a中>=0的min
//fa21:a中<0的max,fa22:a中<0的min 
LL query(LL l,LL r,LL t)
{
    LL k=log2(r-l+1);
    if(t==1)return max(fb1[l][k],fb1[r-(1<<k)+1][k]);
    else if(t==2)return min(fb2[l][k],fb2[r-(1<<k)+1][k]);
    else if(t==3)return max(fa11[l][k],fa11[r-(1<<k)+1][k]);
    else if(t==4)return min(fa12[l][k],fa12[r-(1<<k)+1][k]);
    else if(t==5)return max(fa21[l][k],fa21[r-(1<<k)+1][k]);
    else return min(fa22[l][k],fa22[r-(1<<k)+1][k]);
}
LL read()
{
    LL s=0,w=1;
    char ch=getchar();
    while('0'>ch||ch>'9')w=ch=='-'?-1:1,ch=getchar();
    while('0'<=ch&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    return s*w; 
}
void write(LL x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int main()
{
    LL i,j;
    n=read(),m=read(),q=read();
    for(i=1;i<=n;++i)a[i]=read();
    for(i=1;i<=m;++i)b[i]=read();
    for(j=0;j<=16;++j)
        for(i=1;i+(1<<j)-1<=m;++i)
            if(!j)fb1[i][j]=fb2[i][j]=b[i];
            else{
                fb1[i][j]=max(fb1[i][j-1],fb1[i+(1<<j-1)][j-1]);
                fb2[i][j]=min(fb2[i][j-1],fb2[i+(1<<j-1)][j-1]);
            }

    for(j=0;j<=16;++j)
        for(i=1;i+(1<<j)-1<=n;++i)
            if(!j){
                if(a[i]>=0){
                    fa21[i][j]=-INF;
                    fa22[i][j]=INF;
                    fa11[i][j]=fa12[i][j]=a[i];
                }
                else{
                    fa11[i][j]=-INF;
                    fa12[i][j]=INF;
                    fa21[i][j]=fa22[i][j]=a[i];
                }
            }
            else{
                fa11[i][j]=max(fa11[i][j-1],fa11[i+(1<<j-1)][j-1]);
                fa12[i][j]=min(fa12[i][j-1],fa12[i+(1<<j-1)][j-1]);
                fa21[i][j]=max(fa21[i][j-1],fa21[i+(1<<j-1)][j-1]);
                fa22[i][j]=min(fa22[i][j-1],fa22[i+(1<<j-1)][j-1]);
            }

    while(q--){
        LL l1=read(),r1=read(),l2=read(),r2=read();
        LL mxb=query(l2,r2,1),mnb=query(l2,r2,2),ans=LLONG_MIN;
        if(query(l1,r1,3)>=0)ans=max(ans,query(l1,r1,3)*mnb);
        if(query(l1,r1,4)<INF)ans=max(ans,query(l1,r1,4)*mnb);
        if(query(l1,r1,5)>-INF)ans=max(ans,query(l1,r1,5)*mxb);
        if(query(l1,r1,6)<0)ans=max(ans,query(l1,r1,6)*mxb);
        write(ans),putchar('\n');
    }
}


活动打卡代码 AcWing 1359. 城堡

limie
16天前
#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[2510],c[2510];
int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
char dir[]="WNES";
int get(int x,int y){return (x-1)*m+y;}
int find(int x){return p[x]=(p[x]!=x)?find(p[x]):p[x];}
int main()
{
    int i,j,k;
    cin>>m>>n;
    for(i=1;i<=n*m;i++)p[i]=i,c[i]=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            int x;
            cin>>x;
            int a=find(get(i,j));
            for(k=0;k<4;k++)
                if(!(x>>k&1)){
                    int t1=i+dx[k],t2=j+dy[k];
                    int b=get(t1,t2);
                    int pa=find(a),pb=find(b);
                    if(pa!=pb){
                        p[pa]=pb;
                        c[pb]+=c[pa];
                    }
                }
        }

    int ans1=0,ans2=0,ans=0,rx,ry;
    char rd;
    for(i=1;i<=n*m;i++)
        if(p[i]==i)ans1++,ans2=max(ans2,c[i]);

    cout<<ans1<<endl<<ans2<<endl;
    for(j=1;j<=m;j++)
        for(i=n;i>=1;i--){
            int a=get(i,j);
            for(k=1;k<=2;k++){
                int x=i+dx[k],y=j+dy[k];
                if(x<1||x>n||y<1||y>m)continue;
                int b=get(x,y);
                int pa=find(a),pb=find(b);
                if(pa!=pb&&c[pa]+c[pb]>ans){
                    ans=c[pa]+c[pb];
                    rx=i,ry=j,rd=dir[k];
                }
            }
        }

    cout<<ans<<endl<<rx<<' '<<ry<<' '<<rd;
}


活动打卡代码 AcWing 950. 郁闷的出纳员

limie
24天前

写完了treap,才感到线段树有多好写;写完了splay,才感觉treap有多好写(我讲的

#include<bits/stdc++.h>
using namespace std;
int n,mn,d,t;
const int INF=1e9;
struct Node{
    int s[2],p,v;
    int size;
    void init(int _v,int _p)
    {
        v=_v,p=_p;
        size=1;
    }
}tr[100010];
int root,idx;
void pushup(int u)
{
    tr[u].size=tr[tr[u].s[0]].size+tr[tr[u].s[1]].size+1;
}
void rotate(int x)
{
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void splay(int x,int k)
{
    while(tr[x].p!=k){
        int y=tr[x].p,z=tr[y].p;
        if(z!=k){
            if((tr[y].s[1]==x)^(tr[z].s[1]==y))rotate(x);else rotate(y);
        }
        rotate(x);
    }
    if(!k)root=x;
}
int insert(int v)
{
    int u=root,p=0;
    while(u)p=u,u=tr[u].s[v>tr[u].v];
    u=++idx;
    if(p)tr[p].s[v>tr[p].v]=u;
    tr[u].init(v,p);
    splay(u,0);
    return u;
}
int get(int v)
{
    int u=root,ans;
    while(u)
        if(tr[u].v>=v)ans=u,u=tr[u].s[0];else u=tr[u].s[1];

    return ans;
}
int get_k(int k)
{
    int u=root;
    while(u)
        if(tr[tr[u].s[0]].size>=k)u=tr[u].s[0];
        else if(tr[tr[u].s[0]].size+1==k)return tr[u].v;
        else k-=tr[tr[u].s[0]].size+1,u=tr[u].s[1];

    return -1;
}
int main()
{
    int i;
    cin>>n>>mn;
    int l=insert(-INF),r=insert(INF);
    while(n--){
        char ch;
        int k;
        cin>>ch>>k;
        if(ch=='I'){
            if(k>=mn)k-=d,insert(k),t++;
        }
        else if(ch=='A')d+=k;
        else if(ch=='S'){
            d-=k;
            r=get(mn-d);
            splay(r,0),splay(l,r);
            tr[l].s[1]=0;
            pushup(l),pushup(r);
        }
        else{
            if(tr[root].size-2<k)cout<<-1<<endl;
            else cout<<get_k(tr[root].size-k)+d<<endl;
        }
    }
    cout<<t-tr[root].size+2;
}


活动打卡代码 AcWing 2437. Splay

limie
26天前

代码倒比treap好写,但难调程度上涨了几千倍…

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Tree{
    int s[2],p;
    int v;
    int size,val;
    void init(int _v,int _p)
    {
        v=_v,p=_p;
        size=1;
    }
}tr[100010];
int root,idx;
void pushup(int u)
{
    tr[u].size=tr[tr[u].s[0]].size+tr[tr[u].s[1]].size+1;
}
void pushdown(int u)
{
    if(tr[u].val){
        swap(tr[u].s[0],tr[u].s[1]);
        tr[tr[u].s[0]].val^=1;
        tr[tr[u].s[1]].val^=1;
        tr[u].val=0;
    }
}
void rotate(int x)
{
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void splay(int x,int k)
{
    while(tr[x].p!=k){
        int y=tr[x].p,z=tr[y].p;
        if(z!=k){
            if((tr[y].s[1]==x)^(tr[z].s[1]==y))rotate(x);else rotate(y);
        }
        rotate(x);
    }
    if(!k)root=x;
}
void insert(int x)
{
    int u=root,p=0;
    while(u)p=u,u=tr[u].s[x>tr[u].v];
    u=++idx;
    if(p)tr[p].s[x>tr[p].v]=u;
    tr[u].init(x,p);
    splay(u,0);
}
int get_k(int k)
{
    int u=root;
    while(1){
        pushdown(u);
        if(tr[tr[u].s[0]].size>=k)u=tr[u].s[0];
        else if(tr[tr[u].s[0]].size+1==k)return u;
        else k-=tr[tr[u].s[0]].size+1,u=tr[u].s[1];
    }
    return -1;
}
void output(int u)
{
    pushdown(u);
    if(tr[u].s[0])output(tr[u].s[0]);
    if(1<=tr[u].v&&tr[u].v<=n)cout<<tr[u].v<<' ';
    if(tr[u].s[1])output(tr[u].s[1]);
}
int main()
{
    int i;
    cin>>n>>m;
    for(i=0;i<=n+1;i++)insert(i);
    while(m--){
        int l,r;
        cin>>l>>r;
        l=get_k(l),r=get_k(r+2);
        splay(l,0);
        splay(r,l);
        tr[tr[r].s[0]].val^=1;
    }
    output(root);
}