HS
AFO
HS的博客
LOJ6046「雅礼集训 2017 Day8」爷

题目链接

LOJ

题目描述

给你一个$n$个点的有根树,$1$ 为根,带边权,有$m$次操作。

  1. 求$x$的子树中第$k$小的深度的值,如果子树中没有$k$个点则输出$-1$;
  2. 将$x$与$x$父亲的边权加上$k$。

保证每次操作 2 的$k$以及原树的边权小于等于一个数$len$。

如果操作 2 中$x$为$1$,那么视为将$x$的基础深度加上了$k$。

输入格式

第一行三个数 $n$、$m$、$len$。
之后 $n-1$ 行每行两个数表示 $2 \sim n$ 每个点的父亲编号,以及他们到父亲的边权。
之后 $m$ 行每行三个数 $opt$、$x$、$k$,$opt$ 表示操作种类,$x$、$k$ 意义如题所述。

输出格式

对于每个操作 1,输出一个数表示答案。

输入输出样例

输入 #1

3 5 3
1 3
2 3
1 1 3
2 3 3
1 1 3
2 1 2
1 1 3

输出 #1

6
9
11

说明/提示

对于 $10\%$ 的数据,$n,m \le 1000$;
对于 $30\%$ 的数据,$n,m \le 30000$;
对于 $100\%$ 的数据,$n,m \le 100000,len \le 10$。

本水题采用捆绑测试,你只有通过该部分分的所有数据才可以得到该部分分的分数。

分析

首先用$dfs$序将树上问题转换为区间问题。
问题变成了询问区间第$k$大。
朴素的想法是二分,对于每个块内再二分。
但这是$logn^2$的。
注意题目还有一个参数$len$,而且很小。
那么每个块内最大值于最小值的差不会变化特别快。
考入如果最大值和最小值相差不大的话可以使用前缀和少掉一个$log$。
所以规定一个块最大值和最小值相差不能超过一个闸值,如果超过就将其分裂。
但这样可能会分裂出很多块,因此定期重构即可。

一些对我而言的坑

每次重构的时候记得清空前缀和。
每次重构的时候记得重建链表。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 100010
const int S=400;
const int D=3000;
const int T=1000;
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
struct Edge
{
    int v;
    int w;
    Edge *next;
    Edge(int a=0,int b=0,Edge *c=NULL)
    {
        v=a;
        w=b;
        next=c;
    }
}*head[maxn];
int n,m,len,idx,cnt,a[maxn],L[maxn],R[maxn],mx[maxn],mn[maxn];
int dfn[maxn],tfn[maxn],bel[maxn],tag[maxn],nxt[maxn];
vector<int>val[maxn];
void dfs(int k,int dis)
{
    dfn[k]=++idx;
    a[idx]=dis;
    for(Edge *i=head[k];i!=NULL;i=i->next)
        dfs(i->v,dis+i->w);
    tfn[k]=idx;
}
void down(int x)
{
    if(tag[x])
    {
        for(int i=L[x];i<=R[x];i++)
            a[i]+=tag[x];
        tag[x]=0;
    }
}
void rebuild()
{
    for(int i=1;i<=cnt;i++)
        down(i);
    cnt=1;
    int pos=1;
    mx[cnt]=mn[cnt]=a[1];
    for(int i=2;i<=n+1;i++)
    {
        if(i>n||i-pos+1>S||mx[cnt]-a[i]>D||a[i]-mn[cnt]>D)
        {
            L[cnt]=pos;
            R[cnt]=i-1;
            nxt[cnt]=cnt+1;
            tag[cnt]=0;
            val[cnt].clear();
            val[cnt].resize(mx[cnt]-mn[cnt]+1);
            for(int j=L[cnt];j<=R[cnt];j++)
            {
                val[cnt][a[j]-mn[cnt]]+=1;
                bel[j]=cnt;
            }
            for(int j=1;j<=mx[cnt]-mn[cnt];j++)
                val[cnt][j]+=val[cnt][j-1];
            cnt+=1;
            mx[cnt]=mn[cnt]=a[i];
            pos=i;
            continue;
        }
        mx[cnt]=max(mx[cnt],a[i]);
        mn[cnt]=min(mn[cnt],a[i]);
    }
}
void build(int l,int r,int v)
{
    down(bel[l]);
    for(int i=l;i<=r;i++)
        a[i]+=v;
    int cur=bel[l],pos=L[cur],t=nxt[bel[l]];
    int be=L[cur],ed=R[cur];
    mx[cur]=mn[cur]=a[be];
    for(int i=be+1;i<=ed+1;i++)
    {
        if(i>ed||i-pos+1>S||mx[cur]-a[i]>D||a[i]-mn[cur]>D)
        {
            L[cur]=pos;
            R[cur]=i-1;
            tag[cur]=0;
            val[cur].clear();
            val[cur].resize(mx[cur]-mn[cur]+1);
            if(i<=ed)
                nxt[cur]=cnt+1;
            else
                nxt[cur]=t;
            for(int j=L[cur];j<=R[cur];j++)
            {
                val[cur][a[j]-mn[cur]]+=1;
                bel[j]=cur;
            }
            for(int j=1;j<=mx[cur]-mn[cur];j++)
                val[cur][j]+=val[cur][j-1];
            if(i<=ed)
            {
                cnt+=1;
                cur=cnt;
                mx[cur]=mn[cur]=a[i];
                pos=i;
            }
            continue;
        }
        mx[cur]=max(mx[cur],a[i]);
        mn[cur]=min(mn[cur],a[i]);
    }
}
void change(int l,int r,int v)
{
    if(bel[l]==bel[r])
    {
        build(l,r,v);
        return ;
    }
    for(int i=nxt[bel[l]];i!=bel[r];i=nxt[i])
    {
        tag[i]+=v;
        mx[i]+=v;
        mn[i]+=v;
    }
    build(l,R[bel[l]],v);
    build(L[bel[r]],r,v);
}
int calc(int l,int r,int v)
{
    down(bel[l]);
    int res=0;
    for(int i=l;i<=r;i++)
        res+=a[i]<=v;
    return res;
}
int query(int l,int r,int v)
{
    if(bel[l]==bel[r])
        return calc(l,r,v);
    int res=calc(l,R[bel[l]],v)+calc(L[bel[r]],r,v);
    for(int i=nxt[bel[l]];i!=bel[r];i=nxt[i])
    {
        if(v<mn[i])
            continue;
        if(v<mx[i])
            res+=val[i][v-mn[i]];
        else
            res+=val[i][mx[i]-mn[i]];
    }
    return res;
}
int solve(int L,int R,int k)
{
    if(R-L+1<k)
        return -1;
    int l=0,r=(n+m-1)*len;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(query(L,R,mid)>=k)
            r=mid-1;
        else
            l=mid+1;
    }
    return l;
}
int main()
{
    read(n,m,len);
    for(int i=2;i<=n;i++)
    {
        int f,w;
        read(f,w);
        head[f]=new Edge(i,w,head[f]);
    }
    dfs(1,0);
    rebuild();
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        read(op,x,y);
        if(op==1)
            printf("%d\n",solve(dfn[x],tfn[x],y));
        else
            change(dfn[x],tfn[x],y);
        if(i%T==0)
            rebuild();
    }
    return 0;
}

Gluttony

文章作者

发表评论

textsms
account_circle
email

HS的博客

LOJ6046「雅礼集训 2017 Day8」爷
分块+定期重构。
扫描二维码继续阅读
2020-01-16