結果

問題 No.650 行列木クエリ
ユーザー chocoruskchocorusk
提出日時 2019-10-02 16:34:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 396 ms / 2,000 ms
コード長 4,607 bytes
コンパイル時間 1,314 ms
コンパイル使用メモリ 125,796 KB
実行使用メモリ 59,052 KB
最終ジャッジ日時 2024-10-03 06:01:20
合計ジャッジ時間 3,569 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 130 ms
11,648 KB
testcase_02 AC 331 ms
45,696 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 133 ms
11,648 KB
testcase_05 AC 339 ms
45,568 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 194 ms
14,336 KB
testcase_09 AC 396 ms
59,052 KB
testcase_10 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

template<typename Monoid=int>
struct LinkCutTree{
	using F=function<Monoid(Monoid, Monoid)>;
	using S=function<Monoid(Monoid)>;

	struct Node{
		Node *l, *r, *p;
		int idx;
		Monoid key, sum;

		bool rev;
		int sz;

		bool is_root(){
			return !p || (p->l!=this && p->r!=this);
		}

		Node(int idx, const Monoid &key):idx(idx), key(key), sum(key), sz(1), l(nullptr), r(nullptr), p(nullptr), rev(false) {}
	};

	const Monoid M1;
	const F f;
	const S s;

	LinkCutTree():LinkCutTree([](Monoid a, Monoid b){ return a+b;}, [](Monoid a){ return a;}, Monoid()){}
	LinkCutTree(const F &f, const S &s, const Monoid &M1):f(f), s(s), M1(M1){}

	Node *make_node(int idx, const Monoid &v=Monoid()){
		return new Node(idx, v);
	}

	void toggle(Node *t){
		assert(t);
		swap(t->l, t->r);
		t->sum=s(t->sum);
		t->rev^=true;
	}

	void push(Node *t){
		if(t->rev){
			if(t->l) toggle(t->l);
			if(t->r) toggle(t->r);
			t->rev=false;
		}
	}

	void update(Node *t){
		t->sz=1;
		t->sum=t->key;
		if(t->l) t->sz+=t->l->sz, t->sum=f(t->l->sum, t->sum);
		if(t->r) t->sz+=t->r->sz, t->sum=f(t->sum, t->r->sum);
	}

	void rotr(Node *t){
		auto *x=t->p, *y=x->p;
		if((x->l=t->r)) t->r->p=x;
		t->r=x, x->p=t;
		update(x), update(t);
		if((t->p=y)){
			if(y->l==x) y->l=t;
			if(y->r==x) y->r=t;
			update(y);
		}
	}

	void rotl(Node *t){
		auto *x=t->p, *y=x->p;
		if((x->r=t->l)) t->l->p=x;
		t->l=x, x->p=t;
		update(x), update(t);
		if((t->p=y)){
			if(y->l==x) y->l=t;
			if(y->r==x) y->r=t;
			update(y);
		}
	}

	void splay(Node* t){
		push(t);
		while(!t->is_root()){
			auto *q=t->p;
			if(q->is_root()){
				push(q), push(t);
				if(q->l==t) rotr(t);
				else rotl(t);
			}else{
				auto *r=q->p;
				push(r), push(q), push(t);
				if(r->l==q){
					if(q->l==t) rotr(q), rotr(t);
					else rotl(t), rotr(t);
				}else{
					if(q->r==t) rotl(q), rotl(t);
					else rotr(t), rotl(t);
				}
			}
		}
	}

	Node *expose(Node *t){
		Node *rp=nullptr;
		for(Node *cur=t; cur; cur=cur->p){
			splay(cur);
			cur->r=rp;
			update(cur);
			rp=cur;
		}
		splay(t);
		return rp;
	}

	void link(Node *child, Node *parent){
		expose(child);
		expose(parent);
		child->p=parent;
		parent->r=child;
		update(parent);
	}

	void cut(Node *child){
		expose(child);
		auto *parent=child->l;
		child->l=nullptr;
		parent->p=nullptr;
		update(child);
	}

	void evert(Node *t){
		expose(t);
		toggle(t);
		push(t);
	}

	Node *lca(Node *u, Node *v){
		if(get_root(u)!=get_root(v)) return nullptr;
		expose(u);
		return expose(v);
	}

	Node *get_root(Node *x){
		expose(x);
		while(x->l){
			push(x);
			x=x->l;
		}
		return x;
	}
};
struct Matrix{
	ll a, b, c, d;
	Matrix():a(1), b(0), c(0), d(1){}
	Matrix(ll a, ll b, ll c, ll d):a(a), b(b), c(c), d(d){}
};
using Mp=pair<Matrix, Matrix>;
int main()
{
	int n;
	cin>>n;
	using LCT=LinkCutTree<Mp>;
	Mp ep=Mp(Matrix(), Matrix());
	const ll MOD=1e9+7;
	auto f0=[MOD](Matrix a, Matrix b){
		Matrix c((a.a*b.a+a.b*b.c)%MOD, (a.a*b.b+a.b*b.d)%MOD, (a.c*b.a+a.d*b.c)%MOD, (a.c*b.b+a.d*b.d)%MOD);
		return c;
	};
	auto f=[&](Mp x, Mp y){
		return Mp(f0(x.first, y.first), f0(y.second, x.second));
	};
	auto s=[](Mp x){ return Mp(x.second, x.first);};
	LCT lct(f, s, ep);
	vector<LCT::Node*> nodev(n), nodee(n-1);
	for(int i=0; i<n; i++){
		nodev[i]=lct.make_node(i, ep);
	}
	for(int i=0; i<n-1; i++){
		nodee[i]=lct.make_node(i+n, ep);
	}
	vector<vector<P>> g(n);
	for(int i=0; i<n-1; i++){
		int a, b; cin>>a>>b;
		g[a].push_back({b, i});
		g[b].push_back({a, i});
	}
	vector<int> ve(n-1);
	auto dfs=[&](auto dfs, int x, int p)->void{
		for(auto q:g[x]){
			int y=q.first, i=q.second;
			if(y!=p){
				lct.link(nodee[i], nodev[x]);
				lct.link(nodev[y], nodee[i]);
				dfs(dfs, y, x);
			}
		}
	};
	dfs(dfs, 0, -1);
	int Q; cin>>Q;
	for(int t=0; t<Q; t++){
		char c;
		cin>>c;
		if(c=='x'){
			int i, a, b, c, d;
			cin>>i>>a>>b>>c>>d;
			lct.expose(nodee[i]);
			Matrix x(a, b, c, d);
			nodee[i]->key=Mp(x, x);
		}else{
			int i, j;
			cin>>i>>j;
			lct.evert(nodev[i]);
			lct.expose(nodev[j]);
			Matrix ans=nodev[j]->sum.first;
			cout<<ans.a<<" "<<ans.b<<" "<<ans.c<<" "<<ans.d<<endl;
		}
	}
	return 0;
}
0