2022年11月23日
0 收藏 460 点赞 2,945 浏览 3612 个字

access(x)：访问x节点

perferred child：若以x为根的子树中最后被访问的节点在以x的儿子y为根的子树中，则称y为节点x的preferred child

preferred edge：节点x与其preferred child之间的边

preferred path：由preferred edge组成的路径

bzoj2002弹飞绵羊

`#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;const int Mx=;int n,m,fa[Mx],l[Mx],r[Mx],root[Mx],siz[Mx],rev[Mx];void pushup(int x) { siz[x]=siz[l[x]]+siz[r[x]]+; }void pushdown(int x) { if(rev[x]) rev[x]^=,rev[l[x]]^=,rev[r[x]]^=,swap(l[x],r[x]); }void rotate(int x){    int y=fa[x];    if(l[y]==x) l[y]=r[x],fa[r[x]]=y,r[x]=y,fa[x]=fa[y],fa[y]=x;    else r[y]=l[x],fa[l[x]]=y,l[x]=y,fa[x]=fa[y],fa[y]=x;    if(root[y]) root[y]=,root[x]=;    else        if(r[fa[x]]==y) r[fa[x]]=x;        else l[fa[x]]=x;    pushup(y);}void splay(int x){    while(!root[x])    {        int y=fa[x],yy=fa[y];        if(root[y]) rotate(x);        else            if((l[yy]==y&&l[y]!=x)||(l[yy]!=y&&l[y]==x)) rotate(y),rotate(x);            else rotate(x),rotate(x);    }    pushup(x);}void access(int x){    int y=;    while(x)    {        splay(x); root[r[x]]=,root[y]=;        pushup(x); r[x]=y,y=x,x=fa[x];    }}void rever(int x) { access(x); splay(x); rev[x]^=; }void link(int x,int y) { rever(x); fa[l[x]]=,root[l[x]]=,l[x]=,fa[x]=y; pushup(x); }void cut(int x,int y) { rever(x); access(y); splay(y); l[y]=,fa[x]=; }int main(){    scanf("%d",&n);    for(int i=;i<=n;i++) root[i]=,siz[i]=;    for(int i=;i<=n;i++)    {        int x; scanf("%d",&x);        if(i+x<=n) link(i,i+x);    }    scanf("%d",&m);    while(m--)    {        int num,x,k; scanf("%d",&num);        if(num==)        {            scanf("%d",&x); x++;            rever(x);            printf("%d\n",siz[l[x]]+);        }        else        {            scanf("%d%d",&x,&k); x++;            if(x+k>n) link(x,);            else link(x,x+k);        }    }}`

bzoj2631 tree

`#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;const int Mx=;const int p=;int n,top,q[Mx],fa[Mx],son[Mx][],siz[Mx],rev[Mx];unsigned int val[Mx],sum[Mx],add_tag[Mx],mul_tag[Mx];inline int read(){    int x=,f=;char ch=getchar();    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}    return x*f;}void cal(int x,int a,int b){    if(!x) return ;    val[x]=(a*val[x]+b)%p;    sum[x]=(a*sum[x]+b*siz[x])%p;    add_tag[x]=(a*add_tag[x]+b)%p;    mul_tag[x]=(a*mul_tag[x])%p;}int isroot(int x){    if(son[fa[x]][]!=x&&son[fa[x]][]!=x) return ;    return ;}void pushup(int x){    int l=son[x][],r=son[x][];    sum[x]=(sum[l]+sum[r]+val[x])%p;    siz[x]=(siz[l]+siz[r]+)%p;}void pushdown(int x){    int l=son[x][],r=son[x][];    if(rev[x])        rev[x]^=,rev[l]^=,rev[r]^=,        swap(son[x][],son[x][]);    int a=add_tag[x],m=mul_tag[x];    add_tag[x]=,mul_tag[x]=;    if(a!=||m!=) cal(l,m,a),cal(r,m,a);}void rotate(int x){    int l=,r=,y=fa[x],yy=fa[y];    if(son[y][]==x) l=; r=l^;    if(!isroot(y)) son[yy][(son[yy][]==y)]=x;    fa[x]=yy,fa[y]=x,fa[son[x][r]]=y,son[y][l]=son[x][r],son[x][r]=y;    pushup(y);pushup(x);}void splay(int x){    q[++top]=x;    for(int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];    while(top) pushdown(q[top--]);    while(!isroot(x))    {        int y=fa[x],yy=fa[y];        if(!isroot(y))        {            if((son[y][]==x)^(son[yy][]==y)) rotate(x);            else rotate(y);        }        rotate(x);    }}void access(int x){    for(int t=;x;t=x,x=fa[x])        splay(x),son[x][]=t,pushup(x);}void rever(int x){    access(x); splay(x); rev[x]^=;}void link(int x,int y){    rever(x); fa[x]=y;}void split(int x,int y){    rever(y); access(x); splay(x);}void cut(int x,int y){    rever(x); access(y); splay(y);    son[y][]=fa[x]=;}signed main(){    int m; scanf("%d%d",&n,&m);    for(int i=;i<=n;i++) val[i]=sum[i]=mul_tag[i]=siz[i]=;    for(int i=,x,y;i<n;i++) scanf("%d%d",&x,&y),link(x,y);    while(m--)    {        char ch[]; scanf("%s",ch); int x,y,c; x=read(),y=read();        if(ch[]=='+') c=read(),split(x,y),cal(x,,c);        if(ch[]=='-') cut(x,y),x=read(),y=read(),link(x,y);        if(ch[]=='*') c=read(),split(x,y),cal(x,c,);        if(ch[]=='/') split(x,y),printf("%d\n",sum[x]);    }    return ;}`

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用

400-888-8888

ceotheme@ceo.com