注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4154][Ipsc2015]Generating Synergy  

2015-06-27 20:10:40|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4154: [Ipsc2015]Generating Synergy

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 116  Solved: 44
[Submit][Status][Discuss]

Description

给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色

Input

第一行一个数T,表示数据组数
接下来每组数据的第一行三个数n,c,q表示结点个数,颜色数和操作数
接下来一行n-1个数描述2..n的父节点
接下来q行每行三个数a,l,c
若c为0,表示询问a的颜色
否则将距离a不超过l的a的子节点染成c

Output

设当前是第i个操作,y_i为本次询问的答案(若本次操作是一个修改则y_i为0),令z_i=i*y_i,请输出z_1+z_2+...+z_q模10^9+7

Sample Input

1 4 3 7 1 2 2 3 0 0 2 1 3 3 0 0 1 0 2 2 0 0 4 1 1 4 0 0

Sample Output

32

HINT

第1,3,5,7的询问的答案分别为1,3,3,1,所以答案为 1*1+2*0+3*3+4*0+5*3+6*0+7*1=32.
数据范围:
对于100%的数据T<=6,n,m,c<=10^5,
1<=a<=n,0<=l<=n,0<=c<=c

Solution

解法是神啊。把dfs序和深度变成二维平面上的点,然后每次修改就变成一块矩形区域内的修改了。kdtree实现即可。
我先是写了一个线段树版本的kdtree,然后两下半就写完了(雾其实我是懒得写正常的kdtree),然后居然直接rank1。。。。。。真是的随便构个数据就能卡飞了。。。
然后补了一下正常的kdtree。

Code

/**************************************************************
    Problem: 4154
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:448 ms
    Memory:8412 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 100010
int n,c,q,ans,et,la[N],fa[N],son[N],siz[N],top[N],dfn,dep[N],pos[N],L[N],R[N],x,y,f,g,C;
struct E{int to,nxt;}e[N];
#define adde(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
void dfs(int x){
    son[x]=0,siz[x]=1,dep[x]=dep[fa[x]]+1;
    for(int i=la[x];i;i=e[i].nxt){
        dfs(e[i].to),siz[x]+=siz[e[i].to];
        if(siz[son[x]]<siz[e[i].to])son[x]=e[i].to;
    }
}
void dfs2(int x,int tp){
    top[x]=tp,pos[L[x]=++dfn]=x;
    if(son[x])dfs2(son[x],tp);
    for(int i=la[x];i;i=e[i].nxt)
    if(e[i].to!=son[x])dfs2(e[i].to,e[i].to);
    R[x]=dfn;
}
int y0[1<<18],y1[1<<18],col[1<<18];
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
void bt(int o,int l,int r){
    if(l==r){y0[o]=y1[o]=dep[pos[l]],col[o]=1;return;}
    int mid=l+r>>1;
    bt(o<<1,l,mid),bt(o<<1|1,mid+1,r);
    y0[o]=min(y0[o<<1],y0[o<<1|1]),
    y1[o]=max(y1[o<<1],y1[o<<1|1]);
}
#define pd(o) if(col[o])col[o<<1]=col[o<<1|1]=col[o],col[o]=0
int getcol(int o,int l,int r){
    if(l==r)return col[o];
    int mid=l+r>>1;pd(o);
    if(x<=mid)return getcol(o<<1,l,mid);
    else return getcol(o<<1|1,mid+1,r);
}
void upd(int o,int l,int r){
    if(x<=l&&r<=y){
        if(f<=y0[o]&&y1[o]<=g)col[o]=C;
        else if(l!=r){
            int mid=l+r>>1;pd(o);
            if(f<=y1[o<<1]&&y0[o<<1]<=g)upd(o<<1,l,mid);
            if(f<=y1[o<<1|1]&&y0[o<<1|1]<=g)upd(o<<1|1,mid+1,r);
        }
    }else{
        int mid=l+r>>1;pd(o);
        if(x<=mid)upd(o<<1,l,mid);
        if(mid<y)upd(o<<1|1,mid+1,r);
    }
}
int main(){
    for(int _=F();_--;printf("%d\n",ans)){
        n=F(),c=F(),q=F(),ans=et=dfn=0,memset(la,0,sizeof(la)),memset(col,0,sizeof(col));
        for(int i=2;i<=n;i++)fa[i]=F(),adde(fa[i],i);
        dfs(1),dfs2(1,1);bt(1,1,n);
/*      for(int i=1;i<=n;i++)printf("i=%d (%d,%d)\n",i,L[i],dep[i]);*/
        for(int i=1,a,l,c;i<=q;i++){
            a=F(),l=F(),c=F();
            if(!c)x=L[a],ans=(ans+1LL*i*getcol(1,1,n))%1000000007;
            else x=L[a],y=R[a],f=dep[a],g=dep[a]+l,C=c,upd(1,1,n);
        }
    }
}
/**************************************************************
    Problem: 4154
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1544 ms
    Memory:16996 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 100010
int n,c,q,ans,et,la[N],fa[N],dfn,dep[N],L[N],R[N],id[N],x,y,f,g,root,D,s[N];
struct E{int to,nxt;}e[N];
#define adde(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
void dfs(int x){
    dep[x]=dep[fa[x]]+1,L[x]=++dfn;
    for(int i=la[x];i;i=e[i].nxt)dfs(e[i].to);
    R[x]=dfn;
}
struct P{int d[2],id;}p[N];
bool operator<(const P&a,const P&b){return a.d[D]<b.d[D];}
struct T{int f,s[2],d[2],x[2],y[2],col,tag;}t[1<<18];
#define cmin(a,b) (a>b?a=b:1)
#define cmax(a,b) (a<b?a=b:1)
#define ls t[o].s[0]
#define rs t[o].s[1]
#define mt(o,s) (cmin(t[o].x[0],t[s].x[0]),cmax(t[o].x[1],t[s].x[1]),cmin(t[o].y[0],t[s].y[0]),cmax(t[o].y[1],t[s].y[1]))
int bt(int l,int r){
    int o=l+r>>1;D=rand()&1;std::nth_element(p+l,p+o,p+r+1);
    t[o].col=1,t[o].tag=0,id[p[o].id]=o,t[o].f=0;
    t[o].d[0]=t[o].x[0]=t[o].x[1]=p[o].d[0];
    t[o].d[1]=t[o].y[0]=t[o].y[1]=p[o].d[1];
    if(l<o)ls=bt(l,o-1),mt(o,ls),t[ls].f=o;else ls=0;
    if(o<r)rs=bt(o+1,r),mt(o,rs),t[rs].f=o;else rs=0;
    return o;
}
#define pd(o) if(t[o].tag){if(t[o].s[0])t[t[o].s[0]].tag=t[t[o].s[0]].col=t[o].tag;if(t[o].s[1])t[t[o].s[1]].tag=t[t[o].s[1]].col=t[o].tag;t[o].tag=0;}
inline int getcol(register int x){
    int top=0;
    for(;x;x=t[x].f)s[++top]=x;
    for(;top;top--)pd(s[top]);
    return t[s[1]].col;
}
inline void upd(register int o){
    if(y<t[o].x[0]||t[o].x[1]<x||g<t[o].y[0]||t[o].y[1]<f)return;pd(o);
    if(x<=t[o].x[0]&&t[o].x[1]<=y&&f<=t[o].y[0]&&t[o].y[1]<=g){t[o].col=t[o].tag=c;return;}
    if(x<=t[o].d[0]&&t[o].d[0]<=y&&f<=t[o].d[1]&&t[o].d[1]<=g)t[o].col=c;
    if(ls)upd(ls);if(rs)upd(rs);
}
int main(){
    for(int _=F();_--;printf("%d\n",ans)){
        n=F(),c=F(),q=F(),ans=et=dfn=0,memset(la,0,sizeof(la));
        for(int i=2;i<=n;i++)fa[i]=F(),adde(fa[i],i);
        dfs(1);
        for(int i=1;i<=n;i++)p[i].d[0]=L[i],p[i].d[1]=dep[i],p[i].id=i;
        root=bt(1,n);
        for(int i=1,a,l;i<=q;i++)
        if(a=F(),l=F(),c=F(),!c)ans=(ans+1LL*i*getcol(id[a]))%1000000007;
        else x=L[a],y=R[a],f=dep[a],g=dep[a]+l,upd(root);
    }
}

  评论这张
 
阅读(575)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018