【BZOJ4399】魔法少女LJJ

2016.03.22 15:10 Tue | 67次阅读 | 旧日oi | 固定链接 | 源码

题解

线段树合并

认真看题……
c=1,新建一颗权值线段树,插入一个点
c=2,合并两颗权值线段树。
c=3,清空小于a的树,把信息都加到a上
c=4,清空大于a的树,把信息都加到a上
c=5,直接查就好了
c=6,转化为log维护sum就好了
c=7,并查集搞一下就行了。

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 400005
#define lim 1000000000
int m,c,tot,cnt;
int siz[N],fa[N],val[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int root[N];
double lg[N*20];
int ls[N*20],rs[N*20],sum[N*20];
void insert(int &x,int l,int r,int v,double e)
{
    sum[x=++tot]=1;lg[x]=e;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(v<=mid) insert(ls[x],l,mid,v,e);
    else insert(rs[x],mid+1,r,v,e); 
}
void merge(int &x,int y,int l,int r)
{
    if(!x||!y) {x=x+y;return;}
    if(l==r){sum[x]+=sum[y];lg[x]+=lg[y];return;}
    int mid=(l+r)>>1;
    merge(ls[x],ls[y],l,mid);
    merge(rs[x],rs[y],mid+1,r);
    sum[x]=sum[ls[x]]+sum[rs[x]];
    lg[x]=lg[ls[x]]+lg[rs[x]];
}
void update1(int &x,int l,int r,int a,int v)
{
    if(!x) x=++tot;
    if(l==r) 
    {
        sum[x]+=v;
        lg[x]+=v*log((double)l);
        return;
    }
    int mid=(l+r)>>1;
    if(mid<a) 
    {
        v+=sum[ls[x]],ls[x]=0;
        update1(rs[x],mid+1,r,a,v);
    }
    else update1(ls[x],l,mid,a,v);
    sum[x]=sum[ls[x]]+sum[rs[x]];
    lg[x]=lg[ls[x]]+lg[rs[x]];
}
void update2(int &x,int l,int r,int a,int v)
{
    if(!x) x=++tot;
    if(l==r) 
    {
        sum[x]+=v;
        lg[x]+=v*log((double)l);
        return;
    }
    int mid=(l+r)>>1;
    if(mid+1>a) 
    {
        v+=sum[rs[x]],rs[x]=0;
        update2(ls[x],l,mid,a,v);
    }
    else update2(rs[x],mid+1,r,a,v);
    sum[x]=sum[ls[x]]+sum[rs[x]];
    lg[x]=lg[ls[x]]+lg[rs[x]];
}
int get_kth(int x,int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(sum[ls[x]]>=k) return get_kth(ls[x],l,mid,k);
    else return get_kth(rs[x],mid+1,r,k-sum[ls[x]]);
}
int tim;
int main()
{
    int a,b,c;
    for(cin>>m;m--;)
    {
        scanf("%d",&c);
        if(c==1) 
        {
            scanf("%d",&val[++cnt]);
            fa[cnt]=cnt;siz[cnt]=1;
            insert(root[cnt],1,lim,val[cnt],log((double)val[cnt]));
        }
        else if(c==2)
        {
            scanf("%d%d",&a,&b);
            int p=find(a),q=find(b);
            if(p==q) continue;
            if(siz[p]>siz[q]) swap(p,q);
            merge(root[p],root[q],1,lim);
            fa[q]=p;siz[p]+=siz[q];
        }
        else if(c==3)
        {
            scanf("%d%d",&a,&b);
            update1(root[find(a)],1,lim,b,0);
        }
        else if(c==4)
        {
            scanf("%d%d",&a,&b);
            update2(root[find(a)],1,lim,b,0);
        }
        else if(c==5)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",get_kth(root[find(a)],1,lim,b));
        }
        else if(c==6)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",lg[root[find(a)]]>lg[root[find(b)]]?1:0);
        }
        else if(c==7)
        {
            scanf("%d",&a);
            printf("%d\n",siz[find(a)]);
        }
        else if(c==8) scanf("%d%d",&a,&b);
        else scanf("%d",&a);
    }
}
  • jcysndn 2016-04-08 15:20:23

    为啥开N*20的数组就行啊

  • jkxing 2016-04-09 20:42:33

    NlogN的空间啊

  • jkxing 2016-04-09 20:43:14

    NlogN的空间啊。