T1 A
题面
思路
先离线。
然后方法就很多了，比如记忆化和带权并查集
代码
//这是个记忆化搜索
//吾日八省吾身：
//输入多而不快读乎？
//题目标注而不freopen乎？
//乘除并列先乘后除乎？
//不手撕样例直接写代码乎？
//不仔细读题直接关页面乎？
//1e9而不开long long乎？
//Ctrl+V而不改名称乎？（papaw!!!）
//相信评测神机乎？
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<utility>
#include<deque>
#include<ctime>
#include<sstream>
#include<list>
#include<bitset>
using namespace std;
typedef long long ll;
const ll MAXN(1000233);
inline ll R(){
ll x=0,f=1;char c='c';
while(c>'9'||c<'0'){
c=getchar();
f=f*(c=='-'?-1:1);
}
while(c<='9'&&c>='0'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
struct edge{
ll to,nxt,val;
}ed[MAXN];
ll head[MAXN],cnt,ans[MAXN],ces[MAXN],cece[MAXN],tot,pos[MAXN];
ll n,m,opt,a,x,y;
ll valv[MAXN];
ll rev[MAXN],tov[MAXN];
inline void add(ll fr,ll to,ll v){
ed[++cnt].to=to;
ed[cnt].val=v;
ed[cnt].nxt=head[fr];
head[fr]=cnt;
return;
}
ll guagua;
ll DFS(ll now,ll ccccc){
ll res=valv[now];
if(tov[now]){
res=rev[now];
now=tov[now];
}
ll ha=valv[now];
bool hava=true;
for(ll i=head[now];i;i=ed[i].nxt)
if(ccccc>=ed[i].val){
ll uuuuu=DFS(ed[i].to,ccccc);
res^=uuuuu,ha^=uuuuu,hava=false;
}
if(hava) guagua=now;
rev[now]=ha;
tov[now]=guagua;
return res;
}
int main(){
n=R();m=R();
for(ll i=1;i<=n;++i){
a=R();
valv[i]=a;
}
for(ll i=1;i<=m;++i){
opt=R();
if(opt==1){
x=R();y=R();
add(x,y,i);
}
else{
x=R();
ces[++tot]=x;
cece[tot]=i;
pos[tot]=x;
}
}
for(ll i=1;i<=tot;++i){
ans[i]=DFS(ces[i],cece[i]);
printf("%lld\n",ans[i]);
}
return 0;
}