洛谷 P5354 [Ynoi2017]由乃的OJ

调了好几天，感觉题号已经刻进DNA里了……
等等这是签到题？

先把代码放了，找时间写题解

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef unsigned long long ll;
char *p1,*p2,buf[1<<20];
//#define GC (p1==p2&&(p1=buf,p2=buf+fread(buf,1,1<<20,stdin),p1==p2)?0:(*(p1++)))
#define GC getchar()
inline ll ll_in(){
    ll x=0;
    int w=0;
    char ch=0;
    while(!isdigit(ch)){
        w|=ch=='-';
        ch=GC;
    }
    while(isdigit(ch)){
        x=(x<<3ull)+(x<<1ull)+(ll)(ch^48ull);
        ch=GC;
    }
    return w? -x:x;
}
inline int int_in()
{
    int x=0;
    int w=0;
    char ch=0;
    while(!isdigit(ch)){
        w|=ch=='-';
        ch=GC;
    }
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=GC;
    }
    return w? -x:x;
}
const int maxn=100010;
const ll inf=0-1;
struct edge{
    int next,to;
}g[2*maxn];
int head[maxn],cnt;
void add(int from,int to)
{
    g[++cnt].next=head[from];
    g[cnt].to=to;
    head[from]=cnt;
}
ll opt(ll a,int act,ll b)
{
    switch(act){
        case 1:{
            a=(a&b);
            break;
        }
        case 2:{
            a=(a|b);
            break;
        }
        case 3:{
            a=(a^b);
            break;
        }
    }
    return a;
}
int Top[maxn],Size[maxn],id[maxn],zson[maxn];
ll val[maxn],v[maxn];
int sw[maxn],s[maxn];
int dep[maxn],f[maxn];
int num=0;
int n,m,k;
struct node{
    ll f0,f1;
    ll fx0,fx1;
};
struct tree{
    node t[maxn<<3];//0?????,1?????
    inline int ls(int x){return x<<1;}
    inline int rs(int x){return x<<1|1;}
    node update(node l,node r){
        node res;
        res.f0=((l.f0&r.f1)|((~l.f0)&r.f0));
        res.f1=((l.f1&r.f1)|((~l.f1)&r.f0));
        res.fx0=((r.fx0&l.fx1)|((~r.fx0)&l.fx0));
        res.fx1=((r.fx1&l.fx1)|((~r.fx1)&l.fx0));
        return res;
    }
    void pushup(int p){
        t[p]=update(t[ls(p)],t[rs(p)]);
    }
    void build(int p,int l,int r)
    {
        if(l==r){
            t[p].f0=t[p].fx0=opt(0,sw[l],val[l]);
            t[p].f1=t[p].fx1=opt(inf,sw[l],val[l]);
            return;
        }
        int mid=((l+r)>>1);
        build(ls(p),l,mid);
        build(rs(p),mid+1,r);
        pushup(p);
    }
    void ins(int x,int p,int l,int r,ll k,ll op)
    {
        if(l==r){
            val[l]=k;
            sw[l]=op;
            t[p].f0=t[p].fx0=opt(0,sw[l],val[l]);
            t[p].f1=t[p].fx1=opt(inf,sw[l],val[l]);
            return;
        }
        int mid=((l+r)>>1);
        if(x<=mid)ins(x,ls(p),l,mid,k,op);
        else ins(x,rs(p),mid+1,r,k,op);
        pushup(p);
    }
    node get_sum(int x,int y,int p,int l,int r){
        if(x<=l&&y>=r){
            return t[p];
        }
        int mid=((l+r)>>1);
        node r1,r2;
        if(x<=mid)r1=get_sum(x,y,ls(p),l,mid);
        if(y>mid)r2=get_sum(x,y,rs(p),mid+1,r);
        if(x<=mid&&y>mid){
            node r;
            r=update(r1,r2);
            return r;
        }
        else{
            if(x<=mid)return r1;
            else return r2;
        }
    }
    node ans1[maxn],ans2[maxn];
    int cnt1,cnt2;
    node q_sum(int x,int y)
    {
        cnt1=cnt2=0;
        node ans;
        while(Top[x]!=Top[y]){
            if(dep[Top[x]]<dep[Top[y]]){
                ans1[++cnt1]=get_sum(id[Top[y]],id[y],1,1,n);
                y=f[Top[y]];
            }
            else{
                ans2[++cnt2]=get_sum(id[Top[x]],id[x],1,1,n);
                x=f[Top[x]];
            }
        }
        if(dep[x]>dep[y]){
            swap(x,y);
            ans2[++cnt2]=get_sum(id[x],id[y],1,1,n);
        }
        else ans1[++cnt1]=get_sum(id[x],id[y],1,1,n);
        node r1,r2;
        r1=ans1[cnt1],r2=ans2[1];
        int i;
        for(i=cnt1-1;i>0;i--)r1=update(r1,ans1[i]);
        for(i=2;i<=cnt2;i++)r2=update(ans2[i],r2);
        if(cnt2==0)return r1;
        if(cnt1==0){
            swap(r2.f0,r2.fx0);
            swap(r2.f1,r2.fx1);
            return r2;
        }
        ans.f0=((r2.fx0&r1.f1)|((~r2.fx0)&r1.f0));
        ans.f1=((r2.fx1&r1.f1)|((~r2.fx1)&r1.f0));
        return ans;
    }
}tr;
void dfs1(int x,int fr)
{
    dep[x]=dep[fr]+1;
    f[x]=fr;
    Size[x]=1;
    int _max=0;
    for(int i=head[x];i;i=g[i].next)
    {
        int v=g[i].to;
        if(v==fr)continue;
        dfs1(v,x);
        Size[x]+=Size[v];
        if(Size[v]>_max){
            zson[x]=v;
            _max=Size[v];
        }
    }
}
void dfs2(int x,int fr,int top)
{
    Top[x]=top;
    id[x]=++num;
    sw[num]=s[x];
    val[num]=v[x];
    if(!zson[x])return;
    dfs2(zson[x],x,top);
    for(int i=head[x];i;i=g[i].next){
        int v=g[i].to;
        if(v==fr||v==zson[x])continue;
        dfs2(v,x,v);
    }
}
int main()
{
    // freopen("test.in","r",stdin);
    // freopen("my.out","w",stdout);
    n=int_in();m=int_in();k=int_in();
    int i,j;
    for(i=1;i<=n;i++)
    {
        s[i]=int_in();
        v[i]=ll_in();
    }
    for(i=1;i<n;i++)
    {
        int a,b;
        a=int_in();b=int_in();
        add(a,b);
        add(b,a);
    }
    dfs1(1,0);
    dfs2(1,0,1);
    tr.build(1,1,n);
    ll sb=1;
    while(m--){
        ll q,x,y,z;
        q=ll_in();x=ll_in();y=ll_in();z=ll_in();
        switch(q){
            case 1:{
                node res=tr.q_sum(x,y);
                ll ans=0,tmp=0;
                for(i=63;i>=0;i--){
                    if((res.f0>>i)&1ull){
                        ans+=(1ull<<i);
                        continue;
                    }
                    if((res.f1>>i)&1ull){
                        if(tmp+(1ull<<i)<=z){
                            tmp+=(1ull<<i);
                            ans+=(1ull<<i);
                            continue;
                        }
                    }
                }
                cout<<ans<<endl;
                break;
            }
            case 2:{
                tr.ins(id[x],1,1,n,z,y);
                break;
            }
        }
    }
    return 0;
}

洛谷 P5354 [Ynoi2017]由乃的OJ

原文：https://www.cnblogs.com/cooper233/p/12239506.html