首页 > 代码库 > HDU 5877 dfs+ 线段树（或+树状树组）

HDU 5877 dfs+ 线段树（或+树状树组）

2024-08-15 13:55:56   219人阅读

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;}
View Code

 

（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;}
View Code

 

HDU 5877 dfs+ 线段树（或+树状树组）


联系
我们