woj4675 神经信号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
#define mid ((T[root].l+T[root].r)>>1)
#define lc (root<<1)
#define rc (root<<1|1)
#define int unsigned int
using namespace std;
const int maxn=1e5+10,Log=32,lim=~0;
int Head[maxn],Next[maxn<<1],V[maxn<<1],cnt=0;
int n,m,l,r,u,v,limit,op[maxn],val[maxn],a;char s[3];
int dfn[maxn],t[maxn],son[maxn],fa[maxn],dep[maxn],siz[maxn],top[maxn],tot=0;
struct node{
	int val[2];node(){}
	node(char op,int VAL){
		switch(op){
			case '&':val[0]=0&VAL,val[1]=lim&VAL;break;
			case '|':val[0]=0|VAL,val[1]=lim|VAL;break;
			case '^':val[0]=0^VAL,val[1]=lim^VAL;break;
		}
	}
	friend inline node operator+(const node &a,const node &b){
		node t;
		t.val[0]=(a.val[0]&b.val[1])|(~a.val[0]&b.val[0]);
		t.val[1]=(a.val[1]&b.val[1])|(~a.val[1]&b.val[0]);
		return t;
	}
}ans;
struct sgtnode{int l,r;node cl,cr;}T[maxn<<2];
inline int get(int i,int VAL){return ((VAL?ans.val[1]:ans.val[0])>>i)&1;}
inline void add(int u,int v){Next[++cnt]=Head[u],V[cnt]=v,Head[u]=cnt;}
inline int read(){
	int x=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x;
}
inline void pushup(int root){
	T[root].cl=T[lc].cl+T[rc].cl;
	T[root].cr=T[rc].cr+T[lc].cr;
}
inline void build(int root,int l,int r){
	T[root].l=l,T[root].r=r;
	if(l==r){T[root].cr=T[root].cl=node(op[t[l]],val[t[l]]);return;}
	build(lc,l,mid),build(rc,mid+1,r),pushup(root);
}
inline node query_l(int root,int l,int r){
	if(l<=T[root].l&&T[root].r<=r) return T[root].cl;
	if(l> mid) return query_l(rc,l,r);
	if(r<=mid) return query_l(lc,l,r);
	return query_l(lc,l,mid)+query_l(rc,mid+1,r);
}
inline node query_r(int root,int l,int r){
	if(l<=T[root].l&&T[root].r<=r) return T[root].cr;
	if(l> mid) return query_r(rc,l,r);
	if(r<=mid) return query_r(lc,l,r);
	return query_r(rc,mid+1,r)+query_r(lc,l,mid);
}
inline void update(int root,int pos){
	if(T[root].l==T[root].r){T[root].cr=T[root].cl=node(op[t[pos]],val[t[pos]]);return;}
	(pos<=mid)?update(lc,pos):update(rc,pos),pushup(root);
}
inline void dfs1(int u){
	siz[u]=1,son[u]=0;
	for(int i=Head[u];i;i=Next[i]){
		dep[V[i]]=dep[u]+1,dfs1(V[i]),siz[u]+=siz[V[i]];
		if(siz[V[i]]>siz[son[u]]) son[u]=V[i];
	}
}
inline void dfs2(int u,int tp){
	top[u]=tp,t[dfn[u]=++tot]=u;
	if(son[u]) dfs2(son[u],tp);
	for(int i=Head[u];i;i=Next[i])
		if(V[i]!=son[u]) dfs2(V[i],V[i]);
}

//无上限 
inline int go_l(int i){
	if(!~i) return 0;
	if(get(i,1)>=get(i,0)){
		if(!((l>>i)&1)) return (get(i,1)<<i)|((ans.val[0]|ans.val[1])&((1u<<i)-1));
		else return (get(i,1)<<i)|go_l(i-1);
	}else if(!((l>>i)&1)) return go_l(i-1)|(1u<<i);
	else return go_l(i-1);
}

//无下限 
inline int go_r(int i){
	if(!~i) return 0;
	if(get(i,0)>=get(i,1)){
		if((r>>i)&1) return (get(i,0)<<i)|((ans.val[0]|ans.val[1])&((1u<<i)-1));
		else return (get(i,0)<<i)|go_r(i-1);
	}else if((r>>i)&1) return go_r(i-1)|(1u<<i);
	else return go_r(i-1);
}
inline void get_ans(int u,int v){
	node L=node('|',0),R=node('|',0);
	while(top[u]!=top[v]){
		(dep[top[u]]>dep[top[v]])?
		(L=L+query_r(1,dfn[top[u]],dfn[u]),u=fa[top[u]]):
		(R=query_l(1,dfn[top[v]],dfn[v])+R,v=fa[top[v]]);
	}(dep[u]>dep[v])?(L=L+query_r(1,dfn[v],dfn[u])):(R=query_l(1,dfn[u],dfn[v])+R);
	ans=L+R;
}
inline int query(int l,int r,int ret=0){
	for(int i=Log-1;i>=0;--i){
		int L=(l>>i)&1,R=(r>>i)&1;
		if(L==R){ret|=(get(i,L)<<i);continue;}
		if(get(i,L)==get(i,R)) ret|=(get(i,L)<<i)|(max(go_l(i-1),go_r(i-1)));
		else{(get(i,L)>get(i,R))?ret|=go_l(i):ret|=go_r(i);}
		break;
	}return ret;
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i) scanf("%s",s),op[i]=s[0],val[i]=read();
	for(int i=2;i<=n;++i) fa[i]=read(),add(fa[i],i);dfs1(1),dfs2(1,1),build(1,1,n);
	while(m--){
		scanf("%s",s);
		if(s[0]=='Q') u=read(),v=read(),l=read(),r=read(),get_ans(u,v),printf("%un",query(l,r));
		if(s[0]=='C') u=read(),scanf("%s",s),a=read(),val[u]=a,op[u]=s[0],update(1,dfn[u]);
	}
}