首页 > 代码库 > HDU 5877 dfs+ 线段树（或+树状树组）
HDU 5877 dfs+ 线段树（或+树状树组）
1、HDU 5877 Weak Pair
2、总结：有多种做法，这里写了dfs+线段树（或+树状树组），还可用主席树或平衡树，但还不会这两个
3、思路：利用dfs遍历子节点，同时对于每个子节点au，查询它有多少个祖先av满足av<=k/au。
（1）dfs+线段树
#include<iostream>#include<cstring>#include<cmath>#include<queue>#include<algorithm>#include<cstdio>#define F(i,a,b) for (int i=a;i<b;i++)#define FF(i,a,b) for (int i=a;i<=b;i++)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define LL long longusing namespace std;const int N=101000,MAX=1000100;LL k,a[N],b[N*2];int n,m,tree[N*8],head[N],in[N]; //注：N*8，不是N*4，因为m可能会是n的2倍struct Edge{ int to,nexte;}edge[N*2];int tot;void AddEdge(int u,int v){ edge[tot].to=v; edge[tot].nexte=head[u]; head[u]=tot++;}void update(int pos,int l,int r,int ro,int val){ if(l==r){ tree[ro]+=val; return ; } int mid=(l+r)>>1; if(pos<=mid)update(pos,l,mid,ro<<1,val); else update(pos,mid+1,r,ro<<1|1,val); tree[ro]=tree[ro<<1]+tree[ro<<1|1];}int query(int R,int l,int r,int ro,int L){ if(R>=r&&l>=L){ //注：返回条件 return tree[ro]; } int mid=(l+r)>>1; if(R<=mid)return query(R,l,mid,ro<<1,L); else if(L>mid)return query(R,mid+1,r,ro<<1|1,L); else return query(mid,l,mid,ro<<1,L)+query(R,mid+1,r,ro<<1|1,mid+1); //注：要拆分区间}LL ans;void dfs(int r){ int pos=lower_bound(b+1,b+1+m,a[r])-b; //注：lower_bound()， -b不是-(b+1) int posk=lower_bound(b+1,b+1+m,k/a[r])-b; ans+=1ll*query(posk,1,m,1,1); update(pos,1,m,1,1); for(int i=head[r];i!=-1;i=edge[i].nexte){ dfs(edge[i].to); //利用dfs序遍历子孙 } update(pos,1,m,1,-1);}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%I64d",&n,&k); FF(i,1,n){ scanf("%I64d",&a[i]); b[i]=a[i]; } m=n; FF(i,1,n) b[++m]=k/a[i]; sort(b+1,b+1+m); //排序，离散基础 m=unique(b+1,b+1+m)-(b+1); //注：unique()， -(b+1)不是-b mes(head,-1); int u,v; mes(in,0); ans=tot=0; FF(i,1,n-1){ scanf("%d%d",&u,&v); AddEdge(u,v); in[v]++; } mes(tree,0); FF(i,1,n){ if(!in[i]){ dfs(i);break; } } printf("%I64d\n",ans); } return 0;}
（2）dfs+树状树组
这个刚学，还不太懂
#include<iostream>#include<cstring>#include<cmath>#include<queue>#include<algorithm>#include<cstdio>#define F(i,a,b) for (int i=a;i<b;i++)#define FF(i,a,b) for (int i=a;i<=b;i++)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define LL long longusing namespace std;const int N=100100,MAX=1000100;LL k,a[N],b[N*2],c[N*2];int n,m,head[N],in[N];struct Edge{ int to,nexte;}edge[N*2];int tot;void AddEdge(int u,int v){ edge[tot].to=v; edge[tot].nexte=head[u]; head[u]=tot++;}int Lowbit(int x){ return x&(-x);}void update(int pos,int val){ for(int i=pos;i<=m;i+=Lowbit(i)){ //注 c[i]+=val; }}LL Sum(int posk){ LL ans=0; for(int i=posk;i>0;i-=Lowbit(i)){ //注 ans+=c[i]; } return ans;}LL ans;void dfs(int r){ int pos=lower_bound(b+1,b+1+m,a[r])-b; int posk=upper_bound(b+1,b+1+m,k/a[r])-(b+1); //注：upper_bound()，-(b+1)不是-b ans+=Sum(posk); update(pos,1); for(int i=head[r];i!=-1;i=edge[i].nexte){ dfs(edge[i].to); } update(pos,-1);}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%I64d",&n,&k); FF(i,1,n){ scanf("%I64d",&a[i]); b[i]=a[i]; } m=n; FF(i,1,n) b[++m]=k/a[i]; sort(b+1,b+1+m); m=unique(b+1,b+1+m)-(b+1); mes(head,-1); mes(c,0); int u,v; mes(in,0); ans=tot=0; FF(i,1,n-1){ scanf("%d%d",&u,&v); AddEdge(u,v); in[v]++; } FF(i,1,n){ if(!in[i]){ dfs(i);break; } } printf("%I64d\n",ans); } return 0;}
HDU 5877 dfs+ 线段树（或+树状树组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。