absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] 主代码手的练习(北京赛区D)(hihoCoder 1630)
[破碎的状态] ARC073E

[破碎的状态] Codeforces 893F

absi2011 posted @ Nov 24, 2017 12:52:22 PM in 刷题记录 with tags 线段树 CF 小高考 瞎搞 , 802 阅读

http://codeforces.com/problemset/problem/893/F

题意:

n个点的树,r为根

强制在线的询问,以x为根的子树里面,深度<=k(根深度为0)的点的权值最小为多少

=====

解法:

bfs序

对于每个点,维护它深度+(1<<k)以后的l,r(这个区间内都是它在在+1<<k深度的孩子)

例如:

bfs序列是1234567...的完全二叉树

1的l[1]为4 r[1]为8

表示[4,8)这一段里面是1的第二层孩子

而2的l[1]/r[1]为[8,12),l[0]/r[0]为[4,6)

3的l[1]/r[1]为[12,16),l[0]/r[0]为[6,8)

那么,我们用线段树维护区间l,区间r

然后用倍增的思路,先bfs的时候初始化k=0,然后k=1 k=2 ... k=17

同时,val[i][k]也表示第i个点 在它到1<<k的深度以内的最小值

那么可以顺便维护好val[i][k]

每次询问,就用倍增的思路,每次询问一个区间的val的最小值

例如 x=1 深度为6 还是那个二叉树

首先询问 val[1][2] 然后我们要询问val[8..15][1]的最小值

 

然而在具体实现的时候,因为一些细节问题,我将自己设置为深度1,所以最后只要y++就可以了.....

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int depth[100005];
int a[100005];
int l[1<<18][18];
int r[1<<18][18];
int val[1<<18][18];
int dfn[100005];
int l_l[100005];
int r_r[100005];
int v_v[100005];
struct edge
{
    int y;
    edge * next;
};
edge * new_edge()
{
    static edge a[200005];
    static int top=0;
    return &a[top++];
}
edge * li[100005];
int fa[100005];
void inserts(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y)
{
    inserts(x,y);
    inserts(y,x);
}
void bfs(int s)
{
    memset(dfn,-1,sizeof(dfn));
    static int que[100005];
    int front=0,rail=1;
    que[0]=s;
    dfn[s]=0;
    for (;front<rail;front++)
    {
        edge * t;
        int now=que[front];
        l_l[front]=rail;
        v_v[front]=a[now];
        for (t=li[now];t!=0;t=t->next)
        {
            if (dfn[t->y]!=-1) continue;
            dfn[t->y]=rail;
            que[rail++]=t->y;
        }
        r_r[front]=rail;
        if (l_l[front]==r_r[front])
        {
            l_l[front]=1000000;
            r_r[front]=-1;
        }
    }
}
int query(int num,int ll,int rr,int l0,int r0,int i)
{
    if (l0>=r0) return 1000000000;
    if ((l0<=ll)&&(rr<=r0))
    {
        return val[num][i];
    }
    int mid=(ll+rr)/2;
    int ans=1000000000;
    if (l0<mid) ans=min(ans,query(num*2+1,ll,mid,l0,r0,i));
    if (mid<r0) ans=min(ans,query(num*2+2,mid,rr,l0,r0,i));
    return ans;
}
int query_l(int num,int ll,int rr,int l0,int r0,int i)
{
    if (l0>=r0) return 1000000;
    if ((l0<=ll)&&(rr<=r0))
    {
        return l[num][i];
    }
    int mid=(ll+rr)/2;
    int ans=1000000;
    if (l0<mid) ans=min(ans,query_l(num*2+1,ll,mid,l0,r0,i));
    if (mid<r0) ans=min(ans,query_l(num*2+2,mid,rr,l0,r0,i));
    return ans;
}
int query_r(int num,int ll,int rr,int l0,int r0,int i)
{
    if (l0>=r0) return -1;
    if ((l0<=ll)&&(rr<=r0))
    {
        return r[num][i];
    }
    int mid=(ll+rr)/2;
    int ans=-1;
    if (l0<mid) ans=max(ans,query_r(num*2+1,ll,mid,l0,r0,i));
    if (mid<r0) ans=max(ans,query_r(num*2+2,mid,rr,l0,r0,i));
    return ans;
}
void build_tree(int num,int ll,int rr)
{
    if (ll==rr-1)
    {
        val[num][0]=v_v[ll];
        l[num][0]=l_l[ll];
        r[num][0]=r_r[ll];
        return;
    }
    int mid=(ll+rr)/2;
    build_tree(num*2+1,ll,mid);
    build_tree(num*2+2,mid,rr);
    val[num][0]=min(val[num*2+1][0],val[num*2+2][0]);
    l[num][0]=min(l[num*2+1][0],l[num*2+2][0]);
    r[num][0]=max(r[num*2+1][0],r[num*2+2][0]);
}
int n;
void build_tree2(int num,int ll,int rr,int i)
{
    if (ll==rr-1)
    {
        l[num][i]=query_l(0,0,n,l[num][i-1],r[num][i-1],i-1);
        r[num][i]=query_r(0,0,n,l[num][i-1],r[num][i-1],i-1);
        val[num][i]=min(val[num][i-1],query(0,0,n,l[num][i-1],r[num][i-1],i-1));
        return;
    }
    int mid=(ll+rr)/2;
    build_tree2(num*2+1,ll,mid,i);
    build_tree2(num*2+2,mid,rr,i);
    val[num][i]=min(val[num*2+1][i],val[num*2+2][i]);
    l[num][i]=min(l[num*2+1][i],l[num*2+2][i]);
    r[num][i]=max(r[num*2+1][i],r[num*2+2][i]);
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int r;
    scanf("%d%d",&n,&r);
    r--;
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x--;
        y--;
        insert_edge(x,y);
    }
    bfs(r);
    int m;
    scanf("%d",&m);
    int last_ans=0;
    build_tree(0,0,n);
    for (i=1;i<=17;i++)
    {
        build_tree2(0,0,n,i);
    }
    for (i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x=(x+last_ans)%n;
        y=(y+last_ans)%n;
        int i;
        int ans=a[x];
        int nowl=dfn[x];
        int nowr=dfn[x]+1;
        y++;
        for (i=17;i>=0;i--)
        {
            if ((1<<i)&y)
            {
                y^=(1<<i);
                int lastl=nowl;
                int lastr=nowr;
                ans=min(ans,query(0,0,n,nowl,nowr,i));
                nowl=query_l(0,0,n,lastl,lastr,i);
                nowr=query_r(0,0,n,lastl,lastr,i);
            }
        }
        printf("%d\n",ans);
        last_ans=ans;
    }
    return 0;
}
PSC Result Rajshahi 说:
Aug 29, 2022 10:29:09 PM

Government of the People’s Republic of Bangladesh, Directorate of Primary Education (DPE), is going to announce PSC Result 2022 in student wide on 30th December 2022 for all divisional Grade 5 exam result with Ebtedayee Result 2022 for annual final terminal examinations, The Primary School Certificate Examination Result 2022 will be announced for both of General and Madhrsah students in division wise to all education board known as Prathomik Somaponi Result 2022. PSC Result Rajshahi BoardThe DPE has successfully conducted the class 5th grade PSC and Ebtedayee Examination tests from 17th to 24th November 2022 under all education boards of Dhaka, Chittagong, Comilla, Rajshahi, Sylhet, Barisal, Jessore, Dinajpur and Madrasah Board, and the DPE Grade-5 exams are successfully conducted at all 7,194 centers across the country.

PSC Result Rajshahi 说:
Aug 29, 2022 10:30:33 PM

Government of the People’s Republic of Bangladesh, Directorate of Primary Education (DPE), is going to announce PSC Result 2022 in student wide on 30th December 2022 for all divisional Grade 5 exam result with Ebtedayee Result 2022 for annual final terminal examinations, The Primary School Certificate Examination Result 2022 will be announced for both of General and Madhrsah students in division wise to all education board known as Prathomik Somaponi Result 2022. PSC Result Rajshahi BoardThe DPE has successfully conducted the class 5th grade PSC and Ebtedayee Examination tests from 17th to 24th November 2022 under all education boards of Dhaka, Chittagong, Comilla, Rajshahi, Sylhet, Barisal, Jessore, Dinajpur and Madrasah Board, and the DPE Grade-5 exams are successfully conducted at all 7,194 centers across the country.


登录 *


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