Loading...

洛谷P4592 [TJOI2018]异或

check评论:0 条 remove_red_eye浏览量:382 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-04-07

啊...树上差分题目

可以看另外一道$counting on a tree$,很类似了

数组开小我调了1h,我是zz

#include <bits/stdc++.h>
using namespace std;
#define maxn 200010
int n,m,in[maxn],si[maxn],out[maxn];
int c[maxn],head[maxn],cnt,fa[maxn],son[maxn],top[maxn],dep[maxn],seg[maxn];
struct trie
{
    int ch[maxn<<5][2],siz[maxn<<5],t[maxn];
    void ins(int &rt,int pre,int x)
    {
        rt=++cnt;
        int prt=rt;
        siz[prt]=siz[pre]+1;
        for(int i=30;i>=0;i--)
        {
            int qaq=(x>>i)&1;
            ch[prt][qaq]=++cnt,ch[prt][qaq^1]=ch[pre][qaq^1];
            prt=ch[prt][qaq],pre=ch[pre][qaq];
            siz[prt]=siz[pre]+1;
        }
    }
    int qtree(int lf,int rg,int x)
    {
        int ans=0;
        for(int i=30;i>=0;i--)
        {
            int qwq=(x>>i)&1;
            if(ch[rg][qwq^1]-ch[lf][qwq^1]>0)
            {
                ans|=(1<<i);
                rg=ch[rg][qwq^1],lf=ch[lf][qwq^1];
            }
            else
            {
                rg=ch[rg][qwq],lf=ch[lf][qwq];
            }
        }
        return ans;
    }
    int qlink(int lf,int rg,int l,int r,int x)
    {
        int ans=0;
        for(int i=30;i>=0;i--)
        {
            int qwq=(x>>i)&1;
            if(ch[rg][qwq^1]+ch[lf][qwq^1]-ch[r][qwq^1]-ch[l][qwq^1]>0)
            {
                ans|=(1<<i);
                rg=ch[rg][qwq^1],lf=ch[lf][qwq^1];
                r=ch[r][qwq^1],l=ch[l][qwq^1];
            }
            else
            {
                rg=ch[rg][qwq],lf=ch[lf][qwq];
                r=ch[r][qwq],l=ch[l][qwq];
            }
        }
        return ans;
    }
}tr1,tr2;
struct edge
{
    int next,to;
}e[maxn<<1];
void add(int u,int v)
{
    head[0]++;
    e[head[0]].to=v;
    e[head[0]].next=head[u];
    head[u]=head[0];
}
void dfs(int u)
{
    si[u]=1;
    tr1.ins(tr1.t[u],tr1.t[fa[u]],c[u]);
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u])
        {
            continue;
        }
        fa[v]=u;
        dep[v]=dep[u]+1; 
        dfs(v);
        si[u]+=si[v];
        if(si[v]>si[son[u]])
        {
            son[u]=v;
        }
    }
}
void dfss(int u,int f)
{
    in[u]=++cnt;
    seg[cnt]=u;
    top[u]=f;
    if(son[u])
    {
        dfss(son[u],f);
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u]||v==son[u])
        {
            continue;
        }
        dfss(v,v);
    }
    out[u]=cnt;
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        {
            swap(x,y);
        }
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }
    return y;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    cnt=0;
    dfs(1);
    cnt=0;
    dfss(1,0);
    tr2.ins(tr2.t[0],tr2.t[0],0);
    for(int i=1;i<=n;i++)
    {
        tr2.ins(tr2.t[i],tr2.t[i-1],c[seg[i]]);
    }
    for(int i=1;i<=m;i++)
    {
        int opt,l,r,x;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1)
        {
            printf("%d\n",tr2.qtree(tr2.t[in[l]-1],tr2.t[out[l]],r));
        }
        else
        {
            scanf("%d",&x);
            int qwq=lca(l,r);
            printf("%d\n",tr1.qlink(tr1.t[l],tr1.t[r],tr1.t[qwq],tr1.t[fa[qwq]],x));
        }
    } 
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名