Dragonest @ 2020-01-26 00:48:32
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef unsigned long long ll;
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;
};
struct tree{
node t[maxn<<3][2];//0?????,1?????
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
void pushup(int p){
t[p][0].f0=((t[ls(p)][0].f0&t[rs(p)][0].f1)|((~t[ls(p)][0].f0)&t[rs(p)][0].f0));
t[p][0].f1=((t[ls(p)][0].f1&t[rs(p)][0].f1)|((~t[ls(p)][0].f1)&t[rs(p)][0].f0));
t[p][1].f0=((t[rs(p)][1].f0&t[ls(p)][1].f1)|((~t[rs(p)][1].f0)&t[ls(p)][1].f0));
t[p][1].f1=((t[rs(p)][1].f1&t[ls(p)][1].f1)|((~t[rs(p)][1].f1)&t[ls(p)][1].f0));
}
void build(int p,int l,int r)
{
if(l==r){
t[p][1].f0=t[p][0].f0=opt(0,sw[l],val[l]);
t[p][1].f1=t[p][0].f1=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,int k,int op)
{
if(l==r){
val[l]=k;
sw[l]=op;
t[p][1].f0=t[p][0].f0=opt(0,sw[l],val[l]);
t[p][1].f1=t[p][0].f1=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,int tow){
if(x<=l&&y>=r){
return t[p][tow];
}
int mid=((l+r)>>1);
node r1,r2;
if(x<=mid)r1=get_sum(x,y,ls(p),l,mid,tow);
if(y>mid)r2=get_sum(x,y,rs(p),mid+1,r,tow);
if(x<=mid&&y>mid){
node ss;
if(!tow){
ss.f0=((r1.f0&r2.f1)|((~r1.f0)&r2.f0));
ss.f1=((r1.f1&r2.f1)|((~r1.f1)&r2.f0));
}
else{
ss.f0=((r2.f0&r1.f1)|((~r2.f0)&r1.f0));
ss.f1=((r2.f1&r1.f1)|((~r2.f1)&r1.f0));
}
return ss;
}
else{
if(x<=mid)return r1;
else return r2;
}
}
node q_sum(int x,int y)
{
node res[2],tmp,ans;
bool b1=0,b2=0;
int n1=1,n2=0;
while(Top[x]!=Top[y]){
if(dep[Top[x]]<dep[Top[y]]){
swap(x,y);
swap(n1,n2);
}
tmp=get_sum(id[Top[x]],id[x],1,1,n,n1);
if(n1){
if(!b1){
res[0]=tmp;
b1=1;
}
else{
res[0].f0=((res[0].f0&tmp.f1)|((~res[0].f0)&tmp.f0));
res[0].f1=((res[0].f1&tmp.f1)|((~res[0].f1)&tmp.f0));
}
}
else{
if(!b2){
res[1]=tmp;
b2=1;
}
else{
res[1].f0=((tmp.f0&res[1].f1)|((~tmp.f0)&res[1].f0));
res[1].f1=((tmp.f1&res[1].f1)|((~tmp.f1)&res[1].f0));
}
}
x=f[Top[x]];
}
if(dep[x]>dep[y]){
swap(x,y);
}
tmp=get_sum(id[x],id[y],1,1,n,);
if((!b1)&&(!b2))return tmp;
if(n1){
if(!b1){
res[0]=tmp;
b1=1;
}
else{
res[0].f0=((res[0].f0&tmp.f1)|((~res[0].f0)&tmp.f0));
res[0].f1=((res[0].f1&tmp.f1)|((~res[0].f1)&tmp.f0));
}
}
else{
if(!b2){
res[1]=tmp;
b2=1;
}
else{
res[1].f0=((tmp.f0&res[1].f1)|((~tmp.f0)&res[1].f0));
res[1].f1=((tmp.f1&res[1].f1)|((~tmp.f1)&res[1].f0));
}
}
if(!b1)return res[1];
if(!b2)return res[0];
ans.f0=((res[0].f0&res[1].f1)|((~res[0].f0)&res[1].f0));
ans.f1=((res[0].f1&res[1].f1)|((~res[0].f1)&res[1].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()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
int i,j;
for(i=1;i<=n;i++)
{
cin>>s[i]>>v[i];
}
for(i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs1(1,0);
dfs2(1,0,1);
tr.build(1,1,n);
while(m--){
int q,x,y,z;
cin>>q>>x>>y>>z;
switch(q){
case 1:{
node res=tr.q_sum(x,y);
ll ans=0,tmp=0;
for(i=k-1;i>=0;i--){
if((res.f0>>i)&1){
ans+=(1LL<<i);
continue;
}
if((res.f1>>i)&1){
if(tmp+(1LL<<i)<=z){
tmp+=(1LL<<i);
ans+=(1LL<<i);
continue;
}
}
}
printf("%llu\n",ans);
break;
}
case 2:{
tr.ins(id[x],1,1,n,z,y);
break;
}
}
}
return 0;
}
by Dragonest @ 2020-01-26 00:48:59
代码可读性可能较差
by noip @ 2020-01-26 01:35:12
我谔谔
by impuk @ 2020-01-26 09:43:28
惊现lxl！！
by Dragonest @ 2020-01-26 11:46:22
最有可能升天的点是q_sum中当x与y位于同一条链上的拼接处理但是我想不出来怎么改
by Dragonest @ 2020-01-29 00:21:22
换了种写法依然WA0…… 自闭了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef unsigned long long ll;
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,int k,int 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);
ans1[++cnt1]=get_sum(id[x],id[y],1,1,n);
}
else ans2[++cnt2]=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)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()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
int i,j;
for(i=1;i<=n;i++)
{
cin>>s[i]>>v[i];
}
for(i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs1(1,0);
dfs2(1,0,1);
tr.build(1,1,n);
while(m--){
int q,x,y,z;
cin>>q>>x>>y>>z;
switch(q){
case 1:{
node res=tr.q_sum(x,y);
ll ans=0,tmp=0;
for(i=k-1;i>=0;i--){
if((res.f0>>i)&1){
ans+=(1LL<<i);
continue;
}
if((res.f1>>i)&1){
if(tmp+(1LL<<i)<=z){
tmp+=(1LL<<i);
ans+=(1LL<<i);
continue;
}
}
}
cout<<ans<<endl;
break;
}
case 2:{
tr.ins(id[x],1,1,n,z,y);
break;
}
}
}
return 0;
}by Dragonest @ 2020-01-29 00:44:07
注：靠全开ull捞到40分。
by Dragonest @ 2020-01-29 02:30:22
已通过，AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef unsigned long long ll;
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);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
int i,j;
for(i=1;i<=n;i++)
{
cin>>s[i]>>v[i];
}
for(i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
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;
cin>>q>>x>>y>>z;
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;
}错误全在q_sum中。 我真是个渣渣
by Spasmodic @ 2020-03-13 10:42:27
%%%
by 风之影音 @ 2020-03-26 14:32:30
永远不要怀疑洛谷的评测机