指针-动态开点&合并线段树

一个知识点不在一道题里说是没有灵魂的

线段树是用来处理区间信息的咯

但是往往因为需要4倍空间让许多人退却，而动态开点的线段树就非常棒

仿佛只用2倍就可以咯

指针保存位置，即节点信息，是很舒适的，所以用指针动态开点就更棒

<永无乡题面>

这个题哈，我刚开始学线段树合并时惯例懵，

而且我发现……网上的题解有简短甚至偷懒的，于是我很废了，去问神犇

下面就是，比较清楚的题解

首先我们会发现这个题像一个，图论？

但是并不是，因为他问的并不是图的问题（像最短路？），而是联通性，和排名下标，就不用建图

So，分开考虑

1.联通性：dfs的是想岔了，冰茶几（并查集）适合维护这个-----> O（logN）

2.排名下标：

平衡树，不会合并（哭笑不得）

线段树，不错，如果用权值线段树就可以查排名咯

权值线段树，类似于桶排序，用下标存数，每个节点存的是从L到R的数个数

这样一个数的排名就是左面的节点中个数加一

自带二分，非常快

然后就是合并的操作（这个去专门学也好），用不空的节点直接代替空的节点，把不空的公共节点值相加

另外再说一句，我用指针的new函数了，所以慢死，我从大佬们处得知指针要与结构体数组一块用，达到既美观直观又快的效果

结果：

#include<iostream>

#include<cstring>

#include<cstdio>

#define N 100010

using namespace std;

struct XDS{

    XDS *lid,*rid;

    int dat,l,r;

    XDS(){

        lid=rid=NULL;

        dat=l=r=0;

    }

};XDS *root[N];

int itd[N];

void Build(XDS *&rt,int l,int r){

    rt=new XDS();

    rt->l=l;

    rt->r=r;

}

void add(XDS *&rt,int l,int r,int v){//puts("1");

    rt->l=l;

    rt->r=r;

    if(l==r){

        rt->dat++;

        return ;

    }

    int mid=(l+r)/2;

    if(v<=mid){

        if(rt->lid==NULL) rt->lid=new XDS();

        add(rt->lid,l,mid,v);

    }

    else{

        if(rt->rid==NULL) rt->rid=new XDS();

        add(rt->rid,mid+1,r,v);

    }

    if(rt->lid!=NULL)

        rt->dat+=rt->lid->dat;

    if(rt->rid!=NULL)

        rt->dat+=rt->rid->dat;

}

inline void Add(XDS *&rt,int v){

    add(rt,rt->l,rt->r,v);

}

int kth(XDS *rt,int k){

    if(rt->dat<k)return -1;

    int n=-1;

    if(rt->l==rt->r){

        return rt->dat==0?-1:itd[rt->l];

    }

    if(rt->lid!=NULL&&rt->lid->dat>=k){

        n=kth(rt->lid,k);

    }

    else if(rt->rid!=NULL){

        if(rt->lid!=NULL)

            n=kth(rt->rid,k-rt->lid->dat);

        else{

            n=kth(rt->rid,k);

        }

    }

    return n;

}

XDS* mmerge(int l,int r,XDS *a,XDS *b){

    if(a==NULL)return b;

    if(b==NULL)return a;

    XDS *c;Build(c,l,r);

    c->dat=a->dat+b->dat;

    if(l==r)return c;

    int mid=(l+r)/2;

    c->lid=mmerge(l,mid,a->lid,b->lid);

    c->rid=mmerge(mid+1,r,a->rid,b->rid);

    return c;

}

int fa[N];

int faind(int x){

    if(x!=fa[x]){

        delete root[x];

        fa[x]=faind(fa[x]);

    }

    return fa[x];

}

int isn,bn;

void prerun(){

    int a;

    for(int i=1;i<=isn;i++){

        fa[i]=i;

        Build(root[i],0,100000);

        scanf("%d",&a);

        itd[a]=i;

        Add(root[i],a);

    }

}

void unity(int x,int y){

    x=faind(x);

    y=faind(y);

    if(x!=y){

        fa[x]=y;

        root[y]=mmerge(0,100000,root[x],root[y]);

        delete root[x];

        root[x]=NULL;

    }

}

int main(){

    int a,b,c;

    scanf("%d%d",&isn,&bn);

    prerun();

    for(int i=1;i<=bn;i++){

        scanf("%d%d",&b,&c);

        unity(b,c);

    }

    char ch[3];

    scanf("%d",&a);

    for(int i=1;i<=a;i++){

        scanf("%s%d%d",ch,&b,&c);

        if(ch[0]=='Q'){

            int q=faind(b);

            printf("%d\n",kth(root[q],c));

        }

        else{

            unity(b,c);

        }

    }

    return 0;

}

巴特西

指针-动态开点&合并线段树

最新文章

热门文章