精华内容
下载资源
问答
  • 正在研究的是一个星系,这个星系中有n个星球,其中有一个主星球(方便起见我们默认其为1号星球),其余的所有星球均有且仅有一个依赖星球。主星球没有依赖星球。 我们定义依赖关系如下:若星球a的依赖星球是b,则有...

    题目描述

    物理学家小C的研究正遇到某个瓶颈。

    他正在研究的是一个星系,这个星系中有n个星球,其中有一个主星球(方便起见我们默认其为1号星球),其余的所有星球均有且仅有一个依赖星球。主星球没有依赖星球。

    我们定义依赖关系如下:若星球a的依赖星球是b,则有星球a依赖星球b.此外,依赖关系具有传递性,即若星球a依赖星球b,星球b依赖星球c,则有星球a依赖星球c.

    对于这个神秘的星系中,小C初步探究了它的性质,发现星球之间的依赖关系是无环的。并且从星球a出发只能直接到达它的依赖星球b.

    每个星球i都有一个能量系数wi.小C想进行若干次实验,第i次实验,他将从飞船上向星球di发射一个初始能量为0的能量收集器,能量收集器会从星球di开始前往主星球,并收集沿途每个星球的部分能量,收集能量的多少等于这个星球的能量系数。

    但是星系的构成并不是一成不变的,某些时刻,星系可能由于某些复杂的原因发生变化。

    有些时刻,某个星球能量激发,将使得所有依赖于它的星球以及他自己的能量系数均增加一个定值。还有可能在某些时刻,某个星球的依赖星球会发生变化,但变化后依然满足依赖关系是无环的。

    现在小C已经测定了时刻0时每个星球的能量系数,以及每个星球(除了主星球之外)的依赖星球。接下来的m个时刻,每个时刻都会发生一些事件。其中小C可能会进行若干次实验,对于他的每一次实验,请你告诉他这一次实验能量收集器的最终能量是多少。

    输入

    第一行一个整数n,表示星系的星球数。

    接下来n-1行每行一个整数,分别表示星球2-n的依赖星球编号。

    接下来一行n个整数,表示每个星球在时刻0时的初始能量系数wi.

    接下来一行一个整数m,表示事件的总数。

    事件分为以下三种类型。

    (1)"Q di"表示小C要开始一次实验,收集器的初始位置在星球di.

    (2)"C xi yi"表示星球xi的依赖星球变为了星球yi.

    (3)"F pi qi"表示星球pi能量激发,常数为qi.

    输出

    对于每一个事件类型为Q的事件,输出一行一个整数,表示此次实验的收集器最终能量。

    样例输入

    3
    1
    1
    4 5 7
    5
    Q 2
    F 1 3
    Q 2
    C 2 3
    Q 2

    样例输出

    9
    15
    25

    提示

    n<=100000,m<=300000,1<di,xi<=n,wi,qi<=100000.保证操作合法。注意w_i>=0

     

    如果没有迁移子树操作考虑怎么做?

    求出原树出栈入栈序(下文用dfs序代替),对于入栈点权值为正(即val[x]),对于出站点权值为负(即-val[x]),那么询问就是求询问点在dfs序上入栈点的前缀和(不在这个点到根路径上的点出栈点和入栈点一定同时在询问点的前边,正负权值抵消)。

    对于修改一定是dfs序上的一段区间,用线段树区间修改即可,因为每个点可能是正权可能是负权,因此还要维护区间正权点数与负权点数之差。

    那么现在有了子树迁移操作,dfs序是动态的了,显然线段树无法实现,那么用平衡树就好了。

    将操作点子树从treap中分裂出来然后插入到它新的父节点入栈点后面即可。

    但因为这道题我们只知道dfs序上每个点对应平衡树上节点的编号(建树时开两个数组分别存一下),所以要再维护出平衡树上每个点的父节点然后每次分裂前先从操作点往上找到根节点来得到这个点在平衡树上的具体位置(即它现在是dfs序的第几个点)再从根正常分裂。

    这道题严重卡常,建议用上所有优化,蒟蒻的我差点没卡过去QAQ。

    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long 
    using namespace std;
    char buf[100000],*p1,*p2;
    #define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
    __attribute__((optimize("-O3")))int rd() {
        register int x=0;register char ch=nc();
        while(ch<'0'||ch>'9') ch=nc();
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=nc();
        return x;
    }
    int n,m;
    int x,y;
    int tot;
    int cnt;
    int res;
    int root;
    int a,b,c;
    int head[200010];
    int to[200010];
    int next[200010];
    int num[200010];
    int sig[200010];
    ll sum[200010];
    int v[200010];
    int val[200010];
    int pos[200010];
    int size[200010];
    int ls[200010];
    int rs[200010];
    int f[200010];
    int r[200010];
    int s[200010];
    int t[200010];
    int p[200010];
    int q[200010];
    inline void add(int x,int y)
    {
        tot++;
        next[tot]=head[x];
        head[x]=tot;
        to[tot]=y;
    }
    inline int build(int val,int k)
    {
        int rt=++cnt;
        r[rt]=rand();
        size[rt]=1;
        v[rt]=val*k;
        sum[rt]=1ll*v[rt];
        sig[rt]=k;
        num[rt]=sig[rt];
        return rt;
    }
    inline void pushup(int rt)
    {
        size[rt]=size[ls[rt]]+size[rs[rt]]+1;
        num[rt]=sig[rt];
        sum[rt]=1ll*v[rt];
        if(ls[rt])
        {
            num[rt]+=num[ls[rt]];
            sum[rt]+=sum[ls[rt]];
        }
        if(rs[rt])
        {
            num[rt]+=num[rs[rt]];
            sum[rt]+=sum[rs[rt]];
        }
    }
    inline void pushdown(int rt)
    {
        if(pos[rt])
        {
            pos[ls[rt]]+=pos[rt];
            pos[rs[rt]]+=pos[rt];
            sum[ls[rt]]+=1ll*num[ls[rt]]*pos[rt];
            sum[rs[rt]]+=1ll*num[rs[rt]]*pos[rt];
            v[ls[rt]]+=sig[ls[rt]]*pos[rt];
            v[rs[rt]]+=sig[rs[rt]]*pos[rt];
            pos[rt]=0;
        }
    }
    inline int merge(int x,int y)
    {
        pushdown(x);
        pushdown(y);
        if(!x||!y)
        {
            return x+y;
        }
        if(r[x]<r[y])
        {
            rs[x]=merge(rs[x],y);
            if(rs[x])
            {
                f[rs[x]]=x;
            }
            pushup(x);
            return x;
        }
        else
        {
            ls[y]=merge(x,ls[y]);
            if(ls[y])
            {
                f[ls[y]]=y;
            }
            pushup(y);
            return y;
        }
    }
    inline void split(int rt,int &x,int &y,int k)
    {
        pushdown(rt);
        if(!rt)
        {
            x=y=0;
            return ;
        }
        if(size[ls[rt]]>=k)
        {
            y=rt;
            split(ls[rt],x,ls[y],k);
            if(ls[y])
            {
                f[ls[y]]=y;
            }
            pushup(rt);
        }
        else
        {
            x=rt;
            split(rs[rt],rs[x],y,k-size[ls[rt]]-1);
            if(rs[x])
            {
                f[rs[x]]=x;
            }
            pushup(rt);
        }
    }
    inline int get_size(int rt)
    {
        int ans=0;
        int flag=1;
        while(rt)
        {
            if(flag)
            {
                ans+=size[ls[rt]]+1;
            }
            flag=(rt==rs[f[rt]]);
            rt=f[rt];
        }
        return ans;
    }
    inline void dfs(int x)
    {
        s[x]=build(val[x],1);
        root=merge(root,s[x]);
        for(int i=head[x];i;i=next[i])
        {
            dfs(to[i]);
        }
        t[x]=build(val[x],-1);
        root=merge(root,t[x]);
    }
    int main()
    {
        srand(12378);
        n=rd();
        for(int i=2;i<=n;i++)
        {
            x=rd();
            add(x,i);
        }
        for(int i=1;i<=n;i++)
        {
            val[i]=rd();
        }
        dfs(1);
        m=rd();
        while(m--)
        {
            char op=nc();
            while(op!='C'&&op!='Q'&&op!='F')op=nc();
            int x=rd();
            if(op=='Q')
            {
                res=get_size(s[x]);
                split(root,a,b,res);
                f[a]=f[b]=0;
                printf("%lld\n",sum[a]);
                root=merge(a,b);
            }
            else if(op=='F')
            {
                y=rd();
                res=get_size(t[x]);
                split(root,b,c,res);
                f[b]=f[c]=0;
                res=get_size(s[x]);
                split(b,a,b,res-1);
                f[a]=f[b]=0;
                pos[b]+=y;
                sum[b]+=1ll*num[b]*y;
                v[b]+=sig[b]*y;
                root=merge(merge(a,b),c);
            }
            else
            {
                y=rd();
                res=get_size(t[x]);
                split(root,b,c,res);
                f[b]=f[c]=0;
                res=get_size(s[x]);
                split(b,a,b,res-1);
                f[a]=f[b]=0;
                root=merge(a,c);
                res=get_size(s[y]);
                split(root,a,c,res);
                f[a]=f[c]=0;
                root=merge(merge(a,b),c);
            }
        }
    }

    转载于:https://www.cnblogs.com/Khada-Jhin/p/10028644.html

    展开全文
  • 某一天gty在与的妹子玩游戏。妹子提出一个游戏,给定一棵有根树,每个节点有一些石子,每次可以将不多于L的石子移动到父节点,询问将某个节点的子树中的石子移动到这个节点先手是否有必胜策略。gty很快计算出了...

    题目描述

    某一天gty在与他的妹子玩游戏。
    妹子提出一个游戏,给定一棵有根树,每个节点有一些石子,每次可以将不多于L的石子移动到父节点,询问
    将某个节点的子树中的石子移动到这个节点先手是否有必胜策略。
    gty很快计算出了策略。
    但gty的妹子十分机智,她决定修改某个节点的石子或加入某个新节点。
    gty不忍心打击妹子,所以他将这个问题交给了你。
    另外由于gty十分绅士,所以他将先手让给了妹子。

    输入

    第一行两个数字,n和L,n<=5*10^4,L<=10^9
    第二行n个数字,表示每个节点初始石子数。
    接下来n-1行,每行两个整数u和v,表示有一条从u到v的边。
    接下来一行一个数m,表示m组操作。
    接下来m行,每行第一个数字表示操作类型
    若为1,后跟一个数字v,表示询问在v的子树中做游戏先手是否必胜。
    若为2,后跟两个数字x,y表示将节点x的石子数修改为y。
    若为3,后跟三个数字u,v,x,表示为u节点添加一个儿子v,初始石子数为x。
    在任意时刻,节点数不超过5*10^4。

    输出

    对于每个询问,若先手必胜,输出"MeiZ",否则输出"GTY"。
    另,数据进行了强制在线处理,对于m组操作,除了类型名以外,都需要异或之前回答为"MeiZ"的个数。

    样例输入

    2 1000
    0 0
    1 2
    1
    1 1

    样例输出

    GTY
     
    对于每个询问就是在子树中做阶梯巴什博弈。
    判断谁能赢只要求出与子树根节点深度奇偶性不同的所有子树内点的SG值的异或和就行了。
    巴什博弈的SG值就是石子数%(L+1)。
    如果没有加点操作直接在线段树上维护dfs序就行了,但有了加点操作就要动态维护dfs序。
    每次加一个点直接将这个点插入到它父亲dfs序位置的后面即可,同时记录每个点对应的平衡树上点的编号。
    如果是用splay写那么直接可以通过父节点在splay上点的编号进行操作。
    但用非旋转treap的话你发现因为dfs是动态的,所以无法知道加入点父节点在treap中对应编号点具体的位置,也就无法从根往下找到这个点。
    这时就要记录每个点在treap上父节点是谁然后从操作点自下而上反向分裂(详细做法参见平衡树讲解)。
    同样因为dfs序动态的,我们也不知道一个点的子树在dfs上的区间到哪截止,这里有一个判断方法:
    从子树根节点在dfs序上位置往右第一个深度小于等于它的点之前都是它子树中的点。
    因此在treap上还要维护区间在原树上深度最小值,加上之前维护的奇数偶数层SG值异或和共三个区间信息。
    注意因为treap上要维护父节点是谁,因此在split和merge时都要更新父亲数组。
    #include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<vector>
    #include<bitset>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,L,m;
    int ls[100010];
    int rs[100010];
    int sum[100010];
    int num[100010];
    int mn[100010];
    int val[100010];
    int v[100010];
    int r[100010];
    int d[100010];
    int dep[100010];
    int s[100010];
    int f[100010];
    int head[100010];
    int to[200010];
    int next[200010];
    int tot;
    int cnt;
    int opt;
    int ans;
    int x,y,z;
    int a,b,c;
    int root;
    void add(int x,int y)
    {
        tot++;
        next[tot]=head[x];
        head[x]=tot;
        to[tot]=y;
    }
    int build(int val,int dep)
    {
        int rt=++cnt;
        v[rt]=val;
        r[rt]=rand();
        ls[rt]=rs[rt]=0;
        d[rt]=dep;
        mn[rt]=d[rt];
        if(d[rt]%2==0)
        {
            num[rt]=v[rt];
        }
        sum[rt]=v[rt];
        return rt;
    }
    void pushup(int rt)
    {
        sum[rt]=sum[ls[rt]]^sum[rs[rt]]^v[rt];
        num[rt]=num[ls[rt]]^num[rs[rt]];
        if(d[rt]%2==0)
        {
            num[rt]^=v[rt];
        }
        mn[rt]=d[rt];
        if(ls[rt])
        {
            mn[rt]=min(mn[rt],mn[ls[rt]]);
        }
        if(rs[rt])
        {
            mn[rt]=min(mn[rt],mn[rs[rt]]);
        }
    }
    int merge(int x,int y)
    {
        if(!x||!y)
        {
            return x+y;
        }
        if(r[x]<r[y])
        {
            rs[x]=merge(rs[x],y);
            f[rs[x]]=x;
            if(!rs[x])
            {
                f[0]=0;
            }
            pushup(x);
            return x;
        }
        else
        {
            ls[y]=merge(x,ls[y]);
            f[ls[y]]=y;
            if(!ls[y])
            {
                f[0]=0;
            }
            pushup(y);
            return y;
        }
    }
    void dfs(int x,int fa)
    {
        dep[x]=dep[fa]+1;
        s[x]=build(val[x],dep[x]);
        root=merge(root,s[x]);
        for(int i=head[x];i;i=next[i])
        {
            if(to[i]!=fa)
            {
                dfs(to[i],x);
            }
        }
    }
    void split1(int rt,int &a,int &b)
    {
        int x=ls[rt];
        int y=rs[rt];
        ls[rt]=rs[rt]=0;
        num[rt]=sum[rt]=0;
        sum[rt]=v[rt];
        mn[rt]=d[rt];
        if(d[rt]%2==0)
        {
            num[rt]=v[rt];
        }
        while(f[rt])
        {
            if(ls[f[rt]]==rt) 
            {
                ls[f[rt]]=y;
                f[y]=f[rt];
                y=f[rt];
                pushup(f[rt]);
            }
            else
            {
                rs[f[rt]]=x;
                f[x]=f[rt];
                x=f[rt];
                pushup(f[rt]);
            }
            rt=f[rt];
        }
        a=x;
        b=y;
    }
    void split2(int rt,int &x,int &y,int k)
    {
        if(!rt)
        {
            x=y=0;
            return ;
        }
        if(mn[ls[rt]]<=k)
        {
            y=rt;
            split2(ls[rt],x,ls[y],k);
            f[ls[y]]=y;
            pushup(rt);
        }
        else if(d[rt]<=k)
        {
            x=ls[rt];
            y=rt;
            ls[rt]=0;
            pushup(rt);
            return ;
        }
        else
        {
            x=rt;
            split2(rs[rt],rs[x],y,k);
            f[rs[x]]=x;
            pushup(rt);
        }
    }
    int main()
    {
        scanf("%d%d",&n,&L);
        L++;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&z);
            val[i]=z%L;
        }
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        dfs(1,0);
        mn[0]=n+1;
        scanf("%d",&m);
        while(m--)
        {
            a=b=c=0;
            scanf("%d",&opt);
            if(opt==1)
            {
                scanf("%d",&x);
                x^=ans;
                split1(s[x],a,b);
                split2(b,b,c,dep[x]);
                b=merge(s[x],b);
                if(dep[x]&1)
                {
                    if(num[b]==0)
                    {
                        printf("GTY\n");
                    }
                    else
                    {
                        ans++;
                        printf("MeiZ\n");
                    }
                }
                else
                {
                    if((num[b]^sum[b])==0)
                    {
                        printf("GTY\n");
                    }
                    else
                    {
                        ans++;
                        printf("MeiZ\n");
                    }
                }
                root=merge(merge(a,b),c);
            }
            else if(opt==2)
            {
                scanf("%d%d",&x,&z);
                x^=ans;
                z^=ans;
                split1(s[x],a,b);
                v[s[x]]=z%L;
                sum[s[x]]=z%L;
                num[s[x]]=0;
                if(d[s[x]]%2==0)
                {
                    num[s[x]]=z%L;
                }
                b=merge(s[x],b);
                root=merge(a,b);
            }
            else
            {
                scanf("%d%d%d",&x,&y,&z);
                x^=ans;
                y^=ans;
                z^=ans;
                dep[y]=dep[x]+1;
                s[y]=build(z%L,dep[y]);
                split1(s[x],a,b);
                a=merge(a,s[x]);
                a=merge(a,s[y]);
                root=merge(a,b);
            }
        }
    }

    转载于:https://www.cnblogs.com/Khada-Jhin/p/9971174.html

    展开全文
  • 动态维护凸包

    千次阅读 2012-02-03 21:07:08
    利用granham思想,维护凸包,水平序要维护两个凸壳,比较麻烦,所以用极角序,每次查入用平衡树维护极角离最近的点,此时到双向链表上开始模拟granham双向删点,直到无法删为止,因为每个点至多删一次,所以是...

    依次插入n个点,询问凸包面积。

    利用granham思想,维护凸包,水平序要维护两个凸壳,比较麻烦,所以用极角序,每次查入用平衡树维护极角离他最近的点,此时到双向链表上开始模拟granham双向删点,直到无法删为止,因为每个点至多删一次,所以是nlogn的复杂度。面积维护用叉积即时维护即可。

    依次插入n个半平面,询问半平面交面积。

    与上题类似,维护法向量的极角,双向删半平面(当相邻一半平面两交点均在此半平面外即删),实现更复杂,我还没实现。

    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <ctime>
    const int maxn=100005,oo=1073741819;
    struct point
    {
        long long x,y;
        double t,d;
    }a[maxn],o;
    int n,rt[maxn],r[maxn],l[maxn],id[maxn],ins[maxn],net[maxn];
    long long sum,s[maxn],ans;
    void left(int x)
    {
        long long y=rt[x],z=rt[y];
        r[y]=l[x],rt[l[x]]=y;
        l[x]=y,rt[y]=x;
        if (r[z]==y) r[z]=x;else l[z]=x;rt[x]=z;
    }
    void right(int x)
    {
        long long y=rt[x],z=rt[y];
        l[y]=r[x],rt[r[x]]=y;
        r[x]=y,rt[y]=x;
        if (r[z]==y) r[z]=x;else l[z]=x;rt[x]=z;
    }
    int cmp(int x,int k)
    {
        if ((a[k].t>a[x].t)||((a[k].t==a[x].t)&&(a[k].d>a[x].d))) return -1;
        else if ((a[k].t<a[x].t)||((a[k].t==a[x].t)&&(a[k].d<a[x].d))) return 1;
        return 0;
    }
    long long cross(point e,point r)
    {
        return ((e.x*r.y)-(e.y*r.x));
    }
    long long cr(int i,int j,int k)
    {
        point e;e.x=a[j].x-a[i].x,e.y=a[j].y-a[i].y;
        point r;r.x=a[k].x-a[i].x,r.y=a[k].y-a[i].y;
        return cross(e,r);
    }
    long long dist(point e,point r)
    {
        long long x=e.x-r.x,y=e.y-r.y;
        return (x*x+y*y);
    }
    int ori(int k,int root)
    {
        id[k]=rand(),rt[k]=root;return k;
    }
    void inser(int k)
    {
        int x=0;
        for (;;)
        {
            if (cmp(x,k)==-1)
                if (r[x]!=0) x=r[x];else {r[x]=ori(k,x),x=r[x];break;}
            else if (cmp(x,k)==1)
                if (l[x]!=0) x=l[x];else {l[x]=ori(k,x),x=l[x];break;}
            else return ;
        }   
        for (;id[rt[x]]>id[x];)
            if (l[rt[x]]==x) right(x);else left(x);
    }
    void cancel(int k)
    {
        net[ins[k]]=net[k],ins[net[k]]=ins[k];
        sum=sum-s[ins[k]]-s[k];
        s[ins[k]]=cross(a[ins[k]],a[net[k]]),sum=sum+s[ins[k]];
        for (;(l[k])&&(r[k]);)  if (id[l[k]]<id[r[k]])  right(l[k]);else left(r[k]);
        int j=(l[k]==0) ? r[k] : l[k];
        if (l[rt[k]]==k) l[rt[k]]=j;else r[rt[k]]=j;rt[j]=rt[k];
    }
    int find(int k)
    {
        int ll=0,x=r[0],pd;
        for (;x;)
        {
         pd=cmp(x,k);   
         if (pd==-1) ll=(cmp(ll,x)==-1) ? x : ll,x=r[x];
          else if (pd==1) x=l[x];
          else return x;
        }
        return ll;
    }
    void enter(int k)
    {
        a[k].t=atan2(a[k].y-o.y,a[k].x-o.x)*10000,a[k].d=dist(a[k],o);
        int i=find(k),j=net[i],flag=0;
        if (0==i) {for (;r[i]!=0;i=r[i]) ;j=net[i];}
        if (cmp(i,k)==0) return ;
        for (;(cr(ins[i],i,k)<=0);cancel(i),i=ins[i],flag=1) ;
        if ((1==flag)||(cr(i,k,j)>0))
        {
            net[k]=net[i],ins[k]=i,ins[net[k]]=k,net[i]=k,inser(k);
            sum=sum-s[i],s[i]=cross(a[i],a[k]),s[k]=cross(a[k],a[j]);
            sum=sum+s[i]+s[k];   
            for (i=net[j];(cr(k,j,i)<=0);cancel(j),j=i,i=net[i]) ;
        }
    }
    void origin()
    {
        int i,j;
        point c;
        id[0]=-oo,a[0].t=-oo;
        for (i=1;i<=3;i++) a[i].t=atan2(a[i].y-o.y,a[i].x-o.x)*10000,a[i].d=dist(a[i],o);
        for (i=1;i<=2;i++)
            for (j=i+1;j<=3;j++)
                if (cmp(i,j)==1) c=a[i],a[i]=a[j],a[j]=c;
        net[1]=2,net[2]=3,net[3]=1;
        ins[1]=3,ins[2]=1,ins[3]=2;
        s[1]=cross(a[1],a[2]),s[2]=cross(a[2],a[3]),s[3]=cross(a[3],a[1]);
        sum=s[1]+s[2]+s[3];
        inser(1);inser(2);inser(3);
    }
    void init()
    {
        int i,j,t,k;
        for (i=1;i<=3;o.x+=a[i].x,o.y+=a[i].y,i++) scanf("%d%d",&a[i].x,&a[i].y),a[i].x*=3,a[i].y*=3;
        o.x/=3,o.y/=3;
        origin();
        sum=cross(a[1],a[2])+cross(a[2],a[3])+cross(a[3],a[1]);
        scanf("%d\n",&n);
        for (i=4;i<=n+3;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y),a[i].x*=3,a[i].y*=3;
            enter(i);
            if (sum<0) ans=-sum/9;else ans=sum/9;
            printf("%I64d\n",ans); 
        }
    }
    int main()
    {
        freopen("Convex.in","r",stdin);
        freopen("Convex.out","w",stdout);
            srand((int)time(NULL));
            init();
        return 0;
    }
    


    展开全文
  • 在C++中对象可以静态分配——即编译器在处理程序源代码时分配,也可以动态分配——即程序执行时调用运行时刻库函数来分配。这两种内存分配方法的主要区别是效率与灵活性之间的平衡准则不同。出于静态内存分配是在...

    在C++中对象可以静态分配——即编译器在处理程序源代码时分配,也可以动态分配——即程序执行时调用运行时刻库函数来分配。这两种内存分配方法的主要区别是效率与灵活性之间的平衡准则不同。出于静态内存分配是在程序执行之前进行的,因而效率比较高。但是,他缺少灵活性,他要求在程序执行之前就直到所需内存的类型和数量。例如,利用静态分配的字符串数组,我们无法很容易的处理和存储任意的文本文件。一般来说,存储未知数目的元素需要动态内存分配的灵活性。

    以下内存分配为静态的,例如:int ival = 1024;    指示编译器分配足够的存储区以存放一个整型值,该存储区与名字 ival 相关联。然后用数值1024初始化该存储区。这些工作都是在程序执行之前完成的。

    有两个值与对象 ival 相关联:一个是它包含的值——本例中是1024,另一个是存放这个值的存储区的地址。在C++中,这两个值都可以被访问。当我们写代码: int ival2 = ival + 1;时,我们访问 ival 所包含的值,并把它加 1 ,然后再用该新值初始化 ival2 。在本例中,ival2的值是1025,怎样访问他的地址呢?

    C++支持用指针类型来存放对象的内存地址值。        例如,为了声明一个能存放 ival 内存地址的指针类型。  我们可以写成: int *pint; C++预定义了一个专门取地址的操作符(&)。当我们把他应用在一对象时,返回的是对像的地址值。因此,为了将 ival的内存地址值赋给 pint ,我们可以写成:int *pint; pint = &ival;   为了访问 pint 所指向的实际对象,我们必须先用解引用操作符(*)来接触 pint 的引用。例如,我们通过 pint 间接给 ival 加1:*pint = *pint +1 ; 它等价于对 ival 操作的语句:ival = ival + 1;

    在C++中,指针的主要用处是管理和操纵动态分配的内存。静态与动态内存分配的两个主要区别是:

    1. 静态对象是有名字的变量,我们直接对其进行操作。而动态对象是没有名字的变量,我们通过指针间接的对它进行操作。
    2. 静态对象的分配与释放由编译器自动处理,程序员需要理解这一点,但不需要做任何事情。相反,动态对象的分配与释放,必须由程序员显式的管理,相对来说比较容易出错,他通过 new 和 delete 两个表达式来完成。

    对象的动态分配可通过 new 表达式的两个版本之一来完成。第一个版本用于分配特定类型的单个对象,例如:  int *pint = new int(10); 分配了一个没有名字的int 类型的对象,对象初始值为 1024 。然后表达式返回对象在内存中的地址。接着这个地址被用来初始化指针对象 pint。对于动态分配的内存,唯一的访问是通过指针间接访问。

    new 表达式的第二个版本,用于分配特定类型和维数的数组。例如: int *pia = new int [4]; 分配了含有四个元素的整型数组。我们不可以给动态分配的数组的每个元素显式地指定一个初始值。

    分配动态数组时一个常令人迷惑的问题是,返回值只是一个指针,与分配动态单一动态对象的返回类型相同,例如,pint 与 pia的不同之处在于,pia 拥有四元素数组第一个元素的地址,而 pint 只是简单的包含了一个单一对象的地址。当用完了动态分配的对象或对象数组后,我们必须显式地释放这些内存。我们可以通过 delete 表达式的两个版本之一来完成这件事情,而释放之后的内存则可以被程序重新使用。单一对象的 delete 表达式形式:delete pint; 数组形式的delete 表达式:delete [] pia;

    如果忘了释放动态分配的内存,又会怎么样呢?答案就是,程序会出现内存泄漏(memory leak)的问题。内存泄漏是指一块动态分配的内存,我们不再拥有指向这块内存的指针,因此我们没有办法将它返还给程序供以后使用。

                                   

     

    展开全文
  • 动态索引-【B树】

    2018-08-10 20:42:00
    BST大家都了解是二叉搜索树的意思,但是二叉树并非都是平衡的,严重失衡的情况下还有可能演化成线性表,从而降低了检索效率。要知道添加索引的主要原因是为了查询速度快,所以其平衡性是非常重要的。 如何保证多...
  • 2019-8-5动态规划

    2019-08-05 19:10:56
    T1:矩阵二 ​ 题目:给定一个1*(2n)的矩阵(usqwedf:这不是一个2n的...​ 这道题应该算是乱入的题吧,说是dp,然而就是个递推。首先,我们可以非常快速的写一个暴力算法,然后你观察这个算法的前几位答案,你会...
  • 先说下动态凸包怎么写吧,搞棵平衡树存上下凸壳然后每次插入一个点就往左右维护看是否满足凸性否则就弹出,就是这么简单 这道题就是删点然后询问凸壳,那么离线反着做就行了 出题人还是挺良心的直接让你维护上凸...
  • 这道题目是说现在有一个神奇的天平,你的目的是要令他平衡。天平两边长度均为15,每边最多有20个挂钩,一共提供最多20个砝码,要求计算当所有砝码都挂上的时候,能使天平平衡的悬挂方式一共有多少种呢。 算法...
  • poj1837:大意,给定天平的位置和砝码,找到所放的位置能够使天平... poj1260:用dp[i]来表示处理第i个珍珠,因为对于第i个品质的珍珠,要么自己买,要么前面的珍珠和一起湊过来买。所以状态转移方程为:dp[i] = mi
  • 将树状数组中每一个节点看成一棵平衡树,支持$RANK$操作,每次删除一个数之前,支持查询位置在当前数之前权值比大的有多少个,查询位置在当前数之后权值比小的有多少个,再支持删除操作。 复杂度${O(nlogn^{...
  • 替罪羊树呢就是不用旋转的平衡树,那不旋转如何维持平衡呢?我们设定一个α\alpha值,每当一个点不满足大小平衡时我们就暴力重构那一部分...删除还有回收的时候记得传引用,因为你还要断掉父亲和的边。重构的时候只
  • 采用CLJ在重量平衡树和后缀平衡树在信息学奥赛中的应用中提到的标号思想 不妨令每个节点表示一个区间 用区间的中值代表这个数的大小 具体实现是我们不仅要给每个点记录 l,r,mid 还要记录 x y 表示等价于(x,y)的...
  • 看到这种题,绝对的平衡树乱搞 但我需要练习链表啊 昨天偷懒贴了ldx的读优,结果又没有加负数,气…… 分析 将A数组排序后,建立链表 那么Ai在链表中的pre和nxt就分别对应其前驱和后继 从后往前查,查完后就删除...
  • 没事闲的学学平衡树吧,打代码炒鸡爽的(特别是机械键盘)(无视)。...这样一棵树有啥用呢——就是可以维护一个有序的东西,可以动态插入,删除,查询第k大,查询前驱后继(就是有序序列中跟挨着的
  • 各种大V推荐的股债平衡策略真实效果如何,是否是股市灵丹妙药,能带我们... 最简单的方案就是固定股债比例比如5:5,然后定期动态平衡比如半年或一年。升级方案可以根据市场走势动态调整股债比例,例如熊市加大股票...
  • 查找算法之平衡查找树

    千次阅读 2018-06-16 00:27:56
    但是,在动态插入中保证树的完美平衡的代价太高了。 2-3查找树 我们将一棵标准的二叉查找树中的节点成为2-节点(含有一个键和两条链接),现在我们引入3-节点,它含有两个键和三条链接。 查找 要判断一个键...
  • 查找 代码基本没有,主要是定义,计算...1:分为静态查找表和动态查找表,区别,动态查找表插入不存在的数据元素or删除已存在的数据元素 2:其关键字和给定值进行过比较的记录个数的平均值,的期望为ASL=∑Pi*Ci ...
  • 平衡二叉树-红黑树

    2019-02-06 19:53:01
    如果数组按照有序顺序插入二叉树,那么...由于数据是动态的插入,因此我们不能在最开始获得全部数据,所以就不能用打乱数据的方式来解决这个问题,由此衍生出了红黑树,能保证插入删除查找的概率稳定在O(logN)。 ...
  • 平衡二叉树为了保证其平衡性,需要在插入或删除节点时动态地调整树节点,使其一直保持平衡。在网上查到一篇文献《平衡二叉树(AVL树)》。该文作者用python实现了平衡二叉树的基本操作。唯一有点遗憾的是的输出...
  • 提及将行动社会学与冲突理论联系起来的TOURAINE方法,可以促使行为者以明确的要求动态地在冲突与合作之间摇摆策略:如果法律事务很容易成为媒体事件,则相反,即影响面对的社会职业群体的规范,法官几乎不承认...
  • 这几天,Alice又沉浸在逆序对的快乐当中,已近学会了如何求逆序对对数,动态维护逆序对对数等等题目,认为把这些题让你做简直是太没追求了,于是,经过一天的思考和完善,Alice终于拿出了一道认为差不...
  • 某个数的前缀—>先查一下是区间第几大,再求-1大 某个数的后缀—>和上面那个有区别吗???现在有了区间修改操作 多搞一个树状数组 套在一起就好啦 暴力开点开不下的 要动态开点#include #include<cstdi
  • 动态平衡就比较复杂,但了解的基本的属性时也很容易理解,动态平衡的属性:速度,惯性,运动方向,重心,支撑点,但人物悬空的时候是没有支撑点的,但此时重心就尤为重要,你要知道为什么直升机的尾巴要多一个"风扇"......

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 131
精华内容 52
关键字:

他动动态平衡