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

提示：请注意数据范围中的<= ，特殊条件中提到的y均为询问中的y

Hint

3号建筑物只能到达它自己，而 1号建筑物可以到达所有建筑物。

Solution

• 看到这种区间的询问问题，就可以考虑莫队算法。

• 但是首先要把询问节点对应的子树转化成一个个连续的区间。

• 于是先做一遍正常 tarjan ，再 dfs 一遍，如果一个点 x 连出去是 y，又满足：

  low[y]≥dfn[x]

• 则将 y 作为 x 的子树，否则就将 y 作为 low[y] 的子树即可。

• 这样对 n 个点分块，再对值域也分块，直接莫队即可。

• 时间复杂度 O(NN−−√) 。

Code

#include<cstdio> #include<algorithm> #include<cmath> #include<cctype> using namespace std; const int N=1e5+5; struct data {int l,r,ty,y,n,id; }f[N]; int tot,sn,sv; int first[N],nex[N*3],en[N*3]; int a[N],b[N],ans[N],g[N/100+5][2],cnt[N*10]; int dfn[N],low[N],num[N],id[N],size[N]; bool bz[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline int max(int x,int y) {return x>y?x:y; } inline int min(int x,int y) {return x<y?x:y; } inline void insert(int x,int y) {nex[++tot]=first[x];first[x]=tot;en[tot]=y; } void tarjan(int x,int y) {num[dfn[x]=low[x]=++tot]=x;for(int i=first[x];i;i=nex[i])if(en[i]^y)if(!dfn[en[i]]){tarjan(en[i],x);low[x]=min(low[x],low[en[i]]);}else low[x]=min(low[x],dfn[en[i]]); } void dfs(int x) {id[x]=++tot,bz[x]=size[x]=1;for(int i=first[x];i;i=nex[i])if(!bz[en[i]] && low[en[i]]>=dfn[x]){dfs(en[i]);size[x]+=size[en[i]];}for(int i=first[x];i;i=nex[i])if(!bz[en[i]]){dfs(en[i]);size[num[low[en[i]]]]+=size[en[i]];} } inline bool cmp(data x,data y) {return x.n<y.n || x.n==y.n && x.r<y.r; } inline void update(int x,bool p) {int pos=(b[x]-1)/sv+1;if(p){if(cnt[b[x]]&1) g[pos][0]++,g[pos][1]--; elseif(cnt[b[x]]) g[pos][0]--,g[pos][1]++; else g[pos][1]++;cnt[b[x]]++;}else{if(cnt[b[x]]==1) g[pos][1]--; elseif(cnt[b[x]]&1) g[pos][1]--,g[pos][0]++; else g[pos][1]++,g[pos][0]--;cnt[b[x]]--;} } inline int calc(int x,int p) {int sum=0,pos=(x-1)/sv+1;for(int i=1;i<pos;i++) sum+=g[i][p];for(int i=(pos-1)*sv+1;i<=x;i++)if(cnt[i] && (cnt[i]&1)==p) sum++;return sum; } int main() {int n=read(),m=read();for(int i=1;i<=n;i++) sv=max(sv,a[i]=read());sn=sqrt(n),sv=sqrt(sv);for(int i=1;i<=m;i++){int x=read(),y=read();insert(x,y);insert(y,x);}tarjan(1,tot=0);tot=0,dfs(1);for(int i=1;i<=n;i++) b[id[i]]=a[i];int q=read();for(int i=1;i<=q;i++){f[i].ty=read();int x=read();f[i].l=id[x],f[i].r=id[x]+size[x]-1;f[i].y=read();f[i].id=i,f[i].n=(f[i].l-1)/sn+1;}sort(f+1,f+1+q,cmp);for(int i=1,l=1,r=0;i<=q;i++){while(l>f[i].l) update(--l,true);while(r<f[i].r) update(++r,true);while(l<f[i].l) update(l++,false);while(r>f[i].r) update(r--,false);ans[f[i].id]=calc(f[i].y,f[i].ty);}for(int i=1;i<=q;i++) write(ans[i]),putchar('\n');return 0; } 与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的JZOJ 5629. 【NOI2018模拟4.4】Map的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。