bzoj 4704/CF 226E

首先吐槽一下bzoj,这CF原题还做成权限题啊?!

需要注意的是,一个点不能被选中当且进当这个点在第y+1年到现在这一段时间内受到攻击,其余的点都可以被选

然后...其实这题的重点在于...码

思想很简单,先树链剖分,然后建起一棵主席树维护,每次修改就生成一个新版本,这样的话用现在的版本-时刻y的版本就可以算出这段时间不能用的点的个数,再用总点数去减就是可以用的个数了

然后在查询时查到一个确定的重链上就可以二分答案了(不建议写倍增,因为倍增的话边界情况不好处理)

其实这种题重点应该是看代码啦...

注意几个细节:

题目要求起点和终点不算,因此我在代码中处理掉了这两个点,把他们上移或下移了一个位置

其次,注意LCA不要被重复统计

而且,一定要注意跳的顺序是起点-LCA-终点,不要像普通的树剖那样起点终点一起跳!

剩下看代码吧

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#define ls tree[rt].lson
#define rs tree[rt].rson
using namespace std;
struct Per_Seg_Tree
{
    int lson,rson;
    int siz;
}tree[8000005];
int rot[100005];
int RT=0;
vector <int> v[100005];
int siz[100005];
int son[100005];
int w[100005];
int f[100005][25];
int nnum[100005];
int ttop[100005];
int onum[100005];
int dep[100005];
int vis[100005];
int tot=0,cnt=0,ts=0;
int n,m;
void dfs(int x,int fx)
{
    siz[x]=1,f[x][0]=fx,dep[x]=dep[fx]+1;
    int maxh=0;
    for(int i=1;i<=20;i++)f[x][i]=f[f[x][i-1]][i-1];
    for(int i=0;i<v[x].size();i++)
    {
        int to=v[x][i];
        if(to==fx)continue;
        dfs(to,x);
        siz[x]+=siz[to];
        if(siz[to]>maxh)maxh=siz[to],son[x]=to;
    }
}
void redfs(int x,int fx,int topx)
{
    ttop[x]=topx;
    nnum[x]=++ts,onum[ts]=x;
    if(son[x])redfs(son[x],x,topx);
    for(int i=0;i<v[x].size();i++)
    {
        int to=v[x][i];
        if(to==son[x]||to==fx)continue;
        redfs(to,x,to);
    }
}
void pushup(int rt)
{
    tree[rt].siz=tree[ls].siz+tree[rs].siz;
}
void buildtree(int &rt,int l,int r)
{
    rt=++tot;
    if(l==r){tree[rt].siz=0;return;}
    int mid=(l+r)>>1;
    buildtree(ls,l,mid),buildtree(rs,mid+1,r);
    pushup(rt);
}
void update(int &rt,int lrt,int l,int r,int pos)
{
    rt=++tot;
    if(l==r){tree[rt].siz=1;return;}
    int mid=(l+r)>>1;
    if(pos<=mid)rs=tree[lrt].rson,update(ls,tree[lrt].lson,l,mid,pos);
    else ls=tree[lrt].lson,update(rs,tree[lrt].rson,mid+1,r,pos);
    pushup(rt);
}
int query(int rt1,int rt2,int l,int r,int lq,int rq)
{
    if(l>=lq&&r<=rq)return tree[rt2].siz-tree[rt1].siz;
    int mid=(l+r)>>1;
    int s=0;
    if(lq<=mid)s+=query(tree[rt1].lson,tree[rt2].lson,l,mid,lq,rq);
    if(rq>mid)s+=query(tree[rt1].rson,tree[rt2].rson,mid+1,r,lq,rq);
    return s;
}
int LCA(int x,int y)
{
    while(ttop[x]!=ttop[y])
    {
        if(dep[ttop[x]]<dep[ttop[y]])swap(x,y);
        x=f[ttop[x]][0];
    }
    return dep[x]<dep[y]?x:y;
}
int Jump(int x,int ed)
{
    for(int i=20;i>=0;i--)if(dep[f[x][i]]>dep[ed])x=f[x][i];
    return x;
}
int upsolve(int fr,int to,int qy,int k)
{
    int l=nnum[to],r=nnum[fr],ans=to;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        int num=dep[fr]-dep[onum[mid]]+1;
        int delt=query(rot[qy],rot[cnt],1,n,mid,nnum[fr]);
        if(num-delt>=k)ans=onum[mid],l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int dosolve(int fr,int to,int qy,int k)
{
    int l=nnum[to],r=nnum[fr],ans=to;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        int num=dep[onum[mid]]-dep[to]+1;
        int delt=query(rot[qy],rot[cnt],1,n,nnum[to],mid);
        if(num-delt>=k)ans=onum[mid],r=mid-1;
        else l=mid+1;
    }
    return ans;
}
int goup(int st,int ed,int qy,int &k)
{
    while(ttop[st]!=ttop[ed])
    {
        int num=dep[st]-dep[ttop[st]]+1;
        int delt=query(rot[qy],rot[cnt],1,n,nnum[ttop[st]],nnum[st]);
        if(num-delt>=k)
        {
            return upsolve(st,ttop[st],qy,k);
        }else k-=num-delt,st=f[ttop[st]][0];
    }
    int num=dep[st]-dep[ed]+1;
    int delt=query(rot[qy],rot[cnt],1,n,nnum[ed],nnum[st]);
    if(num-delt>=k)
    {
        return upsolve(st,ed,qy,k);
    }else {k-=num-delt;return 0;}
}
int godown(int st,int ed,int qy,int k)
{
    if(st==ed)
    {
        if(k==1&&vis[st]<=qy)return st;
        else return 0;
    }
    stack <int> S;
    while(ttop[st]!=ttop[ed])S.push(st),S.push(ttop[st]),st=f[ttop[st]][0];
    if(st!=ed)S.push(st);
    else 
    {
        if(vis[ed]<=qy)
        {
            if(k==1)return ed;
            else k--;
        }
        ed=S.top();S.pop();
    }
    while(!S.empty())
    {
        int u=S.top();
        S.pop();
        int num=dep[u]-dep[ed]+1;
        int delt=query(rot[qy],rot[cnt],1,n,nnum[ed],nnum[u]);
        if(num-delt>=k)
        {
            return dosolve(u,ed,qy,k);
        }else 
        {
            k-=num-delt;
            if(!S.empty()){ed=S.top();S.pop();}
        }
    }
    return 0;
}
/*inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}*/
int main()
{
    //n=read();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i][0]);
        if(f[i][0])v[f[i][0]].push_back(i);
        else RT=i;
    }    
    dfs(RT,RT);
    redfs(RT,RT,RT);
    buildtree(rot[0],1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int typ;
        scanf("%d",&typ);
        if(typ==1)
        {
            int p;
            w[i]=++cnt;
            scanf("%d",&p);
            update(rot[cnt],rot[cnt-1],1,n,nnum[p]),vis[p]=cnt;
        }else
        {
            w[i]=w[i-1];
            int st,ed,k,y;
            scanf("%d%d%d%d",&st,&ed,&k,&y);
            if(f[st][0]==ed||f[ed][0]==st){printf("-1\n");continue;}
            y=w[y];
            int fa=LCA(st,ed);
            if(fa==st)
            {
                st=Jump(ed,fa),ed=f[ed][0];
                int t=godown(ed,st,y,k);
                if(!t)printf("-1\n");
                else printf("%d\n",t);
            }else if(fa==ed)
            {
                ed=Jump(st,fa),st=f[st][0];
                int t=goup(st,ed,y,k);
                if(!t)printf("-1\n");
                else printf("%d\n",t);
            }else 
            {
                st=f[st][0],ed=f[ed][0];
                int t=goup(st,fa,y,k);
                if(t)printf("%d\n",t);
                else if(ed==fa){printf("-1\n");continue;}
                else 
                {
                    fa=Jump(ed,fa);
                    t=godown(ed,fa,y,k);
                    if(t)printf("%d\n",t);
                    else printf("-1\n");
                }
            }
        }
    }
    return 0;
}

 

上一篇:luogu P3153 [CQOI2009]跳舞


下一篇:洛谷 P1110 [ZJOI2007]报表统计