BZOJ 3731 Gty的超级妹子树

VictorWonder posted @ 2014年12月21日 10:03 in BZOJ with tags 解题报告 Treap 树套树 树上查询 块状树 , 1032 阅读
明天就要月考了,总感觉现在这个时候还在做题不太好……呃,不过既然都已经开始做这题了,如果不AC了它的话,估计我也没有心情去月考了(好吧,我承认这一段是在胡扯233)
 
下面是正题:
这道题目的做法是块状树套上平衡树,我打的是Treap,感觉还是Treap好打一些,而且为了速度,我作死地打了指针+结构体,调试的时候真的是欲仙欲死。
首先,我们需要将整棵树分成好几个部分,至于怎么分块我就不说了,毕竟网上都应该能够搜到。分块之后,我们就将整棵树(我们定义其为1号树)变成了一棵很小的树,每一个结点都是一个块,我们定义这棵树为2号树。
0.查询
    查询的是一棵子树,首先,我们找到查询的结点u,接着,对u所属的那个块中的属于u子树的结点都查询一遍,判断其权值是不是严格大于x。其次,在2号树对1号树中u的子节点所属的块进行查询,因为每一个块都套上了Treap,查询的话还是挺方便的。具体的可以参照下图:
1.修改
    把点u的权值改成x,其实等于是在u所属块套上的Treap中,将u这个结点删去,改掉权值之后再将u插入回去,这里有一个坑点,我的Treap是根据每一块的根来算的,也就是说,有a1,a2..ak个结点都位于Treap[a1]中,那么将a1从Treap[a1]中删去之后再插入进去,最后得到的是一棵只有一个结点的Treap。
2.插入
    插入一个新结点要分类讨论,如果这个结点的父亲节点所属的块的大小还没有饱和,那么新插入的结点也属于这个块,否则,新插入的结点就是一个新的块,不要忘记将新的块所构成的新结点插入到2号树中。
3.删除
    删除操作也是一个麻烦事,我们假设u属于块pos[u]。如果pos[u]==u那么就在2号树中将这个结点和它的父亲结点断开就行了,否则,我们需要将u的所有子节点中属于pos[u]的点都从Treap[pos[u]]中删去然后再插入到新的Treap[pos[u]=u]中。其次,在2号树中,对于那些u子树所构成的块结点,需要将其和pos[u]断开连接,再重新和pos[u]=u连接。
 
大致就是这个样子,本来这个程序昨天中午就打好了的,调了大概一两个小时,直到后来,极限数据出错概率也只有5%~10%了,那才是最痛苦的时候,小数据大概对拍了半个多小时才拍出了一组数据将我的程序卡掉,结果扔到BZOJ上还是超时了,也不知道在哪里出了问题,直到不久前才发现,原来是对于块的size定义出了问题,为了调试方便,我把每块的大小都定义为了4 TAT。改成了400后就AC了,时间是五秒多,后来一直扩大这个数值,直到每块的size都在6000左右的时候,速度被我提到了1.75秒,感觉再进步就比较麻烦了。
另外,感觉这道题目的这种做法还是有点问题的,我发现如果是菊花图的话,似乎可以卡掉分块做法……不过我也懒得管这么多了,还是乖乖滚去复习月考吧……
 
Updata:BZOJ 3720 Gty的妹子树 和这道题目同一个出题人,操作比这题少了一个(断裂操作),其他都一样,所以你们都懂得。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const int N=500010;
const int M=100010;
const int Q=200010;
const int size=6000;
struct Treap* null;
struct Treap{
    Treap *fa,*son[2];
    int key,data,sz;
    void newnode(int x) {
        data=x; key=rand(); sz=1;
        fa=son[0]=son[1]=null;
    }
    void updata() { sz=son[0]->sz+son[1]->sz+1;}
    void rotate() {
        Treap *x=this,*y=x->fa,*z=y->fa;
        int w=(y->son[0]==x);
        if (z!=null) z->son[z->son[1]==y]=x;
        x->fa=y->fa; y->fa=x;
        if (x->son[w]!=null) x->son[w]->fa=y;
        y->son[w^1]=x->son[w]; x->son[w]=y; 
        y->updata(); x->updata();
    }
    void insert(Treap *&y) {
        Treap *x=this; x->sz++;
        if (y->data>x->data) {
            if (x->son[1]!=null) x->son[1]->insert(y);
            else x->son[1]=y,y->fa=x;
            if (x->son[1]->key<x->key) x->son[1]->rotate();
        } else {
            if (x->son[0]!=null) x->son[0]->insert(y);
            else x->son[0]=y,y->fa=x;
            if (x->son[0]->key<x->key) x->son[0]->rotate();
        } x->updata();
    }
    Treap* merge(Treap *fat,Treap *x,Treap *y) {
        if (x==null&&y==null) return null;
        if (x==null) {
            y->fa=fat;
            return y;
        }
        if (y==null) {
            x->fa=fat;
            return x;
        }
        if (x->key<y->key) {
            x->son[1]=merge(x,x->son[1],y);
            x->fa=fat; x->updata();
            return x;
        } else {
            y->son[0]=merge(y,x,y->son[0]);
            y->fa=fat; y->updata();
            return y;
        }
    }
    void clear() {
        if (this==null) return;
        else this->updata();
        if (this->fa!=null) this->fa->clear();
    }
    void del() {
        Treap *x=this,*y=merge(x->fa,x->son[0],x->son[1]);
        x->fa->son[x->fa->son[1]==x]=y;
        x->fa->clear(); x->sz=1;
        x->fa=x->son[0]=x->son[1]=null;
    }
    int ask(int y) {
        if (this==null) return 0;
        Treap *x=this; int ans=0;
        if (x->data>y) ans++;
        if (y>=x->data) ans+=x->son[1]->ask(y);
        else {
            ans+=x->son[1]->sz;
            ans+=x->son[0]->ask(y);
        } return ans;
    }
    Treap* findroot() {
        if (this->fa==null) return this;
        else return this->fa->findroot();
    }
};
Treap pool[Q];
Treap* v[Q];
Treap* total;
int n,m,w[Q],lastans;
int pos[Q],sz[Q],fa[Q];
int g[Q],to[N],nxt[N],tot;
int G[Q],TO[N],NXT[N],TOT;
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void addedge(int x,int y) {
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
    to[++tot]=x; nxt[tot]=g[y]; g[y]=tot;
}
void ADDEDGE(int x,int y) {
    TO[++TOT]=y; NXT[TOT]=G[x]; G[x]=TOT;
}
void init() {
    total=pool; null=total++;
    null->fa=null->son[0]=null->son[1]=null;
    null->key=null->data=null->sz=0;
}
void dfs(int x,int fat) {
    int cur=pos[x],k; fa[x]=fat;
    for (k=g[x];k;k=nxt[k]) if (to[k]!=fat) {
        if (sz[cur]+1<=size) {
            sz[pos[to[k]]=cur]++;
            Treap *t=v[cur]->findroot();
            t->insert(v[to[k]]);
        } else ADDEDGE(cur,pos[to[k]]);
        dfs(to[k],x);
    }
}
int query(int x,int y) {
    int k,ans=0; Treap *t;
    if (pos[x]==x) {
        t=v[x]->findroot();
        ans+=t->ask(y);
        for (k=G[x];k;k=NXT[k]) ans+=query(TO[k],y);
    } else {
        if (w[x]>y) ans++;
        for (k=g[x];k;k=nxt[k]) if (to[k]!=fa[x]&&fa[to[k]]==x) ans+=query(to[k],y);
    } return ans;
}
void change(int x,int y) {
    Treap *t; w[x]=y;
    t=v[x]->findroot();
    if (t==v[x]) {
        if (t->son[0]!=null) t=t->son[0];
        else if (t->son[1]!=null) t=t->son[1];
        else {
            v[x]->data=y;
            return;
        }
    }
    v[x]->del();
    t=t->findroot();
    v[x]->data=y;
    t->insert(v[x]);
}
void add(int fat,int x,int y) {
    v[x]=total++; fa[x]=fat;
    addedge(fat,x); w[x]=y;
    v[x]->newnode(y);
    if (sz[fat]+1<=size) {
        sz[pos[x]=pos[fat]]++;
        Treap *t=v[pos[fat]]->findroot();
        t->insert(v[x]);
    } else {
        sz[pos[x]=x]++;
        ADDEDGE(pos[fat],pos[x]);
    }
}
void delink(int X,int Y) {
    int K;
    if (TO[G[X]]==Y) G[X]=NXT[G[X]];
    else for (K=G[X];K;K=NXT[K]) {
        if (TO[NXT[K]]==Y) {
            NXT[K]=NXT[NXT[K]];
            return;
        }
    }
}
void cut(int x,int loc) {
    int k;
    if (pos[x]==x) delink(pos[fa[x]],x);
    else {
        v[x]->del(); sz[pos[x]]--;
        for (k=g[x];k;k=nxt[k]) {
            if (pos[to[k]]==pos[x]&&to[k]!=fa[x]&&fa[to[k]]==x) cut(to[k],loc);
            else if (to[k]!=fa[x]&&fa[to[k]]==x&&pos[to[k]]==to[k]) {
                delink(pos[loc],pos[to[k]]);
                ADDEDGE(loc,pos[to[k]]);
            }
        } sz[pos[x]=loc]++;
        if (pos[x]!=x) {
            Treap *t=v[loc]->findroot();
            t->insert(v[x]);
        }
    }
}
int main() {
    int i,x,y,k; init();
    for (read(n),i=1;i<n;i++) {
        read(x); read(y);
        addedge(x,y);
    }
    for (i=1;i<=n;i++) {
        read(w[i]); v[i]=total++;
        v[i]->newnode(w[i]);
        pos[i]=i;
    } dfs(1,0);
    for (read(m),i=1;i<=m;i++) {
        read(k); read(x); x^=lastans;
        if (k!=3) read(y),y^=lastans;
        if (k==0) printf("%d\n",lastans=query(x,y));
        else if (k==1) change(x,y);
        else if (k==2) add(x,++n,y);
        else if (k==3) if (fa[x]) cut(x,x),fa[x]=0;
    }
    return 0;
}
 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter