题解 P3605 [USACO17JAN]Promotion Counting P

· · 个人记录

分块yyds

————关于线段树合并的题我用分块过掉这件事

题目传送门

先说正解

正解当然是线段树合并等一类做法了

至于解析。。。出门右转题解区第一篇 （就是他让我看不懂，然后用分块打的QAQ）

给出 fengwu 的code

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define re register int
const int N=100005;
int n;
int p[N],d[N];
int to[N],nxt[N],head[N],rp;
int rt[N],ans[N];
bool cmp(int x,int y){return p[x]<p[y];}
void add_edg(int x,int y){
    to[++rp]=y;
    nxt[rp]=head[x];
    head[x]=rp;
}
struct node{
    int sum[N*80];
    int ls[N*80],rs[N*80];
    int cnt;
    int insert(int x,int l,int r,int pos){
        if(!x)x=++cnt;
        sum[x]++;
        if(l==r)return x;
        int mid=(l+r)>>1;
        if(pos<=mid)ls[x]=insert(ls[x],l,mid,pos);
        else rs[x]=insert(rs[x],mid+1,r,pos);
        sum[x]=sum[ls[x]]+sum[rs[x]];
        return x;
    }
    int query(int x,int l,int r,int pos){
        if(!x)return 0;
        if(l==r)return sum[x];
        int mid=(l+r)>>1;
        if(pos<=mid)return query(ls[x],l,mid,pos)+sum[rs[x]];
        else return query(rs[x],mid+1,r,pos);
    }
    int marge(int x,int y,int l,int r){
        if(!x)return y+x;
        if(!y)return x+y;
        if(l==r){
            sum[x]+=sum[y];
            return x;
        }
        int mid=(l+r)>>1;
        ls[x]=marge(ls[x],ls[y],l,mid);
        rs[x]=marge(rs[x],rs[y],mid+1,r);
        sum[x]=sum[ls[x]]+sum[rs[x]];
        return x;
    }
}xds;
void dfs(int x){
    for(re i=head[x];i;i=nxt[i])
        dfs(to[i]);
    rt[x]=xds.insert(rt[x],1,n+1,p[x]);
    for(re i=head[x];i;i=nxt[i])
        rt[x]=xds.marge(rt[x],rt[to[i]],1,n+1);
    ans[x]=xds.query(rt[x],1,n+1,p[x]+1);
}
int main(){
    scanf("%d",&n);
    for(re i=1;i<=n;i++)
        scanf("%d",&p[i]),d[i]=i;
    sort(d+1,d+n+1,cmp);
    for(re i=1;i<=n;i++)p[d[i]]=i;
    for(re i=2;i<=n;i++){
        int f;
        scanf("%d",&f);
        add_edg(f,i);
    }
    dfs(1);
    for(re i=1;i<=n;i++){
        printf("%d\n",ans[i]);
    }
}

再谈分块

分块么，无非就是优化的暴力，所以调试到崩溃的我斗胆交了一下暴力代码 =>70pts 出乎意料！！！

然后我吸了口毒氧 ，再然后就100pts了。。。

这个不会的就不用出门了，凑合看看就能懂，下面给出code以及我的link

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int m,n,tot,cnt,tmp,tim,ans,fz[N+5],Ans[N+5],tail[N+5],ys[N+5],num[N+5],nxt[N+5],head[N+5],ver[N+5];
struct jz
{
    int id,num,pos;
}s[N+5];
bool comp(jz x,jz y)
{
    if(x.id!=y.id)
        return x.id<y.id;
}
void lsh()
{
    for(int i=1;i<=n;i++)
        ys[i]=s[i].num;
    sort(ys+1,ys+n+1);
    tmp=unique(ys+1,ys+n+1)-ys-1;
    for(int i=1;i<=n;i++)
        s[i].num=lower_bound(ys+1,ys+tmp+1,s[i].num)-ys;
}
void add_edge(int x,int y)
{
    ver[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
int dfs(int x)
{
    s[x].id=++tim;
    if(head[x]==0)
        return tail[x]=x;
    for(int i=head[x];i;i=nxt[i])
    {
        int jud=dfs(ver[i]);
        if(s[jud].id>s[tail[x]].id)
            tail[x]=jud;
    }
    return tail[x];
}
int ask(int li,int ri,int k)
{
    if(li>ri) return 0;
    for(int i=li;i<=ri;i++)
        if(s[i].num>=k)
            ans++;
    return ans;
}
signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&s[i].num),s[i].pos=i;
    for(int i=2,x;i<=n;i++)
        scanf("%d",&x),add_edge(x,i);
    lsh();
    dfs(1);
    sort(s,s+n+1,comp);
    for(int i=1;i<=n;i++)
        fz[s[i].pos]=s[i].id;
    for(int i=1;i<=n;i++)
        Ans[s[i].pos]=ask(i+1,fz[tail[s[i].pos]],s[i].num+1);
    for(int i=1;i<=n;i++)
        printf("%d\n",Ans[i]);
    return 0;
}

然后嘞就是详解以及分块做法了（调了好久就因为一个j打成了i，痛哭.jpg）link

思路比较简单

先是读入

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&s[i].num),s[i].pos=i;
    for(int i=2,x;i<=n;i++)
        scanf("%d",&x),add_edge(x,i);

然后离散化一下

void lsh()
{
    for(int i=1;i<=n;i++)
        ys[i]=s[i].num;
    sort(ys+1,ys+n+1);
    tmp=unique(ys+1,ys+n+1)-ys-1;
    for(int i=1;i<=n;i++)
        s[i].num=lower_bound(ys+1,ys+tmp+1,s[i].num)-ys;
}

然后就是重点了，先建边，读入的时候一定要从2开始，因为1是没有上司的然后dfs一下求出每个点被便历到的s[i].id值，同时记录一下tail[i]（表示在原顺序下的i的最后一个下属）

分为以下两种情况：

  1. 已经是最后一个，没有下属，那么head[x]一定是0，此时直接return，并且给tail[x]赋值

  2. 有子节点，此时用一个jud记录一下子节点返回的tail，然后与现在存的tail比较id值，取id值较大的，即最后扫描到的，最后不要忘了return一下

int dfs(int x)
{
    s[x].id=++tim;
    if(head[x]==0)
        return tail[x]=x;
    for(int i=head[x];i;i=nxt[i])
    {
        int jud=dfs(ver[i]);
        if(s[jud].id>s[tail[x]].id)
            tail[x]=jud;
    }
    return tail[x];
}

然后给s结构体按照id顺序排个序，顺便用fz数组记录一下：fz[i]=j表示先前为第i的点现在的下标是j

接下来就是愉快的分块了

    t=sqrt(n);
    for(int i=1;i<=t;i++)
    {
        l[i]=(i-1)*sqrt(n)+1;
        r[i]=i*sqrt(n);
    }
    if(r[t]<n)
    {
        t++;
        l[t]=r[t-1]+1;
        r[t]=n;
    }

接下来的做法就与教主的魔法相似了，大概意思就是再建一个数组储存每个块排序后的样子，在二分查找一下就好了，不会的嘛，老办法，出门右转题解区qwq。

最后在拿一个Ans数组存一下输出就OK了

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int m,t,n,tot,cnt,tmp,tim,ans,fz[N+5],Ans[N+5],tail[N+5],ys[N+5],pos[N+5],l[N+5],r[N+5],num[N+5],nxt[N+5],head[N+5],ver[N+5];
struct jz
{
    int id,num,pos;
}s[N+5];
bool comp(jz x,jz y)
{
    if(x.id!=y.id)
        return x.id<y.id;
    return x.num>y.num;
}
void lsh()
{
    for(int i=1;i<=n;i++)
        ys[i]=s[i].num;
    sort(ys+1,ys+n+1);
    tmp=unique(ys+1,ys+n+1)-ys-1;
    for(int i=1;i<=n;i++)
        s[i].num=lower_bound(ys+1,ys+tmp+1,s[i].num)-ys;
}
void add_edge(int x,int y)
{
    ver[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
int dfs(int x)
{
    s[x].id=++tim;
    if(head[x]==0)
        return tail[x]=x;
    for(int i=head[x];i;i=nxt[i])
    {
        int jud=dfs(ver[i]);
        if(s[jud].id>s[tail[x]].id)
            tail[x]=jud;
    }
    return tail[x];
}
int ask(int li,int ri,int k)
{
    if(li>ri) return 0;
    int p=pos[li],q=pos[ri],ans=0;
    if(p==q)
    {
        for(int i=li;i<=ri;i++)
            if(s[i].num>=k)
                ans++;
        return ans;
    }
    for(int i=li;i<=r[p];i++)
        if(s[i].num>=k)
            ans++;
    for(int i=p+1;i<q;i++)
        ans+=r[i]+1-(lower_bound(num+l[i],num+r[i]+1,k)-num);
    for(int i=l[q];i<=ri;i++)
        if(s[i].num>=k)
            ans++;
    return ans;
}
signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&s[i].num),s[i].pos=i;
    for(int i=2,x;i<=n;i++)
        scanf("%d",&x),add_edge(x,i);
    lsh();
    dfs(1);
    sort(s,s+n+1,comp);
    for(int i=1;i<=n;i++)
        fz[s[i].pos]=s[i].id;
    t=sqrt(n);
    for(int i=1;i<=t;i++)
    {
        l[i]=(i-1)*sqrt(n)+1;
        r[i]=i*sqrt(n);
    }
    if(r[t]<n)
    {
        t++;
        l[t]=r[t-1]+1;
        r[t]=n;
    }
    for(int i=1;i<=t;i++)
    {
        for(int j=l[i];j<=r[i];j++)
        {
            pos[j]=i;
            num[j]=s[j].num;
        }
        sort(num+l[i],num+r[i]+1);
    }
    for(int i=1;i<=n;i++)
        Ans[s[i].pos]=ask(i+1,fz[tail[s[i].pos]],s[i].num+1);
    for(int i=1;i<=n;i++)
        printf("%d\n",Ans[i]);
    return 0;
}

不得不说这个题让我的调试能力大增。。。