absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] [-1] (Failed)Splay BZOJ 1056
[破碎的状态] [1] UOJ 212

[破碎的状态] [-0] Hdu 4010

absi2011 posted @ Jul 22, 2016 08:46:43 AM in 刷题记录 with tags 小高考 动态树 瞎搞 HDU , 713 阅读

一个LCT的模版题

写错了好多次..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int maxn=300005;
const int inf=1999999999;
pair<int,int> p[300005];
struct node
{
    int val;
    int max_val;
    int tag;
    bool rev_tag;
    node * ch[2];
    node * father;
};
int top=0;
node * null;
node * a[maxn];
node * new_node(int x)
{
    static node a[300005];
    node * t=&a[top++];
    t->val=x;
    t->max_val=x;
    t->tag=0;
    t->rev_tag=0;
    t->ch[0]=null;
    t->ch[1]=null;
    t->father=null;
    return t;
}
void push_down(node * x)
{
    if (x->rev_tag)
    {
        swap(x->ch[0],x->ch[1]);
        x->ch[0]->rev_tag^=1;
        x->ch[1]->rev_tag^=1;
        x->rev_tag=false;
    }
    if (x->tag)
    {
        if (x->ch[0]!=null)
        {
            x->ch[0]->tag+=x->tag;
            x->ch[0]->max_val+=x->tag;
            x->ch[0]->val+=x->tag;
        }
        if (x->ch[1]!=null)
        {
            x->ch[1]->tag+=x->tag;
            x->ch[1]->max_val+=x->tag;
            x->ch[1]->val+=x->tag;
        }
        x->tag=0;
    }
}
int get_up(node * x)
{
    if (x->father->ch[0]==x) return 0;
    if (x->father->ch[1]==x) return 1;
    return -1;
}
void rotate(node * &x,int c)
{
    node * y=x->ch[c];
    x->ch[c]=y->ch[!c];
    y->ch[!c]->father=x;
    y->ch[!c]=x;
    y->father=x->father;
    x->father=y;
    y->max_val=x->max_val;
    x->max_val=max(x->val,max(x->ch[0]->max_val,x->ch[1]->max_val));
    x=y;
}
void splay(node * x)
{
    for (;;)
    {
        push_down(x->father->father);
        push_down(x->father);
        push_down(x);
        int t1=get_up(x);
        if (t1==-1) return;
        int t2=get_up(x->father);
        if (t2==-1)
        {
            x=x->father;
            rotate(x,t1);
            return;
        }
        int t3=get_up(x->father->father);
        if (t3==-1)
        {
            if (t1==t2)
            {
                x=x->father;
                x=x->father;
                rotate(x,t2);
                rotate(x,t1);
            }
            else
            {
                x=x->father;
                x=x->father;
                rotate(x->ch[t2],t1);
                rotate(x,t2);
            }
        }
        else
        {
            if (t1==t2)
            {
                x=x->father;
                x=x->father;
                x=x->father;
                rotate(x->ch[t3],t2);
                rotate(x->ch[t3],t1);
                x=x->ch[t3];
            }
            else
            {
                x=x->father;
                x=x->father;
                rotate(x->ch[t2],t1);
                x=x->father;
                rotate(x->ch[t3],t2);
                x=x->ch[t3];
            }
        }
    }
}
void access(node * &x)
{
    for (;;)
    {
        splay(x);
        if (x->father==null)
        {
            x->ch[1]=null;
            x->max_val=max(x->val,x->ch[0]->max_val);
            return;
        }
        splay(x->father);
        x->father->ch[1]=x;
        x->father->max_val=max(x->father->ch[0]->max_val,max(x->father->val,x->max_val));
    }
}
void evert(node * x)
{
    access(x);
    x->rev_tag=true;
}
void merges(node * x,node * y)
{
    evert(x);
    x->father=y;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    null=new_node(-inf);
    null->ch[0]=null;
    null->ch[1]=null;
    null->father=null;
    for (;scanf("%d",&n)!=-1;)
    {
        top=1;
        int i;
        for (i=1;i<n;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            x--;
            y--;
            p[i]=make_pair(x,y);
        }
        for (i=0;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            a[i]=new_node(x);
        }
        for (i=1;i<n;i++)
        {
            merges(a[p[i].first],a[p[i].second]);
        }
        int m;
        scanf("%d",&m);
        for (i=0;i<m;i++)
        {
            int oper;
            scanf("%d",&oper);
            int x,y;
            if (oper==1)
            {
                scanf("%d%d",&x,&y);
                x--;
                y--;
                evert(a[x]);
                access(a[y]);
                if ((a[x]->father!=null)||(x==y))
                {
                    printf("-1\n");
                    continue;
                }
                merges(a[x],a[y]);
            }
            else if (oper==2)
            {
                scanf("%d%d",&x,&y);
                x--;
                y--;
                evert(a[x]);
                access(a[y]);
                if ((a[x]->father==null)||(x==y))
                {
                    printf("-1\n");
                    continue;
                }
                a[y]->ch[0]->father=null;
                a[y]->ch[0]=null;
                a[y]->max_val=a[y]->val;
            }
            else if (oper==3)
            {
                int z;
                scanf("%d",&z);
                scanf("%d%d",&x,&y);
                x--;
                y--;
                evert(a[x]);
                access(a[y]);
                if ((a[x]->father==null)&&(x!=y))
                {
                    printf("-1\n");
                    continue;
                }
                a[y]->tag+=z;
                a[y]->val+=z;
                a[y]->max_val+=z;
            }
            else
            {
                scanf("%d%d",&x,&y);
                x--;
                y--;
                evert(a[x]);
                access(a[y]);
                if ((a[x]->father==null)&&(x!=y))
                {
                    printf("-1\n");
                    continue;
                }
                printf("%d\n",a[y]->max_val);
            }
        }
        printf("\n");
    }
    return 0;
}
boardmodelpaper.com 说:
Jan 25, 2024 03:02:29 PM

The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.


登录 *


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