BZOJ 3159: 决战解题报告

2023-12-19 22:08:09

BZOJ 3159: 决战

1 sec 512MB

题意：

给你一颗\(n\)个点，初始点权为\(0\)的有跟树，要求支持

Increase x y w 将路径\(x\)到\(y\)所有点点权加上\(w\)
Sum x y 询问路径\(x\)到\(y\)的点权和
Major x y 询问从路径\(x\)到\(y\)最大点权
Minor x y 询问最小点权
Invert x y 将路径上的点权翻转

有个性质，修改操作一定满足\(x\)为\(y\)祖先或者\(y\)为\(x\)祖先（实际没什么用处）

\(n\le 50000,|w|\le 1000\)

输入格式

第一行有三个整数\(N\)、\(M\)和\(R\)，分别表示树的节点数、指令和询问总数，以及树的跟。

接下来\(N-1\)行，每行两个整数\(u\)和\(v\)，表示一条边。

接下来\(M\)行，每行描述一个指令或询问，格式见题意描述。

输出格式

对于每个询问操作，输出所求的值。

老年菜鸡选手实在写不动大数据结构题...

有两个做法，暂时只写了一种，有可能一会儿会把另一种补充一下。

考虑树链剖分，但是不能维护翻转

考虑平衡树可以维护翻转

于是我们可以拿平衡树维护树剖的每条链

然后每次修改只有\(\log\)条链，我们把每条链要修改的地方拎出来，然后塞到一个平衡树里面，打一个翻转tag，再塞回去就可以了

用fhqtreap实现起来比较方便

说起来蛮简单，写起来还是蛮难受的的

Code:

#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#define ll long long
const int SIZE=1<<21;
char ibuf[SIZE],*iS,*iT;
//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)
#define gc() getchar()
template <class T>
void read(T &x)
{
    int f=0;x=0;char c=gc();
    while(!isdigit(c)) f|=c=='-',c=gc();
    while(isdigit(c)) x=x*10+c-'0',c=gc();
    if(f) x=-x;
}
void reads(char *s)
{
    int k=0;char c=gc();
    while(c<'A'||c>'Z') c=gc();
    while((c>='a'&&c<='z')||(c>='A'&&c<='Z')) s[k++]=c,c=gc();
}
const int N=5e4+10;
inline void ckmax(int &x,int y){x=x>y?x:y;}
inline void ckmin(int &x,int y){x=x<y?x:y;}
int n,m,r,root[N];
namespace treap
{
    int ch[N][2],mx[N],mi[N],siz[N],val[N],dat[N],tag[N],reve[N],tot;
    ll sum[N];
    #define ls ch[now][0]
    #define rs ch[now][1]
    void updata(int now)
    {
        sum[now]=sum[ls]+dat[now]+sum[rs];
        siz[now]=siz[ls]+1+siz[rs];
        mx[now]=mi[now]=dat[now];
        if(ls)
        {
            ckmax(mx[now],mx[ls]);
            ckmin(mi[now],mi[ls]);
        }
        if(rs)
        {
            ckmax(mx[now],mx[rs]);
            ckmin(mi[now],mi[rs]);
        }
    }
    void Reverse(int now)
    {
        std::swap(ls,rs),reve[now]^=1;
    }
    void upt(int now,int d)
    {
        dat[now]+=d;
        tag[now]+=d;
        mi[now]+=d;
        mx[now]+=d;
        sum[now]+=d*siz[now];
    }
    void pushdown(int now)
    {
        if(reve[now])
        {
            if(ls) Reverse(ls);
            if(rs) Reverse(rs);
            reve[now]=0;
        }
        if(tag[now])
        {
            if(ls) upt(ls,tag[now]);
            if(rs) upt(rs,tag[now]);
            tag[now]=0;
        }
    }
    void split(int now,int &x,int &y,int k)
    {
        if(!now){x=y=0;return;}
        pushdown(now);
        if(k<=siz[ls])
            y=now,split(ls,x,ch[y][0],k);
        else
            x=now,split(rs,ch[x][1],y,k-siz[ls]-1);
        updata(now);
    }
    int Merge(int x,int y)
    {
        if(!x||!y) return x^y;
        pushdown(x),pushdown(y);
        if(val[x]<val[y])
        {
            ch[x][1]=Merge(ch[x][1],y);
            updata(x);
            return x;
        }
        else
        {
            ch[y][0]=Merge(x,ch[y][0]);
            updata(y);
            return y;
        }
    }
    int New(int d)
    {
        val[++tot]=rand(),siz[tot]=1,sum[tot]=mi[tot]=mx[tot]=dat[tot]=d;
        return tot;
    }
    void ins(int id,int d)
    {
        root[id]=Merge(root[id],New(d));
    }
    ll querysum(int id,int l,int r)
    {
        int x,y,z;
        split(root[id],x,y,r);
        split(x,x,z,l-1);
        ll ret=sum[z];
        root[id]=Merge(x,Merge(z,y));
        return ret;
    }
    int querymi(int id,int l,int r)
    {
        int x,y,z;
        split(root[id],x,y,r);
        split(x,x,z,l-1);
        int ret=mi[z];
        root[id]=Merge(x,Merge(z,y));
        return ret;
    }
    int querymx(int id,int l,int r)
    {
        int x,y,z;
        split(root[id],x,y,r);
        split(x,x,z,l-1);
        int ret=mx[z];
        root[id]=Merge(x,Merge(z,y));
        return ret;
    }
    void modify(int id,int l,int r,int w)
    {
        int x,y,z;
        split(root[id],x,y,r);
        split(x,x,z,l-1);
        upt(z,w);
        root[id]=Merge(x,Merge(z,y));
    }
}
using treap::modify;
using treap::querysum;
using treap::querymi;
using treap::querymx;
using treap::ins;
using treap::Merge;
using treap::split;
using treap::Reverse;
int head[N],to[N<<1],Next[N<<1],cnt;
void add(int u,int v)
{
    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int top[N],ws[N],siz[N],par[N],dep[N],rk[N],num[N];
void dfs(int now)
{
    siz[now]=1;
    dep[now]=dep[par[now]]+1;
    for(int v,i=head[now];i;i=Next[i])
        if((v=to[i])!=par[now])
        {
            par[v]=now;
            dfs(v);
            siz[now]+=siz[v];
            if(siz[ws[now]]<siz[v]) ws[now]=v;
        }
}
int lin,tot[N];
void dfs(int now,int id,int anc)
{
    top[now]=anc;
    num[now]=id;
    rk[now]=++tot[id];
    ins(id,0);
    if(ws[now]) dfs(ws[now],id,anc);
    for(int v,i=head[now];i;i=Next[i])
        if(!num[v=to[i]])
            dfs(v,++lin,v);
}
void modi(int x,int y,int w)
{
    if(dep[x]<dep[y]) std::swap(x,y);
    while(top[x]!=top[y])
    {
        modify(num[x],1,rk[x],w);
        x=par[top[x]];
    }
    if(dep[x]<dep[y]) std::swap(x,y);
    modify(num[x],rk[y],rk[x],w);
}
void qrysum(int x,int y)
{
    ll ret=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]])
        {
            ret+=querysum(num[x],1,rk[x]);
            x=par[top[x]];
        }
        else
        {
            ret+=querysum(num[y],1,rk[y]);
            y=par[top[y]];
        }
    }
    if(dep[x]<dep[y]) std::swap(x,y);
    ret+=querysum(num[x],rk[y],rk[x]);
    printf("%lld\n",ret);
}
void qrymx(int x,int y)
{
    int ret=-(1<<30);
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]])
        {
            ckmax(ret,querymx(num[x],1,rk[x]));
            x=par[top[x]];
        }
        else
        {
            ckmax(ret,querymx(num[y],1,rk[y]));
            y=par[top[y]];
        }
    }
    if(dep[x]<dep[y]) std::swap(x,y);
    ckmax(ret,querymx(num[x],rk[y],rk[x]));
    printf("%d\n",ret);
}
void qrymi(int x,int y)
{
    int ret=1<<30;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]])
        {
            ckmin(ret,querymi(num[x],1,rk[x]));
            x=par[top[x]];
        }
        else
        {
            ckmin(ret,querymi(num[y],1,rk[y]));
            y=par[top[y]];
        }
    }
    if(dep[x]<dep[y]) std::swap(x,y);
    ckmin(ret,querymi(num[x],rk[y],rk[x]));
    printf("%d\n",ret);
}
void rev(int x,int y)
{
    int tx=x,ty=y;
    if(dep[x]<dep[y]) std::swap(x,y);
    int rt=0;
    while(top[x]!=top[y])
    {
        int id=num[x],k=rk[x],pre;
        split(root[id],pre,root[id],k);
        rt=Merge(pre,rt);
        x=par[top[x]];
    }
    if(dep[x]<dep[y]) std::swap(x,y);
    int id=num[x],l=rk[y],r=rk[x],a,b,c;
    split(root[id],a,c,r);
    split(a,a,b,l-1);
    rt=Merge(b,rt);
    Reverse(rt);
    x=tx,y=ty;
    if(dep[x]<dep[y]) std::swap(x,y);
    while(top[x]!=top[y])
    {
        int id=num[x],k=rk[x],pre;
        split(rt,rt,pre,treap::siz[rt]-k);
        root[id]=Merge(pre,root[id]);
        x=par[top[x]];
    }
    id=num[x];
    root[id]=Merge(a,Merge(rt,c));
}
int main()
{
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    read(n),read(m),read(r);
    for(int u,v,i=1;i<n;i++) read(u),read(v),add(u,v),add(v,u);
    dfs(r);
    dfs(r,++lin,r);
    char op[23];
    for(int x,y,w,i=1;i<=m;i++)
    {
        reads(op),read(x),read(y);
        if(op[0]=='I')
        {
            if(op[2]=='c') read(w),modi(x,y,w);
            else rev(x,y);
        }
        else if(op[0]=='S') qrysum(x,y);
        else
        {
            if(op[1]=='a') qrymx(x,y);
            else qrymi(x,y);
        }
    }
    return 0;
}

2019.5.22

码农公寓

BZOJ 3159: 决战

题意：

输入格式

输出格式

相关文章