結果

問題 No.1054 Union add query
コンテスト
ユーザー kenken714
提出日時 2020-05-15 22:28:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 523 ms / 2,000 ms
コード長 5,204 bytes
コンパイル時間 1,524 ms
コンパイル使用メモリ 172,284 KB
実行使用メモリ 38,656 KB
最終ジャッジ日時 2024-09-19 11:19:52
合計ジャッジ時間 5,640 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
 
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)
#define REPO(i, n) for (ll i = 1; i <= n; i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(), n.end()
#define MOD 1000000007
#define P pair<ll, ll>


//Link Cut Tree
//木クエリを殴る
//ぺちぺち
template< typename Type = ll,typename OType = Type >
struct LCT{
    using F = function<Type(Type, Type)>;       //要素
    using G = function<Type(Type, OType, int)>; //要素と作用素, 長さ
    using H = function<OType(OType, OType)>;    //作用素
    using S = function<Type(Type)>;             //反転
    const F f;
    const G g;
    const H h;
    const S s;
    const Type Te;                              //要素の単位元
    const OType OTe;                            //作用素の単位元

    LCT() : LCT([](Type a, Type b) { return a + b; }, [](Type a) { return a; }, Type()) {}
    LCT(const F &f, const S &s, const Type &Te) : LCT(f, G(), H(), s, Te, OType()){}
    LCT(const F &f, const G &g, const H &h, const S &s, const Type &Te, const OType &OTe) : f(f), g(g), h(h), s(s), Te(Te), OTe(OTe){}
    
    struct Node {
        Node *l, *r, *par;
        int size, idx;
        bool rev;
        Type value, sum;
        OType lazy; //遅延評価
        Node(int num, const Type &t, const OType &ot){
            l = nullptr; r = nullptr; par = nullptr;
            idx = num, value = t, sum = t, lazy = ot;
            size = 1;
        }
        bool is_root(){
            return !par or (par->l != this and par->r != this);
        }
    };
	void toggle(Node *t) {
    assert(t);
    swap(t->l, t->r);
    t->sum = s(t->sum);
    t->rev ^= true;
	}
    void update(Node *me){
        me->size = 1;
        me->sum = me->value;
        if (me->l) {
            me->size += me->l->size;
            me->sum = f(me->l->sum, me->sum);
        }
        if (me->r) {
            me->size += me->r->size;
            me->sum = f(me->sum, me->r->sum);
        }
    }
    void rotate(Node *me){
        Node *p, *pp, *c;
        p = me->par;
        pp = p->par;
        if(p->l == me){
            c = me->r; p->l = c; me->r = p;
        }
        else{
            c = me->l; p->r = c; me->l = p;
        }
        if (pp and pp->l == p) pp->l = me;
        if (pp and pp->r == p) pp->r = me;
        me->par = pp; p->par = me;
        if (c) c->par = p;
        update(p); update(me);
    }
    int state(Node *me){
    if (!me->par) return 0;
    if (me->par->l == me) return 1;
    if (me->par->r == me) return -1;
    return 0;
    }
    void splay(Node *me){
        while(!me->is_root()){
            if (state(me->par) == 0) {
                rotate(me);
            }
            else if (state(me) == state(me->par)){
                rotate(me->par); rotate(me);
            }
            else{
                rotate(me); rotate(me);
            }
        }
    }
    Node* new_node(int idx, const Type &val = Type()){
        return new Node(idx, val, OTe);
    }
    void propagate(Node *x, const OType &o){
        x->lazy = h(x->lazy, o);
        x->value = g(x->value, o, 1);
        x->sum = g(x->value, o, x->size);
    }
    void eval(Node *x){
        if(x->lazy != OTe){
            if (x->l) propagate(x->l, x->lazy);
            if (x->r) propagate(x->r, x->lazy);
            x->lazy = OTe;
        }
    }
    Node* expose(Node* x){
        Node *nr = nullptr;
        for (Node* now = x; now; now = now->par){
            splay(now);
            now->r = nr;
            update(now);
            nr = now;
        }
        splay(x);
        return nr;
    }
    void link(Node *x, Node *p){
        expose(x);
        expose(p);
        x->par = p;
        p->r = x;
        update(p);
    }
    void cut(Node *x){
        expose(x);
        Node *p = x->l;
        p->par = nullptr;
        x->l = nullptr;
        update(x);
    }
    void evert(Node *x){
        expose(x);
        //toggle(x); TODO: あとでやる
        eval(x);
    }
    Node* lca(Node* a, Node* b){
        if (get_root(a) != get_root(b)) return nullptr;
        expose(a);
        return expose(b);
    }
    Node *get_root(Node *x){
        expose(x);
        while(x->l){
            eval(x);
            x = x->l;
        }
        return x;
    }
};

int main() {
    ll n, q;
    cin >> n >> q;
    LCT<int> lct;
    vector<LCT<int>::Node*> s(n);
    REP(i, n) s[i] = lct.new_node(i);
    REP(i, q){
        int t;
        scanf("%d", &t);
		int a, b;
		scanf("%d%d", &a, &b);
        a--;
        b--;
        if(t == 1){
            LCT<int>::Node *ar = lct.get_root(s[a]);
            LCT<int>::Node *br = lct.get_root(s[b]);
           	if (ar == br) continue;
			ar->value -= br->value;
            lct.link(ar, br);
        }
		if(t == 2){
            LCT<int>::Node *ar = lct.get_root(s[a]);
            lct.expose(ar);
            ar->value += b + 1;
        }
		if(t == 3){
            lct.expose(s[a]);
            printf("%d\n", s[a]->sum);
        }
    }
}
0