[Codeforces375D]Tree and Queries（莫队+分块）

2019-11-08 01:31:18

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

搞一个dfs序然后就变成了询问一坨区间莫队刚开始写了个bit结果tle 实际上写一个分块，维护块内和，然后O(1) $O(1)$ 修改O(n√) $O(/sqrt n)$ 查询就可以了因为 ATP：修改次数非常多，能达到nn√ $n/sqrt n$ ，但是查询次数不会超过m $m$

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 200005int n,m,x,y,dfs_clock,block,t;int tot,point[N],nxt[N*2],v[N*2];int in[N],out[N],pt[N],cnt[N],c[N],a[N],sum[N];struct data{int k,l,r,id,ans;}q[N];int L[N],R[N],num[N];void add(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}void dfs(int x,int fa){ in[x]=++dfs_clock;pt[dfs_clock]=x; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa) dfs(v[i],x); out[x]=dfs_clock;}int cmp(data a,data b){ return num[a.l]<num[b.l]||(num[a.l]==num[b.l]&&num[a.r]<num[b.r]);}void change(int x,int val){ sum[num[x]]-=a[x]; a[x]+=val; sum[num[x]]+=a[x];}int query(int x){ int ans=0; if (x>n) return ans; if (x==L[num[x]]) x=num[x]; else { for (int i=x;i<=R[num[x]];++i) ans+=a[i]; x=num[x]+1; } for (int i=x;i<=t;++i) ans+=sum[i]; return ans;}void modui(int l,int r,int f){ for (int i=l;i<=r;++i) { int x=pt[i]; if (cnt[c[x]]) change(cnt[c[x]],-1); cnt[c[x]]+=f; if (cnt[c[x]]) change(cnt[c[x]],1); }}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%d",&c[i]); for (int i=1;i<n;++i) { scanf("%d%d",&x,&y); add(x,y),add(y,x); } dfs(1,0); for (int i=1;i<=m;++i) { scanf("%d%d",&x,&q[i].k); q[i].l=in[x],q[i].r=out[x];q[i].id=i; } block=sqrt(n);t=(n-1)/block+1; for (int i=1;i<=n;++i) num[i]=(i-1)/block+1; L[1]=1,R[1]=block; for (int i=2;i<=t;++i) L[i]=L[i-1]+block,R[i]=R[i-1]+block;R[t]=n; sort(q+1,q+m+1,cmp); modui(q[1].l,q[1].r,1); q[q[1].id].ans=query(q[1].k); for (int i=2;i<=m;++i) { if (q[i-1].l<q[i].l) modui(q[i-1].l,q[i].l-1,-1); else modui(q[i].l,q[i-1].l-1,1); if (q[i-1].r<q[i].r) modui(q[i-1].r+1,q[i].r,1); else modui(q[i].r+1,q[i-1].r,-1); q[q[i].id].ans=query(q[i].k); } for (int i=1;i<=m;++i) PRintf("%d/n",q[i].ans);}

上一篇：JS：计算两数之间所有整数的最小公倍数

下一篇：JS：计算数列中小于等于num的所有质数之和

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注