P1456 Monkey King

题意描述

N只好斗的猴子，互不认识。但是猴子们不能避免争吵，且两只猴子只会在认识对方时发生争吵，当争吵发生时，双方会邀请它们各自最强壮的朋友并发起决斗（决斗的为各自最强壮的朋友）。当然，在决斗之后两只猴子和他们各自的伙伴都认识对方了（成为朋友），虽然他们曾经有过冲突，但是他们之间绝不会再发生争吵了。
假设每只猴子有一个强壮值，强壮值将在一场决斗后减少为原先的一半（例如 10 会减少到 5，而 5 会减少到 2，即向下取整）。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
const int MAXM = 32768;
int pre[MAXN],n,m;
int find(int x)
{   return pre[x]==x?x:pre[x]=find(pre[x]);
}
struct Tree
{   int lc,rc;
    int sz;
} tr[MAXN*40];
int root[MAXN],idx;

void pushup(int u)
{   tr[u].sz=tr[tr[u].lc].sz+tr[tr[u].rc].sz;
}

int getnode()
{   int u=++idx;
    tr[u]= {0,0,0};
    return u;
}
void insert(int &u,int l,int r,int x)
{   if(!u) u=getnode();
    if(l==r)
    {   tr[u].sz++;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) insert(tr[u].lc,l,mid,x);
    else insert(tr[u].rc,mid+1,r,x);
    pushup(u);
}
int query(int u,int l,int r)
{   if(!u) return -1;
    if(l==r) return l;
    int mid=l+r>>1;
    if(tr[tr[u].rc].sz) return query(tr[u].rc,mid+1,r);
    else return query(tr[u].lc,l,mid);
}

void del(int u,int l,int r,int x)
{   if(!u) return ;
    if(l==r)
    {   tr[u].sz--;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) del(tr[u].lc,l,mid,x);
    else del(tr[u].rc,mid+1,r,x);
    pushup(u);

}

int merge(int x,int y)
{   if(!x||!y) return x+y;

    tr[x].sz+=tr[y].sz;


    tr[x].lc=merge(tr[x].lc,tr[y].lc);
    tr[x].rc=merge(tr[x].rc,tr[y].rc);

    return x;

}

int main()
{   while(scanf("%d",&n)!=EOF)
    {   memset(root,0,sizeof(root));
        idx=0;

        for(int i=1; i<=n; i++)
        {   int x;
            scanf("%d",&x);
            pre[i]=i;
            insert(root[i],1,MAXM,x);

        }
        scanf("%d",&m);
        while(m--)
        {   int a,b;
            scanf("%d%d",&a,&b);
            a=find(a),b=find(b);
            if(a==b)
            {   puts("-1");
            }
            else
            {

                int x=query(root[a],1,MAXM);
                int y=query(root[b],1,MAXM);
                del(root[a],1,MAXM,x);
                del(root[b],1,MAXM,y);
                insert(root[a],1,MAXM,x/2);
                insert(root[b],1,MAXM,y/2);
                root[a]=merge(root[a],root[b]);
                pre[b]=a;
                printf("%d\n",query(root[a],1,MAXM));

            }

        }

    }

    return 0;
}

P4556 [Vani有约会]雨天的尾巴

题目描述

首先村落里的一共有 n 座房屋，并形成一个树状结构。然后救济粮分 m 次发放，每次选择两个房屋 (x, y)，然后对于 x 到 y 的路径上(含 x 和 y)每座房子里发放一袋 z 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
const int MAXM = 2e5+10;
int n,m,head[MAXN],tot;
struct Edge
{   int next,to;
} edge[MAXM];
void add(int x,int y)
{   edge[tot].to=y;
    edge[tot].next=head[x];
    head[x]=tot++;
}

struct Tree
{   int lc,rc;
    int cnt,v;
} tr[MAXN*60];
int root[MAXN],idx;
void pushup(int u)
{   if(tr[tr[u].lc].cnt>=tr[tr[u].rc].cnt)
    {   tr[u].cnt=tr[tr[u].lc].cnt;
        tr[u].v=tr[tr[u].lc].v;
    }
    else
    {   tr[u].cnt=tr[tr[u].rc].cnt;
        tr[u].v=tr[tr[u].rc].v;
    }
}
void add(int &u,int l,int r,int x,int num)
{   if(!u) u=++idx;
    if(l==r)
    {   tr[u].v=l;
        tr[u].cnt+=num;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) add(tr[u].lc,l,mid,x,num);
    else add(tr[u].rc,mid+1,r,x,num);
    pushup(u);
}

int dep[MAXN],sz[MAXN],fa[MAXN],son[MAXN],top[MAXN];
void dfs1(int u,int father,int depth)
{   fa[u]=father,dep[u]=depth,sz[u]=1;
    for(int i=head[u]; ~i; i=edge[i].next)
    {   int j=edge[i].to;
        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)
{   top[u]=t;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(int i=head[u]; ~i; i=edge[i].next)
    {   int j=edge[i].to;
        if(j==fa[u]||j==son[u]) continue;
        dfs2(j,j);
    }

}

int lca(int u,int v)
{   while(top[u]!=top[v])
    {   if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    return u;
}

int merge(int x,int y,int l,int r)
{   if(!x||!y) return x+y;
    if(l==r)
    {   tr[x].cnt+=tr[y].cnt;
        return x;
    }

    int mid=l+r>>1;
    tr[x].lc=merge(tr[x].lc,tr[y].lc,l,mid);
    tr[x].rc=merge(tr[x].rc,tr[y].rc,mid+1,r);
    pushup(x);
    return x;

}
int ans[MAXN];
void get_ans(int u,int father)
{   for(int i=head[u]; ~i; i=edge[i].next)
    {   int j=edge[i].to;
        if(j==father) continue;
        get_ans(j,u);
        root[u]=merge(root[u],root[j],1,100000);

    }
    if(tr[root[u]].cnt==0)
        ans[u]=0;
    else
        ans[u]=tr[root[u]].v;

}
int main()
{   memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=0; i<n-1; i++)
    {   int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    dfs1(1,-1,1);
    dfs2(1,1);

    while(m--)
    {   int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(root[a],1,100000,c,1);
        add(root[b],1,100000,c,1);
        int anc=lca(a,b);
        add(root[anc],1,100000,c,-1);
        add(root[fa[anc]],1,100000,c,-1);
    }
    get_ans(1,-1);

    for(int i=1; i<=n; i++)
    {   printf("%d\n",ans[i]);
    }

    return 0;
}

P4197 Peaks 离线询问+线段树合并

题目描述

有n座山峰，每座山峰有他的高度 h_i。有些山峰之间有双向道路相连，共 m条路径，每条路径有一个困难值，这个值越大表示越难走。

现在有 q 组询问，每组询问询问从点 v开始只经过困难值小于等于x的路径所能到达的山峰中第 k 高的山峰，如果无解输出 −1

输入格式

第一行三个数 n,m,q。 第二行 n 个数，第 ii 个数为 h_i。
接下来 m 行，每行三个整数 a,b,c，表示从a→b 有一条困难值为 c 的双向路径。 接下来q 行，每行三个数 v,x,k，表示一组询问。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
const int MAXM = 5e5+10;
int head[MAXN],tot,n,m,q;
int h[MAXN],pre[MAXN];
int find(int x)
{   return pre[x]==x?x:pre[x]=find(pre[x]);
}
struct Edge
{   int u,v,w;
    bool operator <(const Edge& other) const
    {   return w<other.w;
    }
} e[MAXM];

vector<int> nums;
struct Query
{   int v,x,k;
    int id;
    bool operator <(const Query& other) const
    {   return x<other.x;
    }
} query[MAXM];
int ans[MAXM];


int get(int x)
{   return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
int root[MAXN],idx;

struct Tree
{   int lc,rc;
    int cnt;
} tr[MAXN*25];

void pushup(int u)
{   tr[u].cnt=tr[tr[u].lc].cnt+tr[tr[u].rc].cnt;
}
void insert(int &u,int l,int r,int x)
{   if(!u) u=++idx;
    if(l==r)
    {   tr[u].cnt++;
        return ;
    }
    int mid=l+r>>1;
    if(x<=mid) insert(tr[u].lc,l,mid,x);
    else insert(tr[u].rc,mid+1,r,x);
    pushup(u);
}

int merge(int x,int y)
{   if(!x||!y) return x+y;
    tr[x].cnt+=tr[y].cnt;
    tr[x].lc=merge(tr[x].lc,tr[y].lc);
    tr[x].rc=merge(tr[x].rc,tr[y].rc);
    return x;

}
int quer(int u,int l,int r,int k)
{   if(l==r) return l;
    int mid=l+r>>1;
    if(tr[tr[u].rc].cnt>=k) return quer(tr[u].rc,mid+1,r,k);
    else return quer(tr[u].lc,l,mid,k-tr[tr[u].rc].cnt);

}
int main()
{   scanf("%d%d%d",&n,&m,&q);
    for(int i=1; i<=n; i++)
    {   scanf("%d",&h[i]);
        nums.push_back(h[i]);
        pre[i]=i;
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());

    for(int i=1; i<=n; i++)
    {   insert(root[i],0,n-1,get(h[i]));

    }

    for(int i=0; i<m; i++)
    {   int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        e[i]= {a,b,c};
    }
    sort(e,e+m);
    for(int i=0; i<q; i++)
    {   int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        query[i]= {a,b,c,i};
    }
    sort(query,query+q);
    int j=0;
    for(int i=0; i<q; i++)
    {   int v=query[i].v,id=query[i].id,k=query[i].k;

        while(e[j].w<=query[i].x&&j<m)
        {   int a=e[j].u,b=e[j].v;
            a=find(a),b=find(b);
            if(a!=b)
            {   root[a]=merge(root[a],root[b]);
                pre[b]=a;

            }
            ++j;

        }
        v=find(v);
        if(tr[root[v]].cnt<k)
            ans[id]=-1;
        else
        {   ans[id]=nums[quer(root[v],0,n-1,k)];
        }

    }
    for(int i=0; i<q; i++)
    {   printf("%d\n",ans[i]);
    }


    return 0;
}