本题有一个弱化版本:GDKOI2016魔卡少女

弱化版大致题意是:询问一个区间的子区间异或和。具体方法是拆开二进制的每一位,然后用线段树维护异或前缀和中 0,1 的个数,个数相乘后再加权即为答案。这样正确的原因是:对于一个有贡献的区间 [L,R],它一定会被 sum[L-1]sum[R] 算到且仅一次。

然后这题只要把序列的问题搬到树链剖分上就行了,细节处理比较多(而且麻烦)。

代码:

#include<bits/stdc++.h>
#define mid ((L+R)>>1)
#define lc (id<<1)
#define rc (td<<1|1)
typedef long long LL;

using namespace std;

const int maxk=10,maxn=3e4+5;

struct edge {
    int obj,len;
    edge *Next;
}e[maxn<<1];

struct data {
    int sum,num0,num1;
}tree[maxk][maxn<<2];

edge *head[maxn];
int cur=-1;

data zero;

int fa[maxn],dep[maxn],Son[maxn],Size[maxn];
int Top[maxn],dfsx[maxn],dfn[maxn],Time=0;
int val[maxn],n,q;

inline void Add(int x,int y,int z) {
    ++cur;
    e[cur].obj=y;
    e[cur].len=z;
    e[cur].Next=head[x];
    head[x]=e+cur;
    return ;
}

inline void Dfs1(int node) {
    Size[node]=1;
    for (edge *p=head[node];p;p=p->Next) {
        int son=p->obj;
        if(son==fa[node])
            continue;
        fa[son]=node;
        val[son]=p->len;
        dep[son]=dep[node]+1;
        Dfs1(son);
        Size[node]+=Size[son];
        if(Size[son]>Size[Son[node]])
            Son[node]=son;
    }
    return ;
}

inline void Dfs2(int node) {
    dfsx[++Time]=node;
    dfn[node]=Time;
    if(Son[node])
        Top[Son[node]]=Top[node],Dfs2(Son[node]);
    for (edge *p=head[node];p;p=p->Next) {
        int son=p->obj;
        if(son==fa[node] || son==Son[node])
            continue;
        Top[son]=son;
        Dfs2(son);
    }
    return ;
}

inline data Up(data x,data y) {
    data z;
    z.sum=x.sum^y.sum;
    if(x.sum)
        swap(y.num0,y.num1);
    z.num0=x.num0+y.num0;
    z.num1=x.num1+y.num1;
    return z;
}

inline void Build(int i,int id,int L,int R) {
    if(L==R) {
        int v=((bool)(val[ dfsx[L] ]&(1<<i)));
        tree[i][id].sum=v;
        if(v)
            ++tree[i][id].num1;
        else
            ++tree[i][id].num0;
        return ;
    }
    Build(i,lc,L,mid);
    Build(i,rc,mid+1,R);
    tree[i][id]=Up(tree[i][lc],tree[i][rc]);
    return ;
}

inline int Lca(int u,int v) {
    if(Top[u]==Top[v])
        return dfsx[min(dfn[u],dfn[v])];
    if(dep[Top[u]]<dep[Top[v]])
        swap(u,v);
    return Lca(fa[Top[u]],v);
}

inline data Query(int i,int id,int L,int R,int x,int y) {
    if(y<L || R<x)
        return zero;
    if(x<=L && R<=y)
        return tree[i][id];
    data vl=Query(i,lc,L,mid,x,y);
    data vr=Query(i,rc,mid+1,R,x,y);
    return Up(vl,vr);
}

inline data Get(int i,int u,int v) {
    data x;
    if(u==v)
        x=zero;
    else
        x=Query(i,1,1,n,dfn[v]+1,dfn[u]);
    ++x.num0;
    if(x.sum)
        swap(x.num0,x.num1);
    return x;
}

inline data Work(int i,int u,int v) {
    if(Top[u]==Top[v])
        return Get(i,u,v);
    int w=Top[u];
    data y=Work(i,fa[w],v);
    if(val[w]&(1<<i))
        swap(y.num0,y.num1),y.sum^=1;
    data x=Get(i,u,w);
    return Up(x,y);
}

inline LL Query(int u,int v) {
    int w=Lca(u,v);
    LL ans=0;
    for(int i=0;i<maxk;++i) {
        data x=Work(i,u,w);
        data y=Work(i,v,w);
        if(y.sum)
            swap(y.num0,y.num1);
        --y.num0;
        x=Up(x,y);
        ans+=( (1LL<<i)*(long long)x.num0*(long long)x.num1 );
    }
    return ans;
}

inline void Update(int i,int id,int L,int R,int x) {
    if(L==x && x==R) {
        tree[i][id]=zero;
        int v=((bool)(val[ dfsx[L] ]&(1<<i)));
        tree[i][id].sum=v;
        if(v)
            ++tree[i][id].num1;
        else
            ++tree[i][id].num0;
        return ;
    }
    if(x<L || R<x)
        return ;
    Update(i,lc,L,mid,x);
    Update(i,rc,mid+1,R,x);
    tree[i][id]=Up(tree[i][lc],tree[i][rc]);
    return ;
}

int main() {
#ifdef
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
#endif
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)
        head[i]=NULL;
    for(int i=1;i<n;++i) {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        Add(x,y,z);
        Add(y,x,z);
    }
    dep[1]=1;
    Dfs1(1);
    Top[1]=1;
    Dfs2(1);
    for(int i=0;i<maxk;++i)
        Build(i,1,1,n);
    zero.sum=zero.num0=zero.num1=0;
    while(q--) {
        int x,u,v,w;
        scanf("%d%d%d",&x,&u,&v);
        if(x==1)
            printf("%lld\n",Query(u,v));
        else {
            scanf("%d",&w);
            if(fa[u]!=v)
                swap(u,v);
            val[u]=w;
            for(int i=0;i<maxk;++i)
                Update(i,1,1,n,dfn[u]);
        }
    }
    return 0;
}
Categories: OI

0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *