头像

我已经不想再做刺客了




离线:20小时前


最近来访(486)
用户头像
X-7D1C11010
用户头像
njw1123
用户头像
meteor_04
用户头像
刷题家族组长-省赛加油
用户头像
老丰qwq
用户头像
hujiajia
用户头像
NNNNNNoBody
用户头像
大吉大利666
用户头像
OnLine_Set
用户头像
Sham_Devour
用户头像
HopeAc6.0
用户头像
RyanMoriarty
用户头像
WA_FOREVER
用户头像
liang302
用户头像
倒悬打Treap
用户头像
伯牙绝弦
用户头像
rd0
用户头像
11677
用户头像
dp好难
用户头像
su尔


#include<bits/stdc++.h>
using namespace std;
const int N=2200;
int a[N][N],n,m,r,c,x,y;
int o,ans[N][N];
struct node{
    int i,j,x,y;
};
deque<node>q;
int vis[N][N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>r>>c>>x>>y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            cin>>c;
            if(c=='*')a[i][j]=1;
        }
    }
    q.push_back({r,c,x,y});
    while(q.size()){
        auto t=q.front();
        q.pop_front();
        int i=t.i;
        int j=t.j;
        if(vis[i][j])continue;
        int x=t.x;
        int y=t.y;
        ans[i][j]=1;
        vis[i][j]=1;
        //cout<<"i="<<i<<" j="<<j<<'\n';
        //上下左右
        if(i-1>=1&&!a[i-1][j]&&!vis[i-1][j])q.push_front({i-1,j,x,y});
        if(i+1<=n&&!a[i+1][j]&&!vis[i+1][j])q.push_front({i+1,j,x,y});
        if(j-1>=1&&x&&!a[i][j-1]&&!vis[i][j-1])q.push_back({i,j-1,x-1,y});
        if(j+1<=m&&y&&!a[i][j+1]&&!vis[i][j+1])q.push_back({i,j+1,x,y-1});

    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            o+=ans[i][j];
        }
    }
    if(a[r][c])o--;
    cout<<o;
}



给定三个整数 p,q,b,请你计算十进制表示下的 p/q 的结果在 b 进制下是否为有限小数。

结论就是如果约分处理之后,q有的质因数如果b都有的话则YES

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,x,T;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>a>>b>>x;
        int d=__gcd(a,b);
        a/=d,b/=d;
        while(1){
            int t=__gcd(b,x);
            if(t==1){
                if(b!=1)cout<<"NO"<<'\n';
                if(b==1)cout<<"YES"<<'\n';
                break;
            }
            b/=t;
        }
    }
}



ACM2的作业题目
ZOJ真的烦,也看不到错误信息
自己写了个bfs居然在acwing上过了

#include<bits/stdc++.h>
using namespace std;
// map<string,int>mp;
unordered_map<string,string>op;
int xx[]={1,-1,0,0};
int yy[]={0,0,1,-1};
// char zz[]={'d','u','r','l'};
char zz[]={'u','d','l','r'};
string S;
string T="12345678x";
string f(char a[3][3]){
    string ans;
    for(int i=0;i<9;i++)ans+=a[i/3][i%3];
    return ans;
}
char a[3][3];
void bfs(string S){
    op[S]="";
    queue<string>q;
    q.push(S);
    int d=1000000;
    while(q.size()){
        string s=q.front();
        q.pop();
        //if(s==T)break;
        if(--d==0)break;

        int x,y,id;
        for(int i=0;i<9;i++){
            a[i/3][i%3]=s[i];
            if(s[i]=='x')x=i/3,y=i%3,id=i;
        }
        for(int k=3;k>=0;k--){
            int i=(k+2)%4;
            int tx=x+xx[i];
            int ty=y+yy[i];
            char tz=zz[i];
            int ti=tx*3+ty;
            if(tx<0||tx>=3||ty<0||ty>=3)continue;
            string t=s;
            swap(t[id],t[ti]);
            if(op.count(t))continue;
            op[t]=op[s]+tz;
            q.push(t);
        }
    }
}
signed main(){
    bfs(T);
    char j;
    while(cin>>j){
        S+=j;
        for(int i=1;i<9;i++){
            cin>>j;
            S+=j;
        }
        //cout<<"S="<<S<<endl;
        if(op.count(S)){
            string ans=op[S];
            reverse(ans.begin(),ans.end());
            cout<<ans;
        }
        else cout<<"unsolvable";
        //cout<<'\n';
        S="";
    }
}



线段树合并
对每个点开一个权值线段树
插在颜色上,维护max和sum这两个变量
不要直接#define int long long
要把需要的才开long long
不然还是会MLE

#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],idx;
int n,m,c[N],root[N],cnt;
long long ans[N];
struct node{
    int l,r;
    long long sum;//主要颜色的编号和
    int max;//出现最多颜色的次数
    #define ls tr[u].l
    #define rs tr[u].r
}tr[N*100];
void add(int a,int b){
    e[++idx]=b,ne[idx]=h[a],h[a]=idx;
}
void pushup(int u){
    tr[u].max=max(tr[ls].max,tr[rs].max);
    if(tr[ls].max==tr[rs].max)tr[u].sum=tr[ls].sum+tr[rs].sum;
    if(tr[ls].max >tr[rs].max)tr[u].sum=tr[ls].sum;
    if(tr[ls].max <tr[rs].max)tr[u].sum=tr[rs].sum;
}
void pushdown(int u){

}
void modify(int &o,int l,int r,int i,int k){
    if(!o)o=++cnt;
    if(l==r){
        tr[o].max=1;
        tr[o].sum=k;
        return;
    }
    int mid=l+r>>1;
    if(i<=mid)modify(tr[o].l,l,mid,i,k);
    else modify(tr[o].r,mid+1,r,i,k);
    pushup(o);
}
int merge(int a,int b,int l,int r){//线段树合并
    if(!a)return b;
    if(!b)return a;//哪个没有就返回另一个点的编号
    if(l==r){
        tr[a].max+=tr[b].max;
        return a;
    }
    int mid=l+r>>1;
    tr[a].l=merge(tr[a].l,tr[b].l,l,mid);//合并a,b的左儿子
    tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);//合并a,b的右儿子
    pushup(a);
    return a;
}
void cal(int u,int fa=0){
    for(int i=h[u];i;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        cal(j,u);
        root[u]=merge(root[u],root[j],1,n);
    }
    ans[u]=tr[root[u]].sum;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=n;i++)modify(root[i],1,n,c[i],c[i]);
    cal(1);
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}


活动打卡代码 AcWing 4280. 序列查询

#include<bits/stdc++.h>
using namespace std;
int n,k,x,ans;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    int pre;
    cin>>pre;
    for(int i=1;i<n;i++){
        cin>>x;

        ans+=(x-pre)*i;

        pre=x;
    }
    ans+=(k-pre)*n;
    cout<<ans;
}



将每一条边按照a从小到大枚举
化边为点
进而动态加边删边
如果1号点和n号点联通就更新答案
你要维护的是区间最大值还是最大值的编号?
答案是编号,因为只有这样,你才能split之后拿出来删边
注意一下删边时的编号映射,没了这道题就这样

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,p[N],stk[N];
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
struct Edge{
    int x,y,a,b;
    bool operator<(const Edge&t)const{
        return a<t.a;
    }
}e[N];
struct node{
    int s[2],p,v;
    int mx,rev;
    #define ls tr[u].s[0]
    #define rs tr[u].s[1]
    #define lx tr[x].s[0]
    #define rx tr[x].s[1]
}tr[N];
void pushrev(int u){
    swap(ls,rs);
    tr[u].rev^=1;
}
void pushup(int u){
    tr[u].mx=u;
    int lmaxid=tr[ls].mx;
    int rmaxid=tr[rs].mx;
    if(tr[lmaxid].v>tr[tr[u].mx].v)tr[u].mx=lmaxid;
    if(tr[rmaxid].v>tr[tr[u].mx].v)tr[u].mx=rmaxid;
}
void pushdown(int u){
    if(tr[u].rev){
        pushrev(ls);
        pushrev(rs);
        tr[u].rev=0;
    }
}
bool isroot(int u){
    return tr[tr[u].p].s[0]!=u&&tr[tr[u].p].s[1]!=u;
}
void rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void splay(int x){
    int top=0,r=x;
    stk[++top]=r;
    while(!isroot(r))stk[++top]=r=tr[r].p;
    while(top)pushdown(stk[top--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if((tr[z].s[1]==y)^(tr[y].s[1]==x))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x){
    int z=x;
    for(int y=0;x;y=x,x=tr[y].p){
        splay(x);
        tr[x].s[1]=y,pushup(x);
    }
    splay(z);
}
void makeroot(int x){
    access(x);
    pushrev(x);
}
int findroot(int x){
    access(x);
    while(lx)pushdown(x),x=lx;
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x);
    access(y);
}
void link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)tr[x].p=y;
}
void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
        tr[y].p=rx=0;
        pushup(x);
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,a,b;
        cin>>x>>y>>a>>b;
        e[i]={x,y,a,b};
    }
    sort(e+1,e+1+m);
    for(int i=1;i<=n+m;i++){
        p[i]=i;
        if(i>n)tr[i].v=e[i-n].b;
        tr[i].mx=i;
    }
    int ans=1e9;
    for(int i=1;i<=m;i++){
        int x=e[i].x,y=e[i].y,a=e[i].a,b=e[i].b;
        if(find(x)==find(y)){
            split(x,y);
            int t=tr[y].mx;
            if(tr[t].v>b){
                cut(t,e[t-n].x),cut(t,e[t-n].y);
                link(i+n,x),link(i+n,y);
            }
        }
        else{
            p[find(x)]=find(y);
            link(i+n,x),link(i+n,y);
        }
        if(find(1)==find(n)){
            split(1,n);
            ans=min(ans,a+tr[tr[n].mx].v);
        }
    }
    cout<<(ans==1e9?-1:ans);
}



因为A的要求所以这道题被要求强制在线
同时,因为会查询之前的节点信息,所以我们不能真的删掉节点
那么如何找到真正的节点编号呢
我们发现每一个增加的节点一定会被放在某一层里,而这某一层就是排名
而且查询和更新的链路径信息一定是第i名到第j名
至此,找什么链找哪条链就知道了
如何找到第s天第x名选手的节点编号呢
我们可以插入的时候把{第i天,节点编号}push_back进一个容器rank里面
找的时候就是去rank[x]里面找到符合条件的第一个,也就是第一个小于等于{s,0}的节点,也就是前驱
你二分也可以,lower_bound也可以
lct裸题

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rank _rank
const int N=1e6+10;
int m,p,T,A,cur,idx,op,s,l,r,x,dep[N],fa[N],y;
typedef pair<int,int>PII;
vector<PII>rank[N];
struct node{
    int s[2],p,v;
    int sum,rev,mul;
    #define ls tr[u].s[0]
    #define rs tr[u].s[1]
    #define lx tr[x].s[0]
    #define rx tr[x].s[1]
}tr[N];
bool isroot(int u){
    return tr[tr[u].p].s[0]!=u && tr[tr[u].p].s[1]!=u;
}
void pushup(int u){
    tr[u].sum=tr[u].v;
    if(ls)tr[u].sum+=tr[ls].sum;
    if(rs)tr[u].sum+=tr[rs].sum;
    tr[u].sum%=p;

}
void pushrev(int u){
    swap(ls,rs);
    tr[u].rev^=1;
}
void pushdown(int u){
    if(tr[u].rev){
        pushrev(ls);
        pushrev(rs);
        tr[u].rev=0;
    }
    if(tr[u].mul!=1){
        tr[ls].mul=tr[ls].mul*tr[u].mul %p;
        tr[ls].sum=tr[ls].sum*tr[u].mul %p;
        tr[ls].v=tr[ls].v*tr[u].mul %p;

        tr[rs].mul=tr[rs].mul*tr[u].mul %p;
        tr[rs].sum=tr[rs].sum*tr[u].mul %p;
        tr[rs].v=tr[rs].v*tr[u].mul %p;

        tr[u].mul=1;
    }
}
void rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void splay(int x){
    static int stk[N];
    int tt=0,t=x;
    stk[++tt]=t;
    while(!isroot(t))stk[++tt]=t=tr[t].p;
    while(tt)pushdown(stk[tt--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if((tr[z].s[1]==y)^(tr[y].s[1]==x))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x){ // 建立一条从根到x的路径,同时将x变成splay的根节点
    int z=x;
    for(int y=0;x;y=x,x=tr[x].p){
        splay(x);
        tr[x].s[1]=y,pushup(x);
    }
    splay(z);
}
void makeroot(int x){
    access(x);
    pushrev(x);
}
int findroot(int x){// 找到x所在原树的根节点, 再将原树的根节点旋转到splay的根节点
    access(x);
    while(lx)pushdown(x),x=lx;
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x);
    access(y);
}
void link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)tr[x].p=y;
}
void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
        tr[y].p=rx=0;
        pushup(x);
    }
}
int find(int s,int x){
    //去排名为x的节点里面找第一个小于等于s的节点编号
    int l=0,r=rank[x].size()-1;
    while(l<r){
        int mid=l+r+1>>1;
        if(rank[x][mid].first<=s)l=mid;
        else r=mid-1;
    }
    return rank[x][l].second;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>m>>p>>T;
    for(int i=1;i<=m;i++){
        cin>>op;
        if(op==1){
            cin>>x;
            if(T)x^=A;
            if(x>0){
                ++idx;
                tr[idx].v=tr[idx].sum=x;
                tr[idx].mul=1;
                if(cur)link(cur,idx);
                fa[idx]=cur,dep[idx]=dep[cur]+1;
                rank[dep[idx]].push_back({i,idx});
                cur=idx;
            }
            else cur=fa[cur];
        }
        else if(op==2){
            cin>>s>>l>>r>>y;
            if(T)y^=A;
            l=find(s,l);
            r=find(s,r);
            split(l,r);
            tr[r].v=tr[r].v*y%p;
            tr[r].sum=tr[r].sum*y%p;
            tr[r].mul=tr[r].mul*y%p;
        }
        else{
            cin>>s>>l>>r;
            l=find(s,l);
            r=find(s,r);
            split(l,r);
            cout<<tr[r].sum<<'\n';
            if(T)A=tr[r].sum;
        }
    }
}



#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rank _rank
const int N=1e6+10;
int m,p,T,A,cur,idx,op,s,l,r,x,dep[N],fa[N],y;
typedef pair<int,int>PII;
vector<PII>rank[N];
struct node{
    int s[2],p,v;
    int sum,rev,mul;
    #define ls tr[u].s[0]
    #define rs tr[u].s[1]
    #define lx tr[x].s[0]
    #define rx tr[x].s[1]
}tr[N];
bool isroot(int u){
    return tr[tr[u].p].s[0]!=u && tr[tr[u].p].s[1]!=u;
}
void pushup(int u){
    tr[u].sum=tr[u].v;
    if(ls)tr[u].sum+=tr[ls].sum;
    if(rs)tr[u].sum+=tr[rs].sum;
    tr[u].sum%=p;

}
void pushrev(int u){
    swap(ls,rs);
    tr[u].rev^=1;
}
void pushdown(int u){
    if(tr[u].rev){
        pushrev(ls);
        pushrev(rs);
        tr[u].rev=0;
    }
    if(tr[u].mul!=1){
        tr[ls].mul=tr[ls].mul*tr[u].mul %p;
        tr[ls].sum=tr[ls].sum*tr[u].mul %p;
        tr[ls].v=tr[ls].v*tr[u].mul %p;

        tr[rs].mul=tr[rs].mul*tr[u].mul %p;
        tr[rs].sum=tr[rs].sum*tr[u].mul %p;
        tr[rs].v=tr[rs].v*tr[u].mul %p;

        tr[u].mul=1;
    }
}
void rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void splay(int x){
    static int stk[N];
    int tt=0,t=x;
    stk[++tt]=t;
    while(!isroot(t))stk[++tt]=t=tr[t].p;
    while(tt)pushdown(stk[tt--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if((tr[z].s[1]==y)^(tr[y].s[1]==x))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x){ // 建立一条从根到x的路径,同时将x变成splay的根节点
    int z=x;
    for(int y=0;x;y=x,x=tr[x].p){
        splay(x);
        tr[x].s[1]=y,pushup(x);
    }
    splay(z);
}
void makeroot(int x){
    access(x);
    pushrev(x);
}
int findroot(int x){// 找到x所在原树的根节点, 再将原树的根节点旋转到splay的根节点
    access(x);
    while(lx)pushdown(x),x=lx;
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x);
    access(y);
}
void link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)tr[x].p=y;
}
void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
        tr[y].p=rx=0;
        pushup(x);
    }
}
int find(int s,int x){
    //去排名为x的节点里面找第一个小于等于s的节点编号
    int l=0,r=rank[x].size()-1;
    while(l<r){
        int mid=l+r+1>>1;
        if(rank[x][mid].first<=s)l=mid;
        else r=mid-1;
    }
    return rank[x][l].second;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>m>>p>>T;
    for(int i=1;i<=m;i++){
        cin>>op;
        if(op==1){
            cin>>x;
            if(T)x^=A;
            if(x>0){
                ++idx;
                tr[idx].v=tr[idx].sum=x;
                tr[idx].mul=1;
                if(cur)link(cur,idx);
                fa[idx]=cur,dep[idx]=dep[cur]+1;
                rank[dep[idx]].push_back({i,idx});
                cur=idx;
            }
            else cur=fa[cur];
        }
        else if(op==2){
            cin>>s>>l>>r>>y;
            if(T)y^=A;
            l=find(s,l);
            r=find(s,r);
            split(l,r);
            tr[r].v=tr[r].v*y%p;
            tr[r].sum=tr[r].sum*y%p;
            tr[r].mul=tr[r].mul*y%p;
        }
        else{
            cin>>s>>l>>r;
            l=find(s,l);
            r=find(s,r);
            split(l,r);
            cout<<tr[r].sum<<'\n';
            if(T)A=tr[r].sum;
        }
    }
}



#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int f[N][N],n,V,M;
int v,m,w;
signed main(){
    cin>>n>>V>>M;
    while(n--){
        cin>>v>>m>>w;
        for(int i=V;i>=v;i--){
            for(int j=M;j>=m;j--){
                f[i][j]=max(f[i][j],f[i-v][j-m]+w);
            }
        }
    }
    cout<<f[V][M];
}



关于动态树是什么?怎么实现?,铅笔大佬已经写的很nice了
这里简单记一下笔记

动态树难点
理解前驱后继与原树之间的关系
通过不断旋转,变换实链虚链来维护信息
赛场上,如何将问题转化成动态树,如何建树,如何将删边加边与要求一一等价对应才是难点

lct时间复杂度logn,树链剖分logn2

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

struct node{
    int s[2],p,v;
    int sum,rev;
    #define ls tr[u].s[0]
    #define lx tr[x].s[0]
    #define rs tr[u].s[1]
    #define rx tr[x].s[1]
}tr[N];
int n,m,op,x,y;
bool inline isroot(int u){
    return tr[tr[u].p].s[0]!=u&&tr[tr[u].p].s[1]!=u;
}
void inline pushup(int u){
    tr[u].sum=tr[ls].sum^tr[u].v^tr[rs].sum;
}
void inline pushrev(int u){
    swap(ls,rs);
    tr[u].rev^=1;
}
void inline pushdown(int u){
    if(tr[u].rev){
        pushrev(ls),pushrev(rs);
        tr[u].rev=0;
    }
}
void inline rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void inline splay(int x){
    static int stk[N];
    int tt=0,t=x;
    stk[++tt]=t;
    while(!isroot(t))stk[++tt]=t=tr[t].p;
    while(tt)pushdown(stk[tt--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if( (tr[z].s[1]==y)^(tr[y].s[1]==x) )rotate(x);
            else rotate(y);
        }rotate(x);
    }
}
void inline access(int x){
    int z=x;
    for(int y=0;x;y=x,x=tr[x].p){
        splay(x);
        rx=y;
        pushup(x);
    }
    splay(z);
}
void inline makeroot(int x){
    access(x);
    pushrev(x);
}
int inline findroot(int u){
    access(u);
    while(ls)pushdown(u),u=ls;
    splay(u);
    return u;
}
void inline split(int x,int y){
    makeroot(x);
    access(y);
}
void inline link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)tr[x].p=y;
}
void inline cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
        tr[y].p=rx=0;
        pushup(x);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>tr[i].v;
    while(m--){
        cin>>op>>x>>y;
        if(op==0){
            split(x,y);
            cout<<tr[y].sum<<'\n';
        }
        if(op==1)link(x,y);
        if(op==2)cut(x,y);
        if(op==3){
            splay(x);
            tr[x].v=y;
            pushup(x);
        }
    }
}