洛谷P3605 [USACO17JAN]Promotion Counting——线段树合并

蔚落 2023-06-04 07:59 39阅读 0赞

**![1596060-20190723213337543-1333116821.png][]**

![1596060-20190723213407865-1425281841.png][]

![1596060-20190723213426046-1579887520.png][]

**线段树合并裸题，其实这道题就可以看作每一个点的子树中比它的点权大的值的个数。****看这道题的值域范围，知道要用动态开点的线段树，然后我们可以将p数组离散化，每一个点都建一棵对应的值域线段树。最后从根节点开始遍历，回溯时将有上司和下属关系的点合并即可。**

**而关键是合并操作：**

**![1596060-20190723213953027-1468753964.png][]**

**其实还是很好理解的，我的代码没有新开一个节点，就相当于把y合并到x上，从根节点开始，向下递归更新即可，还是比较暴力的。**

**完整代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=3e6+7;
    struct node{
        int nxt;
        int to;
    }edge[maxn*2];
    int lc[maxn],rc[maxn];
    int T;
    int a[maxn],p[maxn];
    int root[maxn];
    struct seg{
        int val;
    }tree[maxn*3];
    int head[maxn],tot;
    int n;
    int x;
    int neww;
    int ans[maxn];
    void add(int x,int y){
        edge[++tot].nxt=head[x];
        edge[tot].to=y;
        head[x]=tot;
    }
    void build(int &node,int l,int r,int x){
        if(!node) node=++T;
        if(l==r){
            tree[node].val++;
            return;
        } 
        int mid=(l+r)>>1;
        if(x<=mid){
            build(lc[node],l,mid,x);
        } 
        else{
            build(rc[node],mid+1,r,x);
        }
        tree[node].val=tree[lc[node]].val+tree[rc[node]].val; 
    }
    void merge(int &x,int y){
        if(!x||!y){
            x=x+y;
            return;
        }
        tree[x].val=tree[x].val+tree[y].val;
        merge(lc[x],lc[y]);
        merge(rc[x],rc[y]);
    }
    int query(int node,int l,int r,int v){
        if(l==r) return 0;
        int mid=(l+r)>>1;
        if(v<=mid) return query(lc[node],l,mid,v)+tree[rc[node]].val;
        else return query(rc[node],mid+1,r,v); 
    }
    void dfs(int x){
        for(int i=head[x];i;i=edge[i].nxt){
            int v=edge[i].to;
            dfs(v);
            merge(root[x],root[v]);//回溯时暴力合并 
        }
        ans[x]=query(root[x],1,neww,p[x]);
    }
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&p[i]);
            a[i]=p[i];
        } 
        std::sort(a+1,a+1+n);
        neww=unique(a+1,a+1+n)-a-1;
        for(int i=2;i<=n;i++){
            scanf("%d",&x);
            add(x,i);
        }
        for(int i=1;i<=n;i++){
            p[i]=lower_bound(a+1,a+1+neww,p[i])-a;//离散化 
            build(root[i],1,neww,p[i]);
        }
        dfs(1);
        for(int i=1;i<=n;i++){
            printf("%d\n",ans[i]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11234726.html

[1596060-20190723213337543-1333116821.png]: /images/20230601/f1e9a20a19d84210aade38ffd6233de0.png
[1596060-20190723213407865-1425281841.png]: /images/20230601/ec6b8ad896334278b21db66cf0e52b17.png
[1596060-20190723213426046-1579887520.png]: /images/20230601/e9e2ac2c430b4120be87d5935fffb8ab.png
[1596060-20190723213953027-1468753964.png]: /images/20230601/be1ece339a514947816e03c840254c75.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/c0ee46fb29bc449ba0a963f7f3747c95.png