Danone.cpp

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 2e6+10;

int n, rel[maxn], val[maxn];
vector<int> with[maxn];

void solve() {
    cin >> n;

    for(int i = 0; i <= n; i++) {
        rel[i] = i;
        val[i] = 0;
        with[i].pb(i);
    }

    int q; cin >> q;
    while(q--) {
        char op; cin >> op;

        if(op == 'C') {
            int l,r; cin >> l >> r;
            if(rel[l-1] == rel[r]) {
                cout << val[r]-val[l-1] << endl;
            }
            else {
                cout << "Esquecido" << endl;
            }
        }
        else {
            int l,r,x; cin >> l >> r >> x;
            if(rel[l-1] != rel[r]) {
                if(with[rel[r]].size() < with[rel[l-1]].size()) {
                    for(auto i : with[rel[r]]) {
                        if(i == r) continue; // Para nao dar problema quando mudar rel[r]
                        val[i] = val[l-1]-val[r]+val[i]+x;
                        rel[i] = rel[l-1];
                        with[rel[i]].pb(i);
                    }
                    val[r] = val[l-1]-val[r]+val[r]+x;
                    rel[r] = rel[l-1];
                    with[rel[r]].pb(r);
                }
                else {
                    for(auto i : with[rel[l-1]]) {
                        if(i == l-1) continue; // Para nao dar problema quando mudar rel[l-1]
                        val[i] = val[r]-val[l-1]+val[i]-x;
                        rel[i] = rel[r];
                        with[rel[i]].pb(i);
                    }
                    val[l-1] = val[r]-val[l-1]+val[l-1]-x;
                    rel[l-1] = rel[r];
                    with[rel[l-1]].pb(l-1);
                }
            }
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}