absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] [-26] 100543 J
[破碎的状态] [-23] 487D

[破碎的状态] [-25] Codeforces 226E

absi2011 posted @ Jun 27, 2016 08:15:33 PM in 刷题记录 with tags 线段树 小高考 CF 树链剖分 可持久化 , 358 阅读

感谢@JCarlson 翻译....

JCarlson翻译的太长了所以我决定直接贴出来而不概括了..

初中历史书有云:“我的附庸的附庸,不是我的附庸。”萌萌的小R对此很感兴趣,于是去调查了一下中世纪的西方历史。他决定以Berland这一小国作为事例研究。
Berland是一个拥有众多城堡的国家,每一个贵族都坐拥一座且仅有一座大城堡。Berland的国王管辖下面若干个诸侯,这些诸侯又管辖下面若干个小诸侯,但是国王是无法直接管辖小诸侯的。如果两个贵族之间是管辖与被管辖的关系,出于信息传递的必要,他们会在两座城堡之间修建一条路。
同时小R在调研Berland历史的时候发现了一个很奇怪的事情。他惊奇的发现每一年,都会发生以下两件事中的其中一件:
1、外敌攻打了城堡c。从已知的历史来看,外敌不会攻打以前曾经打过的城堡。
2、皇家骑士会从城堡a向城堡b周游。(一个城堡在一次周游中只能被访问一次)
小R仔细调研了关于皇家骑士周游的问题。他发现由于每次周游经过的城堡都有可能很多,骑士会在周游期间的其中一个城堡休息一下。出于其贵族身份,骑士并不会在被摧毁的城堡中休息。定义一个被摧毁的城堡为在第y年之后被外敌攻打过的城堡。概括一下,骑士会在a到b的路径中(a和b不算在里头),选择第k个没被摧毁的城堡休息。如果骑士选择的这条周游路径上不存在第k个没被摧毁的城堡,骑士只能不休息了。

小R通过某些途径得到了Berland的一份大年表,上面详细记载了y年来外敌的入侵记录和骑士的周游记录。很遗憾的是,这些记录并没有留下骑士们是在哪个城堡休息的,小R决定要找出这个答案。

这道题9K代码写伤了..

这是个非常奇怪的题..

里面包含两部分..

一部分叫做可持久化线段树

一部分叫树链剖分

实际上..是可持久化线段树来维护的树链剖分..

#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;
struct node
{
    int val;
    node * ch[2]; 
};
node * root[100005];
node * new_node()
{
    static node a[2000005];
    static int top=0;
    return &a[top++];
}
struct edge
{
    int y;
    edge * next;
};
edge * li[100005];
edge * new_edge()
{
    static edge a[100005];
    static int top=0;
    return &a[top++];
}
void insert_edge(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
int up[100005];
int vis[100005];
int dfn[100005];
int size[100005];
int depth[100005];
int father[100005];
edge * prefer[100005];
void dfs1(int x)
{
    edge * t;
    int max_val=0;
    size[x]=1;
    for (t=li[x];t!=0;t=t->next)
    {
        depth[t->y]=depth[x]+1;
        dfs1(t->y);
        size[x]+=size[t->y];
        if (size[t->y]>max_val)
        {
            max_val=size[t->y];
            prefer[x]=t; 
        }
    }
}
void dfs2(int x)
{
    static int now=0;
    dfn[x]=now;
    vis[now]=x;
    now++;
    if (prefer[x]==0) return ;
    up[prefer[x]->y]=up[x];
    dfs2(prefer[x]->y);
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (prefer[x]==t) continue;
        up[t->y]=t->y;
        dfs2(t->y);
    }
}
void build_tree(node * &x,int l,int r)
{
    x=new_node();
    x->val=0;
    if (l==r-1)
    {
        return;
    }
    int mid=(l+r)/2;
    build_tree(x->ch[0],l,mid);
    build_tree(x->ch[1],mid,r);
}
void change(node * &x,int l,int r,int val)
{
    node * t=x;
    x=new_node();
    (*x)=(*t);
    x->val++;
    if (l==r-1)
    {
        return;
    }
    int mid=(l+r)/2;
    if (val<mid) change(x->ch[0],l,mid,val);
    else change(x->ch[1],mid,r,val);
}
int query(node * &x,int l,int r,int l0,int r0)
{
    if ((l0<=l)&&(r<=r0))
    {
        return x->val;
    }
    int mid=(l+r)/2;
    int ans=0;
    if (l0<mid) ans+=query(x->ch[0],l,mid,l0,r0);
    if (mid<r0) ans+=query(x->ch[1],mid,r,l0,r0);
    return ans;
}
int n;
void check_ans(int l,int r,int k,int i,int yy)
{
    for (;l<=r;)
    {
        int mid=(l+r)/2;
        int t=query(root[i],0,n,l,mid+1);
        t-=query(root[yy],0,n,l,mid+1);
        if ((mid-l+1)-t+k>0)
        {
            r=mid-1;
        }
        else
        {
            k+=(mid-l+1)-t;
            l=mid+1;
        }
    }
    printf("%d\n",vis[l]+1);
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    scanf("%d",&n);
    int i;
    int center=0;
    for (i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        x--;
        father[i]=x;
        if (x==-1)
        {
            center=i;
            continue;
        }
        insert_edge(x,i);
    }
    depth[center]=0;
    dfs1(center);
    up[center]=center;
    dfs2(center);
    int m;
    scanf("%d",&m);
    build_tree(root[0],0,n);
    for (i=1;i<=m;i++)
    {
        root[i]=root[i-1];
        int oper;
        scanf("%d",&oper);
        if (oper==1)
        {
            int x;
            scanf("%d",&x);
            x--;
            change(root[i],0,n,dfn[x]);
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            y--;
            int k;
            scanf("%d",&k);
            int yy;
            scanf("%d",&yy);
            int tx=x;
            int ty=y;
            int sum=-1;
            int tot=0;
            k++;
            k-=query(root[i],0,n,dfn[x],dfn[x]+1);
            k+=query(root[yy],0,n,dfn[x],dfn[x]+1);
            tot-=query(root[i],0,n,dfn[y],dfn[y]+1);
            tot+=query(root[yy],0,n,dfn[y],dfn[y]+1);
            for (;;)
            {
                if (up[tx]==up[ty])
                {
                    if (depth[tx]<depth[ty]) swap(tx,ty);
                    sum+=dfn[tx]-dfn[ty]+1;
                    tot+=query(root[i],0,n,dfn[ty],dfn[tx]+1);
                    tot-=query(root[yy],0,n,dfn[ty],dfn[tx]+1);
                    break;
                }
                else
                {
                    if (depth[up[tx]]<depth[up[ty]])
                    {
                        swap(tx,ty);
                    }
                    sum+=dfn[tx]-dfn[up[tx]]+1;
                    tot+=query(root[i],0,n,dfn[up[tx]],dfn[tx]+1);
                    tot-=query(root[yy],0,n,dfn[up[tx]],dfn[tx]+1);
                    tx=father[up[tx]];
                }
            }
            if (sum-tot<k)
            {
                printf("-1\n");
            }
            else
            {
                tot+=query(root[i],0,n,dfn[y],dfn[y]+1);
                tot-=query(root[yy],0,n,dfn[y],dfn[y]+1);
                sum++;
                int top=ty;
                for (;;)
                {
                    if (up[x]==up[top])
                    {
                        int t=query(root[i],0,n,dfn[top],dfn[x]+1);
                        t-=query(root[yy],0,n,dfn[top],dfn[x]+1);
                        sum-=dfn[x]-dfn[top]+1;
                        k-=dfn[x]-dfn[top]+1-t;
                        tot-=t;
                        if (k<=0)
                        {
                            check_ans(dfn[top],dfn[x],k,i,yy);
                            break;
                        }
                        sum++;
                        t=query(root[i],0,n,dfn[top],dfn[top]+1);
                        t-=query(root[yy],0,n,dfn[top],dfn[top]+1);
                        k+=1-t;
                        tot+=t;
                        for (;;)
                        {
                            if (up[y]==up[top])
                            {
                                int t=query(root[i],0,n,dfn[top],dfn[y]+1);
                                t-=query(root[yy],0,n,dfn[top],dfn[y]+1);
                                sum-=dfn[y]-dfn[top]+1;
                                tot-=t;
                                if (sum-tot<k)
                                {
                                    /*
                                    sum+=dfn[y]-dfn[top]+1;
                                    tot+=t;
                                    */
                                    check_ans(dfn[top],dfn[y],(sum-tot)-k+1,i,yy);
                                    break;
                                }
                            }
                            else
                            {
                                int t=query(root[i],0,n,dfn[up[y]],dfn[y]+1);
                                t-=query(root[yy],0,n,dfn[up[y]],dfn[y]+1);
                                sum-=dfn[y]-dfn[up[y]]+1;
                                tot-=t;
                                if (sum-tot<k)
                                {
                                    /*
                                    sum+=dfn[y]-dfn[up[y]]+1;
                                    tot+=t;
                                    */
                                    check_ans(dfn[up[y]],dfn[y],(sum-tot)-k+1,i,yy);
                                    break;
                                }
                                y=father[up[y]];
                            }
                        }
                        break;
                    }
                    else
                    {
                        int t=query(root[i],0,n,dfn[up[x]],dfn[x]+1);
                        t-=query(root[yy],0,n,dfn[up[x]],dfn[x]+1);
                        sum-=dfn[x]-dfn[up[x]]+1;
                        k-=dfn[x]-dfn[up[x]]+1-t;
                        tot-=t;
                        if (k<=0)
                        {
                            check_ans(dfn[up[x]],dfn[x],k,i,yy);
                            break;
                        }
                        x=father[up[x]];
                    }
                }
            }
        }
    }
    return 0;
}

登录 *


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