ZJT's Blog

大変に気分がいい~

[自选题 #142] 简单树题

2018-1-7 18:552018-1-7 18:55
集训队作业自选题kd-tree点分治

传送门

一开始直接想歪了,想到点分那边去了。。。接着就发现这tm要维护二维平面啊,这不是得写kd树吗。然后就很脑抽的写了一个点分树套kd树。。。估计这题用了kd树的就我这个zz。。。

考虑动态点分治,每次改边权,对于点分树到根路径上的每个点,都会影响一整棵子树。子树的话肯定用dfs序处理,但是这题的询问区间是跟原编号相关的。所以我们就对点分树上的每个节点维护一棵kd树,维护对应的所有点组成的关于原编号和dfs序的二维平面。这样一次操作的复杂度就是$O(\sqrt n)+O(\sqrt{n/2})+O(\sqrt{n/4})+\cdots=O(\sqrt{n})$,所以总复杂度就是$O(m\sqrt n)$啦。

然而这题正解好像是$O(m\sqrt n\log n)$的。。。然后我的根号做法竟然还被碾了(大概是因为kd树常数过于玄学),一直TLE卡不过去。最后把同一份代码反复交了22次之后竟然过了,刚好用完所有提交机会,分数在80~100之间随机。。。tuoj怕是真实土豆评测机。。。

#include <bits/stdc++.h>
#define MAXN 70010
#define LL long long
using namespace std;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

struct edge{
    int to,next,w;
    edge(int _to=0,int _next=0,int _w=0):to(_to),next(_next),w(_w){}
}e[MAXN<<1];

int n,m,type;
int g[MAXN],nume;
int size[MAXN],maxs[MAXN],pre[MAXN];
int e2[MAXN][3];
int w[MAXN][20][3],w2[MAXN][20][2],ls[MAXN];
bool visit[MAXN];
int root,sums;
int debug=0;

struct KDTree{
    int n,root;
    int *xmin,*xmax,*ymin,*ymax,*px,*py,*lc,*rc,*size,*pre;
    LL *tag,*s,*v;
    int sz;
    static int p[MAXN],nump;
    static int w[MAXN][2],numw;
    static LL v0[MAXN];

    static bool cmpx(int x,int y){ return x<y; }
    static bool cmpy(int x,int y){ return w[x][0]<w[y][0]; }

    void dfs(int x,int pre){
        ::w[x][++ls[x]][0]=w[x][0]=++numw;
        p[++nump]=x;
        for(int i=g[x];~i;i=e[i].next)
            if(!visit[e[i].to] && e[i].to!=pre){
                v0[e[i].to]=v0[x]+e[i].w;
                dfs(e[i].to,x);
            }
        ::w[x][ls[x]][1]=w[x][1]=numw;
    }

    void dfs2(int x,int p,int t1,int t2){
        ::w2[x][ls[x]][0]=t1;
        ::w2[x][ls[x]][1]=t2;
        for(int i=g[x];~i;i=e[i].next)
            if(!visit[e[i].to] && e[i].to!=p)
                dfs2(e[i].to,x,t1,t2);
    }

    int build(int l,int r,int d){
        if(l>r) return 0;
        int mid=(l+r)>>1;
        if(d==0) nth_element(p+l,p+mid,p+r+1,cmpx);
        else nth_element(p+l,p+mid,p+r+1,cmpy);
        int x=++sz;
        ::w[p[mid]][ls[p[mid]]][2]=x;
        xmin[x]=xmax[x]=px[x]=p[mid]; ymin[x]=ymax[x]=py[x]=w[p[mid]][0];
        lc[x]=build(l,mid-1,d^1);
        rc[x]=build(mid+1,r,d^1);
        if(lc[x]){
            xmin[x]=min(xmin[x],xmin[lc[x]]);
            ymin[x]=min(ymin[x],ymin[lc[x]]);
            xmax[x]=max(xmax[x],xmax[lc[x]]);
            ymax[x]=max(ymax[x],ymax[lc[x]]);
        }
        if(rc[x]){
            xmin[x]=min(xmin[x],xmin[rc[x]]);
            ymin[x]=min(ymin[x],ymin[rc[x]]);
            xmax[x]=max(xmax[x],xmax[rc[x]]);
            ymax[x]=max(ymax[x],ymax[rc[x]]);
        }
        v[x]=v0[p[mid]];
        size[x]=1+size[lc[x]]+size[rc[x]];
        s[x]=v[x]+s[lc[x]]+s[rc[x]];
        if(lc[x]) pre[lc[x]]=x;
        if(rc[x]) pre[rc[x]]=x;
        return x;
    }

    void pushdown(int x){
        if(!tag[x]) return;
        if(lc[x]){
            tag[lc[x]]+=tag[x];
            v[lc[x]]+=tag[x];
            s[lc[x]]+=tag[x]*size[lc[x]];
        }
        if(rc[x]){
            tag[rc[x]]+=tag[x];
            v[rc[x]]+=tag[x];
            s[rc[x]]+=tag[x]*size[rc[x]];
        }
        tag[x]=0;
    }

    void modify(int x,int y1,int y2,LL dv){
        if(y1<=ymin[x] && y2>=ymax[x]){
            tag[x]+=dv;
            s[x]+=dv*size[x];
            v[x]+=dv;
            return;
        }
        pushdown(x);
        if(y1<=py[x] && y2>=py[x]) v[x]+=dv;
        if(lc[x] && y1<=ymax[lc[x]] && y2>=ymin[lc[x]])
            modify(lc[x],y1,y2,dv);
        if(rc[x] && y1<=ymax[rc[x]] && y2>=ymin[rc[x]])
            modify(rc[x],y1,y2,dv);
        s[x]=v[x]+s[lc[x]]+s[rc[x]];
    }

    void query(int x,int x1,int x2,int y1,int y2,LL &res1,int &res2){
        if(!x || x1>xmax[x] || x2<xmin[x] || y1>ymax[x] || y2<ymin[x]) return;
        if(x1<=xmin[x] && x2>=xmax[x] && y1<=ymin[x] && y2>=ymax[x]){
            res1+=s[x],res2+=size[x];
            return;
        }
        pushdown(x);
        if(x1<=px[x] && x2>=px[x] && y1<=py[x] && y2>=py[x]) res1+=v[x],res2++;
        query(lc[x],x1,x2,y1,y2,res1,res2);
        query(rc[x],x1,x2,y1,y2,res1,res2);
    }

    LL getV(int x){
        LL res=v[x];
        for(x=pre[x];x;x=pre[x]) res+=tag[x];
        return res;
    }

    void init(int _n,int _root){
        n=_n;
        xmin=new int[n+1];
        xmax=new int[n+1];
        ymin=new int[n+1];
        ymax=new int[n+1];
        px=new int[n+1];
        py=new int[n+1];
        lc=new int[n+1];
        rc=new int[n+1];
        size=new int[n+1];
        pre=new int[n+1];
        tag=new LL[n+1];
        s=new LL[n+1];
        v=new LL[n+1];
        for(int i=0;i<=n;i++) s[i]=v[i]=tag[i]=0;
        size[0]=0;
        nump=numw=0;
        v0[_root]=0;
        dfs(_root,0);
        for(int i=g[_root];~i;i=e[i].next)
            if(!visit[e[i].to])
                dfs2(e[i].to,_root,w[e[i].to][0],w[e[i].to][1]);
        root=build(1,n,1);
    }
}a[MAXN];

int KDTree::p[MAXN],KDTree::nump;
int KDTree::w[MAXN][2],KDTree::numw;
LL KDTree::v0[MAXN];

void addEdge(int u,int v,int w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
}

void findRoot(int x,int p){
    size[x]=1; maxs[x]=0;
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to] && e[i].to!=p){
            findRoot(e[i].to,x);
            size[x]+=size[e[i].to];
            if(size[e[i].to]>maxs[x]) maxs[x]=size[e[i].to];
        }
    if(sums-size[x]>maxs[x]) maxs[x]=sums-size[x];
    if(maxs[x]<maxs[root]) root=x;
}

void build(int x){
    visit[x]=1;
    findRoot(x,0);
    a[x].init(sums,x);
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to]){
            root=0; sums=size[e[i].to];
            findRoot(e[i].to,0);
            pre[root]=x;
            build(root);
        }
}

void modify(int eid,int v){
    int y=e2[eid][1],x=e2[eid][0];
    int lx=ls[x],ly=ls[y];
    int tx=x,ty=y;
    while(ls[ty]>ls[tx]) ty=pre[ty],ly--;
    while(ls[ty]<ls[tx]) tx=pre[tx],lx--;
    while(tx!=ty) tx=pre[tx],ty=pre[ty],lx--,ly--;
    for(;tx;tx=pre[tx],lx--,ly--){
        if(w[x][lx][0]<w[y][ly][0]) swap(x,y);
        a[tx].modify(1,w[x][lx][0],w[x][lx][1],v-e2[eid][2]);
    }
    e2[eid][2]=v;
}

LL query(int x,int l,int r){
    LL res=0;
    int zjtsb;
    a[x].query(1,l,r,1,a[x].n,res,zjtsb);
    int cl=ls[x]-1;
    for(int y=pre[x];y;y=pre[y],cl--){
        int p1=w2[x][cl][0],p2=w2[x][cl][1],res2=0;
        LL res1=0,temp=0;
        a[y].query(1,l,r,1,p1-1,res1,res2);
        if(p2<a[y].n) a[y].query(1,l,r,p2+1,a[y].n,res1,res2);
        temp=a[y].getV(w[x][cl][2]);
        res+=res1+res2*temp;
    }
    return res;
}

int main(){
#ifdef DEBUG
    freopen("142.in","r",stdin);
    freopen("142.out","w",stdout);
#endif
    memset(g,-1,sizeof g);
    maxs[0]=0x7FFFFFFF;
    scanf("%d%d%d",&n,&m,&type);
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        e2[i][0]=u; e2[i][1]=v; e2[i][2]=w;
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    root=0; sums=n;
    findRoot(1,0);
    build(root);
    LL lastans=0;
    while(m--){
        char c;
        while((c=getchar())!='q' && c!='m');
        if(c=='q'){
            int l=read(),r=read(),x=read();
            if(type) l^=lastans,r^=lastans,x^=lastans;
            printf("%lld\n",lastans=query(x,l,r));
            lastans%=n;
        }else{
            int x=read(),y=read();
            if(type) x^=lastans,y^=lastans;
            modify(x,y);
        }
    }
    return 0;
}

查看详细内容

[自选题 #111] 资源采集

2018-1-5 15:182018-1-5 15:18
集训队作业自选题kd-tree

传送门

这题北京集训的时候做过。。。

大概就是先按dfs序和深度把每个点表示在一个二维平面上,然后一个询问覆盖到的点就是一个矩形内的点。我们把这些点的KD树建出来,这样每次询问覆盖到的节点数量就是$O(\sqrt n)$级别的。操作之后的节点我们可以打上标记,然后如果一次询问中发现子树里面存在之前的标记,就暴力搜索下去,把标记都清除,并更新答案。这样每添加一个标记,最多会花费$O(\log n)$的时间去清除它(这个log是KD树的树高)。所以总复杂度就是$O(n\sqrt n\log n)$的。相信KD树常数很小的话就能过啦!

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
#define LL long long
#define MAXN 100010
using namespace std;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9')
        res=res*10+c-'0';
    return res;
}

struct edge{
    int to,next;
    LL w;
    edge(int _to=0,int _next=0,LL _w=0):to(_to),next(_next),w(_w){}
}e[MAXN<<1];

int n,m;
int w[MAXN][2],numw=0;
int g[MAXN],nume=0;
LL v[MAXN],lim[MAXN],d[MAXN];
LL q[MAXN][3];
int p[MAXN];

int debug=0;

namespace SegTree{
    struct node{
        LL s1,s2;
        int lc,rc;
    }a[7000000];

    int size;
    LL sizew;

    void init(){
        size=0;
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++)
            sizew=max(sizew,(lim[i]-1)/v[i]+1);
    }

    int create(int l,int r,int p,LL v1,LL v2){
        int x=++size;
        a[x].s1=v1;
        a[x].s2=v2;
        if(l==r) return x;
        int mid=(l+r)>>1;
        if(p<=mid) a[x].lc=create(l,mid,p,v1,v2);
        else a[x].rc=create(mid+1,r,p,v1,v2);
        return x;
    }

    int join(int x,int y){
        if(!x) return y;
        if(!y) return x;
        int z=++size;
        a[z].s1=a[x].s1+a[y].s1;
        a[z].s2=a[x].s2+a[y].s2;
        a[z].lc=join(a[x].lc,a[y].lc);
        a[z].rc=join(a[x].rc,a[y].rc);
        return z;
    }

    LL getS1(int x,int l,int r,int cl,int cr){
        if(l<=cl && cr<=r) return a[x].s1;
        int mid=(cl+cr)>>1;
        LL res=0;
        if(l<=mid)
            res+=getS1(a[x].lc,l,r,cl,mid);
        if(r>mid)
            res+=getS1(a[x].rc,l,r,mid+1,cr);
        return res;
    }

    LL getS2(int x,int l,int r,int cl,int cr){
        if(l<=cl && cr<=r) return a[x].s2;
        int mid=(cl+cr)>>1;
        LL res=0;
        if(l<=mid)
            res+=getS2(a[x].lc,l,r,cl,mid);
        if(r>mid)
            res+=getS2(a[x].rc,l,r,mid+1,cr);
        return res;
    }
}

namespace KD_Tree{
    struct point{
        int id;
        LL x,y;
        LL t1,t2,t3;
    }p[MAXN];

    bool cmpx(point x,point y){ return x.x<y.x; }
    bool cmpy(point x,point y){ return x.y<y.y; }

    struct node{
        int lc,rc,p,l,r;
        int seg_root;
        bool tag;
        LL delta_t;
        LL minx,maxx,miny,maxy;
    }a[MAXN<<1];

    int size;
    LL total_delta_t;

    int build(int l,int r,int d){
        if(!d)
            sort(p+l,p+r+1,cmpx);
        else
            sort(p+l,p+r+1,cmpy);
        int x=++size;
        a[x].l=l;
        a[x].r=r;
        a[x].minx=a[x].maxx=p[l].x;
        a[x].miny=a[x].maxy=p[l].y;
        for(int i=l+1;i<=r;i++){
            if(p[i].x<a[x].minx) a[x].minx=p[i].x;
            if(p[i].x>a[x].maxx) a[x].maxx=p[i].x;
            if(p[i].y<a[x].miny) a[x].miny=p[i].y;
            if(p[i].y>a[x].maxy) a[x].maxy=p[i].y;
        }
        if(l==r){
            p[l].t1=(lim[p[l].id]-1)/v[p[l].id]+1;
            p[l].t2=lim[p[l].id];
            p[l].t3=v[p[l].id];
            a[x].seg_root=SegTree::create(1,SegTree::sizew,p[l].t1,p[l].t2,p[l].t3);
            return x;
        }
        int mid=(l+r)>>1;
        a[x].lc=build(l,mid,d^1);
        a[a[x].lc].p=x;
        a[x].rc=build(mid+1,r,d^1);
        a[a[x].rc].p=x;
        a[x].seg_root=SegTree::join(a[a[x].lc].seg_root,a[a[x].rc].seg_root);
        return x;
    }

    void init(){
        SegTree::init();
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++)
            p[i].x=w[i][0],p[i].y=d[i],p[i].id=i;
        size=0;
        build(1,n,0);
        a[1].p=0;
        total_delta_t=0;
    }

    bool collide(int x,LL minx,LL miny,LL maxx,LL maxy){
        if(minx>a[x].maxx) return 0;
        if(miny>a[x].maxy) return 0;
        if(maxx<a[x].minx) return 0;
        if(maxy<a[x].miny) return 0;
        return 1;
    }

    bool contain(int x,LL minx,LL miny,LL maxx,LL maxy){
        if(minx>a[x].minx) return 0;
        if(miny>a[x].miny) return 0;
        if(maxx<a[x].maxx) return 0;
        if(maxy<a[x].maxy) return 0;
        return 1;
    }

    LL query(int x,LL t){
        if(a[x].r-a[x].l+1<=70){
            LL res=0;
            for(int i=a[x].l;i<=a[x].r;i++)
                res+=(p[i].t1<=t)?(p[i].t2):(p[i].t3*t);
            return res;
        }
        LL res=0;
        if(t)
            res+=SegTree::getS1(a[x].seg_root,1,t,1,SegTree::sizew);
        if(t<SegTree::sizew)
            res+=SegTree::getS2(a[x].seg_root,t+1,SegTree::sizew,1,SegTree::sizew)*t;
        return res;
    }

    LL res_gao;

    void dfs(int x){
        a[x].tag=0;
        if(a[x].delta_t){
            res_gao-=query(x,total_delta_t);
            res_gao+=query(x,total_delta_t+a[x].delta_t);
            a[x].delta_t=0;
        }else{
            if(a[a[x].lc].tag) dfs(a[x].lc);
            if(a[a[x].rc].tag) dfs(a[x].rc);
        }
    }

    LL gao(int x){
        res_gao=query(x,total_delta_t);
        if(a[x].tag)
            dfs(x);
        a[x].delta_t=-total_delta_t;
        a[x].tag=1;
        if(a[x].p && !a[a[x].p].tag){
            for(int i=a[x].p;i;i=a[i].p)
                a[i].tag=1;
        }
        return res_gao;
    }

    void pushdown(int x){
        if(!a[x].delta_t) return;
        a[a[x].lc].tag=1;
        a[a[x].rc].tag=1;
        a[a[x].lc].delta_t=a[x].delta_t;
        a[a[x].rc].delta_t=a[x].delta_t;
        a[x].delta_t=0;
    }

    LL gao(int x,LL minx,LL miny,LL maxx,LL maxy){
        if(!collide(x,minx,miny,maxx,maxy)) return 0;
        if(contain(x,minx,miny,maxx,maxy)) return gao(x);
        pushdown(x);
        LL res=0;
        if(a[x].lc) res+=gao(a[x].lc,minx,miny,maxx,maxy);
        if(a[x].rc) res+=gao(a[x].rc,minx,miny,maxx,maxy);
        return res;
    }
}

void addEdge(int u,int v,LL w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
}

void dfs(int x,int p){
    w[x][0]=++numw;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            d[e[i].to]=d[x]+e[i].w;
            dfs(e[i].to,x);
        }
    w[x][1]=numw;
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("C.in","r",stdin);
    #endif
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        v[i]=read();
    for(int i=1;i<=n;i++)
        lim[i]=read();
    d[1]=d[0]=0;
    for(int i=2;i<=n;i++){
        p[i]=read();
        d[i]=read();
        addEdge(p[i],i,d[i]);
    }
    dfs(1,0);
    KD_Tree::init();
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        q[i][0]=read();
        q[i][1]=read();
        q[i][2]=read();
    }
    for(int i=1;i<=m;i++){
        KD_Tree::total_delta_t=q[i][0];
        printf("%lld\n", KD_Tree::gao(1,w[q[i][1]][0],d[q[i][1]],w[q[i][1]][1],d[q[i][1]]+q[i][2]));
    }
    return 0;
}

查看详细内容