bzoj 1483: [HNOI2009]梦幻布丁线段树合并-白红宇

bzoj 1483: [HNOI2009]梦幻布丁线段树合并

阅读量：303 次

发布时间：2019-03-03

本文共 1665 字，大约阅读时间需要 5 分钟。

题意很简单，但是没有数据范围，这就是这题最难的地方

考虑线段树合并。。

就是随便搞搞

相信大家都会。。

就是这个数据范围很坑爹。。。

经过我无限WA和RE

我得出了以下结论：

1.数字可以很大

2.n不超过10W

3.询问非常非常多，比10W不知道高到哪里去了

通过结论1和2，我们知道可以用离散化

然后由由于性质3，上面一句作废，因为我开了100W的数组都没装下这个东西。。~~也可能是我的姿势不对~~

或许有的读者会说，那我可以只对一开始的离散化啊！！！

那么你后面怎么办，会有问题的，我打过了。。

那么我们考虑使用map，于是就A了

这个辣鸡数据范围，害我搞了这么久

#include
   
    #include
    
     #include
     #include
      
       #include
       
        using namespace std;const int N=100005;int n,m;struct qq{    int c,s1,s2;     bool L,R;}s[N*20];int num=0;map
        
          root;void change (int &now,int l,int r,int x){ if (now==0) now=++num; if (l==r) {s[now].L=s[now].R=true;s[now].c=1;return ;} int mid=(l+r)>>1; if (x<=mid) change(s[now].s1,l,mid,x); else change(s[now].s2,mid+1,r,x); s[now].c=s[s[now].s1].c+s[s[now].s2].c; s[now].L=s[s[now].s1].L;s[now].R=s[s[now].s2].R; if (s[s[now].s1].R&&s[s[now].s2].L) s[now].c--;}int ans=0;void Merge (int &x,int &y)//吧x的全部东西送给y { if (x==0) return ; if (y==0) {y=x;x=0;return ;} Merge(s[x].s1,s[y].s1); Merge(s[x].s2,s[y].s2); s[y].c=s[s[y].s1].c+s[s[y].s2].c; s[y].L=s[s[y].s1].L;s[y].R=s[s[y].s2].R; if (s[s[y].s1].R&&s[s[y].s2].L) s[y].c--; x=0;}int shen[N],cnt;int main(){ s[0].c=0; s[0].L=s[0].R=false; scanf("%d%d",&n,&m); for (int u=1;u<=n;u++) { int x; scanf("%d",&x); shen[u]=x; change(root[x],1,n,u); } sort(shen+1,shen+1+n); cnt=1;ans=s[root[shen[1]]].c; for (int u=2;u<=n;u++) if (shen[u]!=shen[cnt]) { shen[++cnt]=shen[u]; ans=ans+s[root[shen[u]]].c; } for (int u=1;u<=m;u++) { int x; scanf("%d",&x); if (x==2) printf("%d\n",ans); else { int a,b; scanf("%d%d",&a,&b); if (a==b) continue; ans=ans-s[root[a]].c-s[root[b]].c; Merge(root[a],root[b]); ans=ans+s[root[b]].c; } } return 0;}