本文主要是介绍【NOI2018模拟4.4】Map，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
Rin是个特别好动的少女。
一天Rin来到了一个遥远的都市。这个都市有N个建筑，编号从1到N，其中市中心编号为1，这个都市有M条双向通行的街道，每条街道连接着两个不同的建筑，其中某些街道首尾相连连接成了一个环。Rin通过长时间的走访，已经清楚了这个都市的两个特点：
从市中心出发可以到达所有的建筑物。
任意一条街道最多存在与一个简单环中。令Rin心花怒放的是，每个建筑物都会有拉面售卖。拉面有很多不同的种类，但对于Rin而言只有油腻程度的不同，因此我们把油腻程度相同的拉面看做同一种拉面。由于不同建筑物的拉面的油腻程度可能不同，我们用一个正整数来表示拉面的油腻程度。
要知道，拉面可是Rin的最爱，但是现在到了下班高峰期，都市的交通变得非常的堵塞。Rin只能通过没有被堵死的街道通行，去品尝所在建筑物的拉面。
现在Rin想知道，如果她正在编号为x的建筑物，那么在从市中心到x的所有简单路径经过的街道都被堵死的情况下，Rin可以品尝到的拉面中（注意没有出现的拉面是不能算在里面的）：
油腻程度<=y且品尝次数为奇数次的拉面有多少种？
油腻程度<=y且品尝次数为偶数次的拉面有多少种？
Input
第一行两个正整数N,M，含义如题所示。
第二行一共N个正整数，第i个数Ai表示第i个建筑物出售的拉面的油腻程度。
接下来M行，每行两个正整数x,y，表示在建筑物x,y之间有一条双向通行的街道。数据保证1<=x,y<=N。
接下来一行一个正整数Q，表示询问个数。
接下来Q行每行三个非负整数ty,x,y，x表示询问的建筑物编号，y表示油腻程度的限制，ty=0时表示询问偶数，ty=1表示询问奇数。
Output
一共q行，对于每个询问输出一个答案。
Sample Input
5 6
2 1 6 7 7
1 2
1 3
2 4
4 5
4 5
1 3
3
0 3 2
0 3 1
0 1 7
Sample Output
0
0
1
Data Constraint
Solution
仙人掌，有一种套路变成树：详细点这里查看
大概就是弄出环顶，把环上的点连到环顶上。这样和树就完全相同了。
树怎么做呢？
对于每个点，开一个线段树表示每个点的每种拉面偶数次和奇数次的有多少种，维护很简单，线段树合并一下就行了。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 101000
using namespace std;
int n,m,a[N],last[N],nxt[N*5],to[N*5],tot=1,fa[N],dfn[N],s[N],K;
int root[N],q[N][3],las[N],xnt[N],dat[N],son[N],sz[N],ans[N],b[N],c[N],d[1010000],qu;
struct node{int l,r,d1,d2;
}t[N*70];
void putin(int x,int y)
{nxt[++tot]=last[x];last[x]=tot;to[tot]=y;
}
void putsin(int x,int y)
{xnt[++tot]=las[x];las[x]=tot;dat[tot]=y;
}
bool cnt(int x,int y){return c[x]<c[y];}
void tarjan(int x,int fat)
{dfn[x]=++tot;s[++s[0]]=x;for(int i=last[x];i;i=nxt[i])if(i!=fat){int y=to[i];if(dfn[y]>0){if(dfn[y]<dfn[x]) for(int z=s[0];s[z]!=y;z--) fa[s[z]]=y;continue;}tarjan(y,i^1);if(fa[y]==0) fa[y]=x;}s[0]--;
}
void dg(int x)
{sz[x]=1;for(int i=last[x];i;i=nxt[i]){int y=to[i];dg(y);sz[x]+=sz[y];if(sz[y]>sz[son[x]]) son[x]=y;}
}
void add(int &x)
{if(x>0) return;x=++tot;
}
void update(int v)
{t[v].d1=t[t[v].l].d1+t[t[v].r].d1;t[v].d2=t[t[v].l].d2+t[t[v].r].d2;
}
void merge(int v1,int v2,int i,int j)
{if(i==j){int x=t[v1].d1^t[v2].d1;if(x==0) t[v1].d1=1,t[v1].d2=0;else t[v1].d1=0,t[v1].d2=1;return;}int m=(i+j)/2;if(t[v1].l==0) t[v1].l=t[v2].l;else if(t[v2].l>0) merge(t[v1].l,t[v2].l,i,m);if(t[v1].r==0) t[v1].r=t[v2].r;else if(t[v2].r>0) merge(t[v1].r,t[v2].r,m+1,j);update(v1);}
void change(int v,int i,int j,int x)
{if(i==j){if(t[v].d1+t[v].d2==0) t[v].d2=1;else t[v].d1=1-t[v].d1,t[v].d2=1-t[v].d2;return;}int m=(i+j)/2;if(x<=m) add(t[v].l),change(t[v].l,i,m,x);else add(t[v].r),change(t[v].r,m+1,j,x);update(v);
}
int get(int v,int i,int j,int x,int y,int z)
{if(v==0) return 0;if(i==x&&j==y){if(z==0) return t[v].d1;else return t[v].d2;}int m=(i+j)/2;if(y<=m) return get(t[v].l,i,m,x,y,z);else if(x>m) return get(t[v].r,m+1,j,x,y,z);else return get(t[v].l,i,m,x,m,z)+get(t[v].r,m+1,j,m+1,y,z);
}
void dfs(int x)
{if(son[x]>0){dfs(son[x]);root[x]=root[son[x]];}else root[x]=++tot;for(int i=last[x];i;i=nxt[i]){int y=to[i];if(y==son[x]) continue;dfs(y);merge(root[x],root[y],1,K);}change(root[x],1,K,a[x]);for(int i=las[x];i;i=xnt[i]){int y=dat[i];if(q[y][2]>c[b[n]]) d[q[y][2]]=K;if(d[q[y][2]]>0) ans[y]=get(root[x],1,K,1,d[q[y][2]],q[y][0]);}
}
int main()
{freopen("map.in","r",stdin);freopen("map.out","w",stdout);scanf("%d%d",&n,&m);fo(i,1,n) scanf("%d",&c[i]),b[i]=i;sort(b+1,b+n+1,cnt);fo(i,1,n){if(c[b[i]]>c[b[i-1]]) K++;fo(j,c[b[i-1]],c[b[i]]-1) d[j]=K-1;a[b[i]]=K;}d[c[b[n]]]=K;fo(i,1,m){int x,y;scanf("%d%d",&x,&y);putin(x,y);putin(y,x);}tot=0;tarjan(1,0);memset(last,0,sizeof(last));tot=0;fo(i,2,n) putin(fa[i],i);dg(1);tot=0;scanf("%d",&qu);fo(i,1,qu){scanf("%d%d%d",&q[i][0],&q[i][1],&q[i][2]);putsin(q[i][1],i);}tot=0;dfs(1);fo(i,1,qu) printf("%d\n",ans[i]);
}这篇关于【NOI2018模拟4.4】Map的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
