BZOJ-4399: 魔法少女LJJ

[文章目录]

Description

1.新建一个节点,权值为x。
2.连接两个节点。
3.将一个节点a所属于的联通快内权值小于x的所有节点权值变成x。
4.将一个节点a所属于的联通快内权值大于x的所有节点权值变成x。
5.询问一个节点a所属于的联通块内的第k小的权值是多少。
6.询问一个节点a所属联通快内所有节点权值之积与另一个节点b所属联通快内所有节点权值之积的大小。
7.询问a所在联通快内节点的数量
0<=m<=400000,c<=7,所有出现的数均<=1000000000

达成成就:获得新外号 LJJ!!!(神**魔法少女)
有查询第k大,有合并。有修改,还是明显告诉你是线段树的打标记修改为空。直接动态开点+权值线段树合并,并查集维护所在联通块的根。注意,merge(x,y)不一定一直返回x,当x为空的时候会返回y。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 401000
const int inf=1000000000;
inline void read(int &x)
{
    x=0; char ch=getchar(); int f=1;
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); x*=f;
}
int n,m,tot,rt[M],fa[M];
int find(int x){return (x==fa[x])?x:(fa[x]=find(fa[x]));}
struct seg
{
    int siz,ls,rs;
    double sl;
    bool lz;
}s[M*17];
inline void clear(int x)
{
    if(!x) return ;
    s[x].siz=0; s[x].sl=0; s[x].lz=1;
}
inline void pushdown(int x)
{
    if(s[x].lz) clear(s[x].ls),clear(s[x].rs),s[x].lz=0;
}
inline void pushup(int x)
{
    s[x].siz=s[s[x].ls].siz+s[s[x].rs].siz;
    s[x].sl=s[s[x].ls].sl+s[s[x].rs].sl;
}
int merge(int x,int y)
{
    if(!s[x].siz||!s[y].siz) return (s[x].siz)?x:y;
    pushdown(x); pushdown(y);
    s[x].siz+=s[y].siz; s[x].sl+=s[y].sl;
    s[x].ls=merge(s[x].ls,s[y].ls);
    s[x].rs=merge(s[x].rs,s[y].rs);
    return x;
}
void insert(int l,int r,int &root,int w,int z)
{
    if(!root) root=++tot; s[root].siz+=z; s[root].sl+=log(w)*z;
    if(l==r) return ; pushdown(root); int mid=(l+r)>>1;
    if(w<=mid) insert(l,mid,s[root].ls,w,z);
    else insert(mid+1,r,s[root].rs,w,z);
}
void fix(int l,int r,int root,int x,int y)
{
    if(!s[root].siz) return ;
    if(x<=l&&y>=r){
        s[root].siz=0; s[root].sl=0; s[root].lz=1;
        return ;
    }
    int mid=(l+r)>>1; pushdown(root);
    if(y<=mid) fix(l,mid,s[root].ls,x,y);
    else if(x>mid) fix(mid+1,r,s[root].rs,x,y);
    else fix(l,mid,s[root].ls,x,y),fix(mid+1,r,s[root].rs,x,y);
    pushup(root);
}
int query_w(int l,int r,int root,int x)
{
    if(l==r) return l;
    int tmp=s[s[root].ls].siz,mid=(l+r)>>1;
    if(x<=tmp) return query_w(l,mid,s[root].ls,x);
    return query_w(mid+1,r,s[root].rs,x-tmp);
}
int main()
{
    read(m); int sw,x,y,z;
    while(m--)
    {
        read(sw);
        switch(sw)
        {
            case 1:
            {
                read(x); ++n; fa[n]=n;
                insert(0,inf,rt[n],x,1); break;
            }
            case 2:
            {
                read(x); read(y); x=find(x); y=find(y);
                if(x==y) break;
                merge(rt[x],rt[y]); fa[y]=x;
                break;
            }
            case 3:
            {
                read(x); x=find(x); read(y);
                z=s[rt[x]].siz; fix(0,inf,rt[x],0,y); z-=s[rt[x]].siz;
                insert(0,inf,rt[x],y,z);
                break;
            }
            case 4:
            {
                read(x); x=find(x); read(y);
                z=s[rt[x]].siz; fix(0,inf,rt[x],y,inf); z-=s[rt[x]].siz;
                insert(0,inf,rt[x],y,z);
                break;
            }
            case 5:
            {
                read(x); x=find(x); read(y);
                printf("%d\n",query_w(0,inf,rt[x],y));
                break;
            }
            case 6:
            {
                read(x); read(y); x=find(x); y=find(y);
                if(s[rt[x]].sl>s[rt[y]].sl) puts("1");
                else puts("0");
                break;
            }
            case 7:
            {
                read(x); x=find(x); printf("%d\n",s[rt[x]].siz);
                break;
            }
            default : break;
        }
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注