的梗来自于Yveh在SDWC2018上的课件

 

线段树背今晚的大锅

在这里再说一点轶事,据说集训队大爷WZD神犇出过一道带八个操作的LCT

Exciting.

还有我成功拿到了4k的长度,代码更加高清了。

//牺牲一些长度换易读性吧 反正手速快。[滑稽

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<iterator>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

struct Segment_Tree { int l,r,lazy_tag,w; }SGT[400010]={0};
struct ed { int pre,to; }edge[200010]={0};
int nodenum,rootx,opt,modx,fx,tx,at=1,pointer[100010]={0};
int nodev[100010]={0},lx,rx,val,oopt;

int nnv[100010]={0},topx[100010]={0},dfn[100010]={0};
int hson[100010]={0},tsize[100010]={0},depth[100010]={0},anc[100010]={0};
int tstamp=0;

inline void readx(int& x)
{
    x=0; int k=1; register char ch=0;
    while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

inline void Insert()
{
    edge[at].pre=pointer[fx];
    edge[at].to=tx;
    pointer[fx]=at;
    at++;
    edge[at].pre=pointer[tx];
    edge[at].to=fx;
    pointer[tx]=at;
    at++;
}

inline void Fancy(int nownode,int nowdep,int fa)
{
    depth[nownode]=nowdep; tsize[nownode]=1; anc[nownode]=fa;
    int prex=pointer[nownode];
    while (prex)
    {
        if (edge[prex].to!=fa)
        {
            Fancy(edge[prex].to,nowdep+1,nownode);
            tsize[nownode]+=tsize[edge[prex].to];
            if (tsize[edge[prex].to]>tsize[hson[nownode]]) hson[nownode]=edge[prex].to;
        }
        prex=edge[prex].pre;
    }
}

inline void Dreams(int nownode,int src)
{
    dfn[nownode]=++tstamp; topx[nownode]=src; nnv[tstamp]=nodev[nownode]%modx;
    if (hson[nownode]) Dreams(hson[nownode],src);
    int prex=pointer[nownode];
    while (prex)
    {
        if (edge[prex].to!=anc[nownode] && edge[prex].to!=hson[nownode]) Dreams(edge[prex].to,edge[prex].to);
        prex=edge[prex].pre;
    }
}

inline void BuildTree(int leftx,int rightx,int inx)
{
    SGT[inx].l=leftx; SGT[inx].r=rightx;
    if (leftx==rightx) { SGT[inx].w=nnv[leftx]; return; }
    int mid=(leftx+rightx)>>1;
    BuildTree(leftx,mid,inx<<1);
    BuildTree(mid+1,rightx,inx<<1|1);
    SGT[inx].w=(SGT[inx<<1].w+SGT[inx<<1|1].w)%modx;
}

inline void pushdown(int inx)
{
    SGT[inx<<1].lazy_tag+=SGT[inx].lazy_tag; SGT[inx<<1].lazy_tag%=modx;
    SGT[inx<<1|1].lazy_tag+=SGT[inx].lazy_tag; SGT[inx<<1|1].lazy_tag%=modx;
    SGT[inx<<1].w+=(SGT[inx<<1].r-SGT[inx<<1].l+1)*SGT[inx].lazy_tag; SGT[inx<<1].w%=modx;
    SGT[inx<<1|1].w+=(SGT[inx<<1|1].r-SGT[inx<<1|1].l+1)*SGT[inx].lazy_tag; SGT[inx<<1|1].w%=modx;
    SGT[inx].lazy_tag=0;
}

inline void update(int inx)
{
    if (SGT[inx].l>=lx && SGT[inx].r<=rx)
    {
        SGT[inx].w+=val*(SGT[inx].r-SGT[inx].l+1); SGT[inx].w%=modx;
        SGT[inx].lazy_tag+=val; SGT[inx].lazy_tag%=modx;
        return;
    }
    if (SGT[inx].lazy_tag) pushdown(inx);
    int mid=(SGT[inx].l+SGT[inx].r)>>1;
    if (lx<=mid) update(inx<<1);
    if (rx>mid) update(inx<<1|1);
    SGT[inx].w=(SGT[inx<<1].w+SGT[inx<<1|1].w)%modx;
}

inline int query(int inx)
{
    if (SGT[inx].l>=lx && SGT[inx].r<=rx) return SGT[inx].w;
    if (SGT[inx].lazy_tag) pushdown(inx);
    int mid=(SGT[inx].l+SGT[inx].r)>>1,ret=0;
    if (mid>=lx) ret=(ret+query(inx<<1))%modx;
    if (mid<rx) ret=(ret+query(inx<<1|1))%modx;
    return ret;
}

inline int solve_range(int u,int v)
{
    int ans=0;
    while (topx[u]!=topx[v])
    {
        if (depth[topx[u]]<depth[topx[v]]) swap(u,v);
        lx=dfn[topx[u]]; rx=dfn[u];
        ans+=query(1); ans%=modx;
        u=anc[topx[u]];
    }
    if (depth[u]<depth[v]) swap(u,v);
    lx=dfn[v]; rx=dfn[u];
    ans+=query(1);
    return ans%modx;
}

inline void upd_range(int u,int v)
{
    while (topx[u]!=topx[v])
    {
        if (depth[topx[u]]<depth[topx[v]]) swap(u,v);
        lx=dfn[topx[u]]; rx=dfn[u]; update(1);
        u=anc[topx[u]];
    }
    if (depth[u]<depth[v]) swap(u,v);
    lx=dfn[v]; rx=dfn[u];
    update(1);
}

inline int solve_subt(int u)
{
    lx=dfn[u]; rx=dfn[u]+tsize[u]-1;
    int ans=query(1);
    return ans%modx;
}

inline void upd_subt(int u)
{
    lx=dfn[u]; rx=dfn[u]+tsize[u]-1;
    update(1);
}

int main()
{
    readx(nodenum); readx(opt); readx(rootx); readx(modx);
    for (int i=1;i<=nodenum;i++) readx(nodev[i]);
    for (int i=1;i<nodenum;i++) { readx(fx); readx(tx); Insert(); }
    
    Fancy(rootx,1,-1);
    Dreams(rootx,rootx);
    BuildTree(1,tstamp,1);
    
    int ux,vx;
    for (int i=1;i<=opt;i++)
    {
        readx(oopt);
        if (oopt==1) { readx(ux); readx(vx); readx(val); upd_range(ux,vx); }
        else if (oopt==2) { readx(ux); readx(vx); printf("%d\n",solve_range(ux,vx)); }
        else if (oopt==3) { readx(ux); readx(val); upd_subt(ux); }
        else { readx(ux); printf("%d\n",solve_subt(ux)); }
    }
    return 0;
}

没错这就是洛谷的板子题.

分类: 树剖

发表评论

电子邮件地址不会被公开。 必填项已用*标注