首页 > 其他分享 >P4899 [IOI2018] werewolf 狼人

P4899 [IOI2018] werewolf 狼人

时间：2024-12-06 12:25:31浏览次数：6  
标签：cnt IOI2018 return int 狼人 pos tot fa P4899

P4899 [IOI2018] werewolf 狼人

又是欢乐的 kruskal 重构树捏。

首先我们来仔细研读一下题目：

当你是人形时，你必须避开城市 \(0, 1, \ldots , L_i - 1\) ；而当你是狼形时，则必须避开城市 \(R_i + 1, R_i + 2, \ldots , N - 1\)。

也就是说，从起点开始，你只能走 \([L,n]\) 从终点开始，你只能走 \([1,R]\) 那么我们考虑建两颗 Kruskal重构树

以“起点树”为例：
一颗重构树的实点权为该点的编号，虚点权为该树下点权的最小值 ，这样我们就能保证在此树下，只要满足　\(w[x] \ge L\) 那么这个树下的所有点对于起点来说都是可到达的。

由于这个式子 \(w[x] \ge L\) 是判断该子树下的节点是否可达的充分条件，所以我们自然希望 \(w[x]\) 尽可能地大。那么我们排序的时候就要以 \((u,v)\)的最小值最大化 来排序

那么对于终点树：

我们用虚点维护该树下所有点的最大值
，我们需要满足的条件是 \(w[x] \le R\) 。

我们显然希望　\(w[x]\) 尽可能的小，所以我们排序的关键字就应该是 \((u,v)\) 的最大值最小化

我们求完了这两颗重构树了之后在他们上面跑倍增和 \(dfs\) 序，这样我们就知道了每个子树的编号区间。对于答案统计，我们先让起点和终点 \(s,t\) 各自跳到起点树和终点树的相应的节点 \(u,v\) ，这两个节点所对应的子树分别对应着 \(s,t\) 所能到达的点集。我们只需要知道这两个点集是否有交就行了

然而判断是否有交当然又是我们 喜闻乐见 的主席树环节了：

我是对于起点树来建的主席树：

对于 起点树 上的一个 \(dfn_{s}\) 求出它所对应的节点 \(pos\) 然后再在 终点树 上获取 \(pos\) 在终点树上的 \(dfn_{t}\) 然后将 \(dfn_{t}\) 插入根下标为 \(dfn_{s}\) 的主席树中

那么我们查询的时候只需要知道终点在终点树上对应的节点 \(v\) 的子树的 \(dfn_{t}\) 区间 \([l,r]\)
在 \(u\) 这颗主席树上是否有点就好了

Code：

#include<bits/stdc++.h>
const int N=4e5+5;
const int lg=20;
using namespace std;
int n,m,Q,e_cnt,ans;
struct Grapgh{
    int head[N];
    struct Edge{
        int to,nxt;
    }e[N<<2];
    void add(int x,int y)
    {
        e[++e_cnt]=Edge{y,head[x]};
        head[x]=e_cnt;
    }
    void init()
    {
        for(int i=0;i<N;i++)head[i]=0;
        e_cnt=0;
    }
    int tot;
    int f[N][lg+5];
    int st[N],ed[N],pos[N],siz[N],w[N];
    void dfs(int x,int fa)
    {
        pos[++tot]=x;st[x]=tot;
        f[x][0]=fa;
        for(int j=1;j<=lg;j++)f[x][j]=f[f[x][j-1]][j-1];
        for(int i=head[x],y;i;i=e[i].nxt)
        {
            y=e[i].to;
            if(y==f[x][0])continue;
            dfs(y,x);
            siz[x]+=siz[y];
        }
        if(!siz[x])siz[x]=1;
        ed[x]=tot;
    }
    int get_lower(int x,int k)
    {
        for(int i=lg;i>=0;i--)if(w[f[x][i]]<=k&&f[x][i])x=f[x][i];
        return x;
    }
    int get_upper(int x,int k)
    {
        for(int i=lg;i>=0;i--)if(w[f[x][i]]>=k&&f[x][i])x=f[x][i];
        return x;
    }
}G1,G2;
struct edge{
    int u,v;
}q[N<<1];
bool cmp1(edge e1,edge e2){
    return (e1.u<e1.v ? e1.u : e1.v)>(e2.u<e2.v ? e2.u : e2.v);
}
bool cmp2(edge e1,edge e2){
    return (e1.u>e1.v ? e1.u : e1.v)<(e2.u>e2.v ? e2.u : e2.v);
}
struct Kruskal{
    int fa[N];
    int tot;
    int find(int x){return fa[x] = fa[x]==x ? fa[x] : find(fa[x]);}
    void build(int tag,Grapgh &G)
    {
        tot=n;
        for(int i=0;i<N;i++)fa[i]=i;
        for(int i=0;i<n;i++)G.w[i]=i;
        for(int i=1;i<=m;i++)
        {
            int x=find(q[i].u),y=find(q[i].v);
            if(x!=y)
            {
                G.w[++tot]= (tag ? (G.w[x] > G.w[y] ? G.w[x] : G.w[y]) : (G.w[x] < G.w[y] ? G.w[x] : G.w[y]));
                G.add(tot,x);G.add(tot,y);
                fa[tot]=fa[x]=fa[y]=tot;
            }
        }
    }
}K;
//Segment_Tree
struct Segment_Tree{
    int rt[N],cnt;
    struct Tree{
        int ls,rs,cnt;
    }t[N*40];
    void insert(int &x,int y,int l,int r,int pos)
    {
        t[x=++cnt]=t[y];
        t[x].cnt++;
        if(l==r)return ;
        int mid=l+r>>1;
        if(pos<=mid)insert(t[x].ls,t[y].ls,l,mid,pos);
        if(mid<pos) insert(t[x].rs,t[y].rs,mid+1,r,pos);
    }
    int query(int x,int y,int l,int r,int L,int R)
    {
        if(R<L||!y)return 0;
        if(L<=l&&r<=R)
        {
            return -t[x].cnt+t[y].cnt;
        }
        int mid=l+r>>1;
        int res=0;
        if(L<=mid)res+=query(t[x].ls,t[y].ls,l,mid,L,R);
        if(mid<R) res+=query(t[x].rs,t[y].rs,mid+1,r,L,R);
        return res;
    }
}T;
int idd[N];
void work()
{
    cin>>n>>m>>Q;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].u,&q[i].v);
    }
    sort(q+1,q+1+m,cmp1);
    K.build(0,G1);
    G1.dfs(K.tot,K.tot);
    sort(q+1,q+1+m,cmp2);
    K.build(1,G2);
    G2.dfs(K.tot,K.tot);
    for(int i=1;i<=G1.tot;i++)
    {
        if(G1.pos[i]<=n)
        {
            int x=G1.pos[i];
            T.insert(T.rt[i],T.rt[i-1],0,N,G2.st[x]);
        }
        else
        {
            T.rt[i]=T.rt[i-1];
        }
    }
    for(int i=1,s,t,l,r;i<=Q;i++)
    {
        scanf("%d%d%d%d",&s,&t,&l,&r);
        s=G1.get_upper(s,l);
        t=G2.get_lower(t,r);
        ans=T.query(T.rt[G1.st[s]-1],T.rt[G1.ed[s]],0,N,G2.st[t],G2.ed[t]);
        ans = ans>0 ? 1 : 0;
        printf("%d\n",ans);
    }
}
int main()
{
    //freopen("werewolf.in","r",stdin);freopen("werewolf.out","w",stdout);
    work();
    return 0;
}
```# [P4899 [IOI2018] werewolf 狼人](https://www.luogu.com.cn/problem/P4899)

又是欢乐的 **kruskal** 重构树捏。

首先我们来仔细研读一下题目：

当你是人形时，你必须避开城市 $0, 1, \ldots , L_i - 1$ ；而当你是狼形时，则必须避开城市 $R_i + 1, R_i + 2, \ldots , N - 1$。

也就是说，从起点开始，你只能走 $[L,n]$ 从终点开始，你只能走 $[1,R]$ 那么我们考虑建两颗 **Kruskal重构树**

以“起点树”为例：
一颗重构树的实点权为该点的编号，虚点权为**该树下点权的最小值** ，这样我们就能保证在此树下，只要满足　$w[x] \ge L$ 那么这个树下的所有点对于起点来说都是可到达的。

由于这个式子 $w[x] \ge L$ 是判断该子树下的节点是否可达的充分条件，所以我们自然希望 $w[x]$ 尽可能地大。那么我们排序的时候就要以 **$(u,v)$的最小值最大化** 来排序


那么对于终点树：

我们用虚点维护该树下所有点的最大值
，我们需要满足的条件是 $w[x] \le R$ 。

我们显然希望　$w[x]$ 尽可能的小，所以我们排序的关键字就应该是 **$(u,v)$ 的最大值最小化**

我们求完了这两颗重构树了之后在他们上面跑**倍增**和 $dfs$ 序，这样我们就知道了每个子树的编号区间。对于答案统计，我们先让起点和终点 $s,t$ 各自跳到起点树和终点树的相应的节点 $u,v$ ，这两个节点所对应的子树分别对应着 $s,t$ 所能到达的点集。我们只需要知道这两个点集是否有交就行了


然而判断是否有交当然又是我们 ~喜闻乐见~ 的主席树环节了：

我是对于起点树来建的主席树：

对于 **起点树** 上的一个 $dfn_{s}$ 求出它所对应的节点 $pos$ 然后再在 **终点树** 上获取 $pos$ 在终点树上的 $dfn_{t}$ 然后将 $dfn_{t}$ 插入根下标为 $dfn_{s}$ 的主席树中 

那么我们查询的时候只需要知道**终点**在**终点树**上对应的节点 $v$ 的子树的 $dfn_{t}$ 区间 $[l,r]$
在 $u$ 这颗主席树上是否有点就好了

# Code：

include<bits/stdc++.h>

const int N=4e5+5;
const int lg=20;
using namespace std;
int n,m,Q,e_cnt,ans;
struct Grapgh{
int head[N];
struct Edge{
int to,nxt;
}e[N<<2];
void add(int x,int y)
{
e[++e_cnt]=Edge{y,head[x]};
head[x]=e_cnt;
}
void init()
{
for(int i=0;i<N;i++)head[i]=0;
e_cnt=0;
}
int tot;
int f[N][lg+5];
int st[N],ed[N],pos[N],siz[N],w[N];
void dfs(int x,int fa)
{
pos[++tot]=x;st[x]=tot;
f[x][0]=fa;
for(int j=1;j<=lg;j++)f[x][j]=f[f[x][j-1]][j-1];
for(int i=head[x],y;i;i=e[i].nxt)
{
y=e[i].to;
if(yf[x][0])continue;
dfs(y,x);
siz[x]+=siz[y];
}
if(!siz[x])siz[x]=1;
ed[x]=tot;
}
int get_lower(int x,int k)
{
for(int i=lg;i>=0;i--)if(w[f[x][i]]<=k&&f[x][i])x=f[x][i];
return x;
}
int get_upper(int x,int k)
{
for(int i=lg;i>=0;i--)if(w[f[x][i]]>=k&&f[x][i])x=f[x][i];
return x;
}
}G1,G2;
struct edge{
int u,v;
}q[N<<1];
bool cmp1(edge e1,edge e2){
return (e1.u<e1.v ? e1.u : e1.v)>(e2.u<e2.v ? e2.u : e2.v);
}
bool cmp2(edge e1,edge e2){
return (e1.u>e1.v ? e1.u : e1.v)<(e2.u>e2.v ? e2.u : e2.v);
}
struct Kruskal{
int fa[N];
int tot;
int find(int x){return fa[x] = fa[x]x ? fa[x] : find(fa[x]);}
void build(int tag,Grapgh &G)
{
tot=n;
for(int i=0;i<N;i++)fa[i]=i;
for(int i=0;i<n;i++)G.w[i]=i;
for(int i=1;i<=m;i++)
{
int x=find(q[i].u),y=find(q[i].v);
if(x!=y)
{
G.w[++tot]= (tag ? (G.w[x] > G.w[y] ? G.w[x] : G.w[y]) : (G.w[x] < G.w[y] ? G.w[x] : G.w[y]));
G.add(tot,x);G.add(tot,y);
fa[tot]=fa[x]=fa[y]=tot;
}
}
}
}K;
//Segment_Tree
struct Segment_Tree{
int rt[N],cnt;
struct Tree{
int ls,rs,cnt;
}t[N*40];
void insert(int &x,int y,int l,int r,int pos)
{
t[x=++cnt]=t[y];
t[x].cnt++;
if(l==r)return ;
int mid=l+r>>1;
if(pos<=mid)insert(t[x].ls,t[y].ls,l,mid,pos);
if(mid<pos) insert(t[x].rs,t[y].rs,mid+1,r,pos);
}
int query(int x,int y,int l,int r,int L,int R)
{
if(R<L||!y)return 0;
if(L<=l&&r<=R)
{
return -t[x].cnt+t[y].cnt;
}
int mid=l+r>>1;
int res=0;
if(L<=mid)res+=query(t[x].ls,t[y].ls,l,mid,L,R);
if(mid<R) res+=query(t[x].rs,t[y].rs,mid+1,r,L,R);
return res;
}
}T;
int idd[N];
void work()
{
cin>>n>>m>>Q;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&q[i].u,&q[i].v);
}
sort(q+1,q+1+m,cmp1);
K.build(0,G1);
G1.dfs(K.tot,K.tot);
sort(q+1,q+1+m,cmp2);
K.build(1,G2);
G2.dfs(K.tot,K.tot);
for(int i=1;i<=G1.tot;i++)
{
if(G1.pos[i]<=n)
{
int x=G1.pos[i];
T.insert(T.rt[i],T.rt[i-1],0,N,G2.st[x]);
}
else
{
T.rt[i]=T.rt[i-1];
}
}
for(int i=1,s,t,l,r;i<=Q;i++)
{
scanf("%d%d%d%d",&s,&t,&l,&r);
s=G1.get_upper(s,l);
t=G2.get_lower(t,r);
ans=T.query(T.rt[G1.st[s]-1],T.rt[G1.ed[s]],0,N,G2.st[t],G2.ed[t]);
ans = ans>0 ? 1 : 0;
printf("%d\n",ans);
}
}
int main()
{
//freopen("werewolf.in","r",stdin);freopen("werewolf.out","w",stdout);
work();
return 0;
}


又是欢乐的 **kruskal** 重构树捏。

首先我们来仔细研读一下题目：

当你是人形时，你必须避开城市 $0, 1, \ldots , L_i - 1$ ；而当你是狼形时，则必须避开城市 $R_i + 1, R_i + 2, \ldots , N - 1$。

也就是说，从起点开始，你只能走 $[L,n]$ 从终点开始，你只能走 $[1,R]$ 那么我们考虑建两颗 **Kruskal重构树**

以“起点树”为例：
一颗重构树的实点权为该点的编号，虚点权为**该树下点权的最小值** ，这样我们就能保证在此树下，只要满足　$w[x] \ge L$ 那么这个树下的所有点对于起点来说都是可到达的。

由于这个式子 $w[x] \ge L$ 是判断该子树下的节点是否可达的充分条件，所以我们自然希望 $w[x]$ 尽可能地大。那么我们排序的时候就要以 **$(u,v)$的最小值最大化** 来排序


那么对于终点树：

我们用虚点维护该树下所有点的最大值
，我们需要满足的条件是 $w[x] \le R$ 。

我们显然希望　$w[x]$ 尽可能的小，所以我们排序的关键字就应该是 **$(u,v)$ 的最大值最小化**

我们求完了这两颗重构树了之后在他们上面跑**倍增**和 $dfs$ 序，这样我们就知道了每个子树的编号区间。对于答案统计，我们先让起点和终点 $s,t$ 各自跳到起点树和终点树的相应的节点 $u,v$ ，这两个节点所对应的子树分别对应着 $s,t$ 所能到达的点集。我们只需要知道这两个点集是否有交就行了


然而判断是否有交当然又是我们 ~喜闻乐见~ 的主席树环节了：

我是对于起点树来建的主席树：

对于 **起点树** 上的一个 $dfn_{s}$ 求出它所对应的节点 $pos$ 然后再在 **终点树** 上获取 $pos$ 在终点树上的 $dfn_{t}$ 然后将 $dfn_{t}$ 插入根下标为 $dfn_{s}$ 的主席树中 

那么我们查询的时候只需要知道**终点**在**终点树**上对应的节点 $v$ 的子树的 $dfn_{t}$ 区间 $[l,r]$
在 $u$ 这颗主席树上是否有点就好了

# Code：

include<bits/stdc++.h>

const int N=4e5+5;
const int lg=20;
using namespace std;
int n,m,Q,e_cnt,ans;
struct Grapgh{
int head[N];
struct Edge{
int to,nxt;
}e[N<<2];
void add(int x,int y)
{
e[++e_cnt]=Edge{y,head[x]};
head[x]=e_cnt;
}
void init()
{
for(int i=0;i<N;i++)head[i]=0;
e_cnt=0;
}
int tot;
int f[N][lg+5];
int st[N],ed[N],pos[N],siz[N],w[N];
void dfs(int x,int fa)
{
pos[++tot]=x;st[x]=tot;
f[x][0]=fa;
for(int j=1;j<=lg;j++)f[x][j]=f[f[x][j-1]][j-1];
for(int i=head[x],y;i;i=e[i].nxt)
{
y=e[i].to;
if(yf[x][0])continue;
dfs(y,x);
siz[x]+=siz[y];
}
if(!siz[x])siz[x]=1;
ed[x]=tot;
}
int get_lower(int x,int k)
{
for(int i=lg;i>=0;i--)if(w[f[x][i]]<=k&&f[x][i])x=f[x][i];
return x;
}
int get_upper(int x,int k)
{
for(int i=lg;i>=0;i--)if(w[f[x][i]]>=k&&f[x][i])x=f[x][i];
return x;
}
}G1,G2;
struct edge{
int u,v;
}q[N<<1];
bool cmp1(edge e1,edge e2){
return (e1.u<e1.v ? e1.u : e1.v)>(e2.u<e2.v ? e2.u : e2.v);
}
bool cmp2(edge e1,edge e2){
return (e1.u>e1.v ? e1.u : e1.v)<(e2.u>e2.v ? e2.u : e2.v);
}
struct Kruskal{
int fa[N];
int tot;
int find(int x){return fa[x] = fa[x]x ? fa[x] : find(fa[x]);}
void build(int tag,Grapgh &G)
{
tot=n;
for(int i=0;i<N;i++)fa[i]=i;
for(int i=0;i<n;i++)G.w[i]=i;
for(int i=1;i<=m;i++)
{
int x=find(q[i].u),y=find(q[i].v);
if(x!=y)
{
G.w[++tot]= (tag ? (G.w[x] > G.w[y] ? G.w[x] : G.w[y]) : (G.w[x] < G.w[y] ? G.w[x] : G.w[y]));
G.add(tot,x);G.add(tot,y);
fa[tot]=fa[x]=fa[y]=tot;
}
}
}
}K;
//Segment_Tree
struct Segment_Tree{
int rt[N],cnt;
struct Tree{
int ls,rs,cnt;
}t[N*40];
void insert(int &x,int y,int l,int r,int pos)
{
t[x=++cnt]=t[y];
t[x].cnt++;
if(l==r)return ;
int mid=l+r>>1;
if(pos<=mid)insert(t[x].ls,t[y].ls,l,mid,pos);
if(mid<pos) insert(t[x].rs,t[y].rs,mid+1,r,pos);
}
int query(int x,int y,int l,int r,int L,int R)
{
if(R<L||!y)return 0;
if(L<=l&&r<=R)
{
return -t[x].cnt+t[y].cnt;
}
int mid=l+r>>1;
int res=0;
if(L<=mid)res+=query(t[x].ls,t[y].ls,l,mid,L,R);
if(mid<R) res+=query(t[x].rs,t[y].rs,mid+1,r,L,R);
return res;
}
}T;
int idd[N];
void work()
{
cin>>n>>m>>Q;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&q[i].u,&q[i].v);
}
sort(q+1,q+1+m,cmp1);
K.build(0,G1);
G1.dfs(K.tot,K.tot);
sort(q+1,q+1+m,cmp2);
K.build(1,G2);
G2.dfs(K.tot,K.tot);
for(int i=1;i<=G1.tot;i++)
{
if(G1.pos[i]<=n)
{
int x=G1.pos[i];
T.insert(T.rt[i],T.rt[i-1],0,N,G2.st[x]);
}
else
{
T.rt[i]=T.rt[i-1];
}
}
for(int i=1,s,t,l,r;i<=Q;i++)
{
scanf("%d%d%d%d",&s,&t,&l,&r);
s=G1.get_upper(s,l);
t=G2.get_lower(t,r);
ans=T.query(T.rt[G1.st[s]-1],T.rt[G1.ed[s]],0,N,G2.st[t],G2.ed[t]);
ans = ans>0 ? 1 : 0;
printf("%d\n",ans);
}
}
int main()
{
//freopen("werewolf.in","r",stdin);freopen("werewolf.out","w",stdout);
work();
return 0;
}


又是欢乐的 **kruskal** 重构树捏。

首先我们来仔细研读一下题目：

当你是人形时，你必须避开城市 $0, 1, \ldots , L_i - 1$ ；而当你是狼形时，则必须避开城市 $R_i + 1, R_i + 2, \ldots , N - 1$。

也就是说，从起点开始，你只能走 $[L,n]$ 从终点开始，你只能走 $[1,R]$ 那么我们考虑建两颗 **Kruskal重构树**

以“起点树”为例：
一颗重构树的实点权为该点的编号，虚点权为**该树下点权的最小值** ，这样我们就能保证在此树下，只要满足　$w[x] \ge L$ 那么这个树下的所有点对于起点来说都是可到达的。

由于这个式子 $w[x] \ge L$ 是判断该子树下的节点是否可达的充分条件，所以我们自然希望 $w[x]$ 尽可能地大。那么我们排序的时候就要以 **$(u,v)$的最小值最大化** 来排序


那么对于终点树：

我们用虚点维护该树下所有点的最大值
，我们需要满足的条件是 $w[x] \le R$ 。

我们显然希望　$w[x]$ 尽可能的小，所以我们排序的关键字就应该是 **$(u,v)$ 的最大值最小化**

我们求完了这两颗重构树了之后在他们上面跑**倍增**和 $dfs$ 序，这样我们就知道了每个子树的编号区间。对于答案统计，我们先让起点和终点 $s,t$ 各自跳到起点树和终点树的相应的节点 $u,v$ ，这两个节点所对应的子树分别对应着 $s,t$ 所能到达的点集。我们只需要知道这两个点集是否有交就行了


然而判断是否有交当然又是我们 ~喜闻乐见~ 的主席树环节了：

我是对于起点树来建的主席树：

对于 **起点树** 上的一个 $dfn_{s}$ 求出它所对应的节点 $pos$ 然后再在 **终点树** 上获取 $pos$ 在终点树上的 $dfn_{t}$ 然后将 $dfn_{t}$ 插入根下标为 $dfn_{s}$ 的主席树中 

那么我们查询的时候只需要知道**终点**在**终点树**上对应的节点 $v$ 的子树的 $dfn_{t}$ 区间 $[l,r]$
在 $u$ 这颗主席树上是否有点就好了

# Code：

include<bits/stdc++.h>

const int N=4e5+5;
const int lg=20;
using namespace std;
int n,m,Q,e_cnt,ans;
struct Grapgh{
int head[N];
struct Edge{
int to,nxt;
}e[N<<2];
void add(int x,int y)
{
e[++e_cnt]=Edge{y,head[x]};
head[x]=e_cnt;
}
void init()
{
for(int i=0;i<N;i++)head[i]=0;
e_cnt=0;
}
int tot;
int f[N][lg+5];
int st[N],ed[N],pos[N],siz[N],w[N];
void dfs(int x,int fa)
{
pos[++tot]=x;st[x]=tot;
f[x][0]=fa;
for(int j=1;j<=lg;j++)f[x][j]=f[f[x][j-1]][j-1];
for(int i=head[x],y;i;i=e[i].nxt)
{
y=e[i].to;
if(yf[x][0])continue;
dfs(y,x);
siz[x]+=siz[y];
}
if(!siz[x])siz[x]=1;
ed[x]=tot;
}
int get_lower(int x,int k)
{
for(int i=lg;i>=0;i--)if(w[f[x][i]]<=k&&f[x][i])x=f[x][i];
return x;
}
int get_upper(int x,int k)
{
for(int i=lg;i>=0;i--)if(w[f[x][i]]>=k&&f[x][i])x=f[x][i];
return x;
}
}G1,G2;
struct edge{
int u,v;
}q[N<<1];
bool cmp1(edge e1,edge e2){
return (e1.u<e1.v ? e1.u : e1.v)>(e2.u<e2.v ? e2.u : e2.v);
}
bool cmp2(edge e1,edge e2){
return (e1.u>e1.v ? e1.u : e1.v)<(e2.u>e2.v ? e2.u : e2.v);
}
struct Kruskal{
int fa[N];
int tot;
int find(int x){return fa[x] = fa[x]x ? fa[x] : find(fa[x]);}
void build(int tag,Grapgh &G)
{
tot=n;
for(int i=0;i<N;i++)fa[i]=i;
for(int i=0;i<n;i++)G.w[i]=i;
for(int i=1;i<=m;i++)
{
int x=find(q[i].u),y=find(q[i].v);
if(x!=y)
{
G.w[++tot]= (tag ? (G.w[x] > G.w[y] ? G.w[x] : G.w[y]) : (G.w[x] < G.w[y] ? G.w[x] : G.w[y]));
G.add(tot,x);G.add(tot,y);
fa[tot]=fa[x]=fa[y]=tot;
}
}
}
}K;
//Segment_Tree
struct Segment_Tree{
int rt[N],cnt;
struct Tree{
int ls,rs,cnt;
}t[N*40];
void insert(int &x,int y,int l,int r,int pos)
{
t[x=++cnt]=t[y];
t[x].cnt++;
if(l==r)return ;
int mid=l+r>>1;
if(pos<=mid)insert(t[x].ls,t[y].ls,l,mid,pos);
if(mid<pos) insert(t[x].rs,t[y].rs,mid+1,r,pos);
}
int query(int x,int y,int l,int r,int L,int R)
{
if(R<L||!y)return 0;
if(L<=l&&r<=R)
{
return -t[x].cnt+t[y].cnt;
}
int mid=l+r>>1;
int res=0;
if(L<=mid)res+=query(t[x].ls,t[y].ls,l,mid,L,R);
if(mid<R) res+=query(t[x].rs,t[y].rs,mid+1,r,L,R);
return res;
}
}T;
int idd[N];
void work()
{
cin>>n>>m>>Q;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&q[i].u,&q[i].v);
}
sort(q+1,q+1+m,cmp1);
K.build(0,G1);
G1.dfs(K.tot,K.tot);
sort(q+1,q+1+m,cmp2);
K.build(1,G2);
G2.dfs(K.tot,K.tot);
for(int i=1;i<=G1.tot;i++)
{
if(G1.pos[i]<=n)
{
int x=G1.pos[i];
T.insert(T.rt[i],T.rt[i-1],0,N,G2.st[x]);
}
else
{
T.rt[i]=T.rt[i-1];
}
}
for(int i=1,s,t,l,r;i<=Q;i++)
{
scanf("%d%d%d%d",&s,&t,&l,&r);
s=G1.get_upper(s,l);
t=G2.get_lower(t,r);
ans=T.query(T.rt[G1.st[s]-1],T.rt[G1.ed[s]],0,N,G2.st[t],G2.ed[t]);
ans = ans>0 ? 1 : 0;
printf("%d\n",ans);
}
}
int main()
{
//freopen("werewolf.in","r",stdin);freopen("werewolf.out","w",stdout);
work();
return 0;
}

标签：cnt,IOI2018,return,int,狼人,pos,tot,fa,P4899
From： https://www.cnblogs.com/LG017/p/18590483

相关文章

  • 上海计算机学会2022年5月月赛C++乙组T3狼人游戏（二）
    狼人游戏（二）内存限制: 256 Mb时间限制: 1000 ms题目描述有 n 名玩家在玩狼人游戏，有一些玩家的身份是狼人。其余玩家的身份是预言家。游戏的进程中，陆续出现了 m 句发言，每句发言来自于某个玩家，发言的信息是声称另一个玩家的身份是狼人或者是预言家。小爱猜想，狼人的发......
  • C++狼人杀游戏
    #include<bits/stdc++.h>#include<cstdio>#include<cstdlib>#include<ctime>#include<windows.h>usingnamespacestd;structIDname{intgeshu;stringNAME;};IDnamejue_se[100];structID{intnum;boollife;......
  • 和GPT-4这些大模型玩狼人杀，人类因太蠢被票死，真·反向图灵测试
    最近，一位昵称「ToreKnabe」的网友在X平台发布的一段视频引发了人们的讨论。这是一次「反向图灵测试」，几个全球最先进的大模型坐在一起，坐着火车唱着歌，但其中混进了人类：而AI的任务，是把这个人类揪出来。最近，一位昵称「ToreKnabe」的网友在X平台发布的一段视频引发了......
  • c++游戏 狼人杀（升级）
    代码：#include<iostream>//C++输入输出流库#include<cstdlib>//使用srand函数要用到这个库#include<ctime>//使用time函数要用到这个库#include<Windows.h>#include<conio.h>longlongsr=0;usingnamespacestd;voidbrc(){ system("cls"); lon......
  • 狼人杀好局记录
    第一局：wky裁判。逆时针依次xyl，xyj，gxr，yk，wzy，czl。第一晚，xyl和czl死了。第二天白天，xyj跳女巫，说自己毒了xyl。yk跳预言家，验了xyl是狼。gxr跳女巫，说她毒了czl，踩xyj。我直接支持xyj（主要是关照到上局她真预言家被xyl反跳跳死，我相信她有充足的理由毒xyl）选警长，yk......
  • P4899 [IOI2018] werewolf 狼人 题解
    因为我记忆力不好，经常遇到之前做过的题一下子想不起来，所以打算基本上给每个比较有意思的题写题解，同时造福后代。这是werewolf，它是furry，很可爱题意：一张无向图，点有点权，每次询问从\(u\)到\(v\)的路径中，是否存在一条先走点权大于等于\(L\)，再走点权小于等于\(R\)的路径。思路......
  • DreadHunger恐惧饥荒海上狼人杀服务器配置要求
    DreadHunger恐惧饥荒海上狼人杀服务器配置要求大家好我是艾西，在这几天DreadHunger恐惧饥荒海上狼人杀技术组对于客户端做了一些调整修复，对于之前开房间只能默认7777端口做出了调整。目前经过我自己的测试是可以完全设置成你自己想要的端口，官方客户端更新固定游戏端口的设置，改成随机......
  • DreadHunger恐惧饥荒海上狼人杀服务器搭建架设教程windows系统
    DreadHunger恐惧饥荒海上狼人杀服务器搭建架设教程windows系统大家好我是艾西，在11月底我有发文DreadHunger恐惧饥荒海上狼人杀官方停服的消息，当时在官方的公告模版中公布了在2024年一月一日会将服务端公开让喜欢玩这个游戏的玩家能够继续的快乐其中。经过漫长的等待DreadHunger工作......
  • Dread Hunger恐惧饥荒服务器语言与阴谋的狼人杀对决
    DreadHunger恐惧饥荒服务器语言与阴谋的狼人杀对决大家好我是艾西，今天跟大家聊下DreadHunger这一款开放世界冒险，生存与背叛的8人游戏以航海为题材的狼人杀游戏。一场关于生存与背叛为主题的海上狼人杀游戏，八位探险家将乘着船只航行过残酷的北极，而船上有两位叛徒呼唤了黑暗的力量......
  • P4899 [IOI2018] werewolf 狼人 题解
    P4899[IOI2018]werewolf狼人题解题目描述省流：\(n\)个点，\(m\)条边，\(q\)次询问，对于每一次询问，给定一个起点\(S\)和终点\(T\)，能否找到一条路径，前半程不能走\(0\thicksimL-1\)这些点，后半程不能走\(R+1\thicksimN-1\)这些点。中途必须有一个点在\(L\thicksimR\)之......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99