結果

問題 No.772 Dynamic Distance Sum
ユーザー HIR180HIR180
提出日時 2020-04-14 21:54:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,162 ms / 5,000 ms
コード長 6,540 bytes
コンパイル時間 2,895 ms
コンパイル使用メモリ 234,104 KB
実行使用メモリ 96,896 KB
最終ジャッジ日時 2024-10-01 18:14:06
合計ジャッジ時間 23,394 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 50 ms
62,208 KB
testcase_01 AC 51 ms
62,208 KB
testcase_02 AC 54 ms
62,208 KB
testcase_03 AC 58 ms
62,208 KB
testcase_04 AC 57 ms
62,592 KB
testcase_05 AC 53 ms
62,464 KB
testcase_06 AC 56 ms
62,464 KB
testcase_07 AC 52 ms
62,336 KB
testcase_08 AC 54 ms
62,336 KB
testcase_09 AC 58 ms
62,720 KB
testcase_10 AC 56 ms
62,592 KB
testcase_11 AC 52 ms
62,464 KB
testcase_12 AC 1,162 ms
92,800 KB
testcase_13 AC 1,000 ms
92,416 KB
testcase_14 AC 1,030 ms
95,360 KB
testcase_15 AC 733 ms
92,544 KB
testcase_16 AC 899 ms
93,312 KB
testcase_17 AC 1,045 ms
93,056 KB
testcase_18 AC 604 ms
94,976 KB
testcase_19 AC 989 ms
92,288 KB
testcase_20 AC 526 ms
95,360 KB
testcase_21 AC 1,068 ms
93,568 KB
testcase_22 AC 953 ms
92,928 KB
testcase_23 AC 1,072 ms
96,768 KB
testcase_24 AC 758 ms
93,312 KB
testcase_25 AC 893 ms
93,952 KB
testcase_26 AC 992 ms
93,696 KB
testcase_27 AC 844 ms
94,464 KB
testcase_28 AC 1,037 ms
92,800 KB
testcase_29 AC 589 ms
96,896 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//Let's join Kaede Takagaki Fan Club !!
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define all(x) x.begin(),x.end()
template<class T>
void dmp(T a){
	rep(i,a.size()) cout << a[i] << " ";
	cout << endl;
}
template<class T>
bool chmax(T&a, T b){
	if(a < b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
bool chmin(T&a, T b){
	if(a > b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
void g(T &a){
	cin >> a;
}
template<class T>
void o(const T &a,bool space=false){
	cout << a << (space?' ':'\n');
}
//ios::sync_with_stdio(false);
const ll mod = 1000000007;//998244353
template<class T>
void add(T&a,T b){
	a+=b;
	if(a >= mod) a-=mod;
}


struct LinkCutTree{
	struct dat {
		int cnt1;
		ll sum, sum1, sum2;
		void rv(){ swap(sum1, sum2); }
	};
	struct node{
		node *p,*l,*r; //親、左の子、右の子
		int id, rev;
		dat D, L, S;
		multiset<P, greater<P>>L_sz;
		node(int i, int c, int w) : l(0), r(0), p(0), id(i), rev(0) {
			D = S = {c, w, w, w};
			L = {0, 0, 0, 0};
			L_sz.clear();
		}
		//このノードはsplay木の根？ (=今いるパスの最上頂点？)
		bool is_root(){
			return !p || (p->l != this && p->r != this);
		}
	};
	//右回転
	void rotr(node *n, int sz){
		node *q = n->p, *g = q->p;
		if((q->l = n->r)) n->r->p = q;
		n->r = q; q->p = n;
		if((n->p = g)){
			if(g->l == q) g->l = n;
			else if(g->r == q) g->r = n;
			else{
				g->L_sz.erase(mp(sz, q->id));
				g->L_sz.insert(mp(sz, n->id));
			}
		}
	}
	//左回転
	void rotl(node *n, int sz){
		node *q = n->p, *g = q->p;
		if((q->r = n->l)) n->l->p = q;
		n->l = q; q->p = n;
		if((n->p = g)){
			if(g->l == q) g->l = n;
			else if(g->r == q) g->r = n;
			else{
				g->L_sz.erase(mp(sz, q->id));
				g->L_sz.insert(mp(sz, n->id));
			}
		}
	}
	//スプレー操作
	void splay(node *n){
	    if(n->is_root()) {
	        update(n); return;
	    }
		while(!n->is_root()){
			node *q = n->p;
			//自分の親がroot、zig
			if(q->is_root()){
			    push(q); push(n);
			    int X = q->D.cnt1;
				if(q->l == n){
					rotr(n, X);
				}
				else{
					rotl(n, X);
				}
				update(q); update(n);
			}
			else{
				node *r = q->p;
				push(r); push(q); push(n);
				int X = r->D.cnt1;
				if(r->l == q){
					if(q->l == n){
						//zig-zig
						rotr(q, X), rotr(n, X);
					}
					else{
						//zig-zag
						rotl(n, X), rotr(n, X);
					}
				}
				else{
					if(q->r == n){
						//zig-zig
						rotl(q, X);rotl(n, X);
					}
					else{
						//zig-zag
						rotr(n, X);rotl(n, X);
					}
				}
				update(r); update(q); update(n);
			}
		}
	}
	
	node *pool[300005];
	//本質
	//xから根までのパスを形成
	node *expose(node *x){
		node *r = (node *)NULL;
		for(node *p = x;p;p = p->p){
			//今いるところをsplay
			splay(p);
			//右にさっきまでの木を繋げる
			if(p->r){
				p->L.cnt1 += p->r->D.cnt1;
				p->L.sum1 += p->r->D.sum1;
				p->L_sz.insert(mp(p->r->D.cnt1, p->r->id));
			}
			p->r = r;
			if(p->r){
				p->L.cnt1 -= p->r->D.cnt1;
				p->L.sum1 -= p->r->D.sum1;
				p->L_sz.erase(mp(p->r->D.cnt1, p->r->id));
			}
			//覚えておく
			update(p);
			r = p;
		}
		splay(x);
		return r;
	}
	node *find_root(node *n){
		if(!n) return NULL;
		while(1){ push(n); if(n->r) n = n->r; else return n; }
	}
	node *cut(node *n){
	    expose(n);
		node *p = n->l;
		n->l->p = NULL;
		n->l = NULL;
		update(n);
		return find_root(p);
	}
	void link(node *c, node *p){
		expose(c); expose(p);
		c->p = p;
		p->r = c;
		update(p);
	}
	void push(node *n){
		if(n->rev){
			swap(n->l, n->r);
			if(n->l) n->l->rev ^= 1, n->l->D.rv();
			if(n->r) n->r->rev ^= 1, n->r->D.rv();
			n->rev = 0;
		}
	}
	void update(node *n){
		push(n);
		
		n->D.cnt1 = (n->l?n->l->D.cnt1:0) + (n->r?n->r->D.cnt1:0) + n->L.cnt1 + n->S.cnt1;
		n->D.sum = (n->l?n->l->D.sum:0) + (n->r?n->r->D.sum:0) + n->S.sum;
		n->D.sum1 = 0;
		if(n->l) n->D.sum1 += n->l->D.sum1;
		if(n->r) n->D.sum1 += n->r->D.sum1 + 1LL*(n->S.sum+(n->l?n->l->D.sum:0)) * n->r->D.cnt1;
		if(n->S.cnt1) n->D.sum1 += 1LL*(n->S.sum+(n->l?n->l->D.sum:0));
		n->D.sum1 += n->L.sum1 + 1LL*(n->S.sum+(n->l?n->l->D.sum:0)) * n->L.cnt1;
		
		n->D.sum2 = 0;
		if(n->l) n->D.sum2 += n->l->D.sum2 + 1LL*(n->S.sum+(n->r?n->r->D.sum:0)) * n->l->D.cnt1;
		if(n->r) n->D.sum2 += n->r->D.sum2;
		if(n->S.cnt1) n->D.sum2 += 1LL*(n->S.sum+(n->r?n->r->D.sum:0));
		n->D.sum2 += n->L.sum1 + 1LL*(n->S.sum+(n->r?n->r->D.sum:0)) * n->L.cnt1;
	}
	int find(node *n, int sz){
	    int lim = (sz+1)/2;
		while(1){
			push(n);
			if(n->r && n->r->D.cnt1 >= lim) n = n->r;
			else if(n->l && n->D.cnt1 - n->l->D.cnt1 < lim){
			    lim -= (n->D.cnt1-n->l->D.cnt1); n = n->l; 
			}
			else if(n->L_sz.size() && (*n->L_sz.begin()).fi >= (sz+1)/2){
				lim = (sz+1)/2; n = pool[(*n->L_sz.begin()).sc];
			}
			else return n->id;
		}
	}
	void evert(node *n){
		expose(n);
		n->rev ^= 1;
		n->D.rv();
	}
}kaede;

int n, q;
ll sum;
int nxt = 100001;
int main(){
	scanf("%d%d",&n, &q);
	repn(i, 300003) kaede.pool[i] = new LinkCutTree::node(i, 1, 0);
	rep(i, q){
		int ty; scanf("%d",&ty);
		if(ty == 1){
			int a, b, c; scanf("%d%d%d",&a,&b,&c);
			a = (a-1+sum)%n+1; b = (b-1+sum)%n+1;
			kaede.evert(kaede.pool[a]);
			kaede.pool[nxt] = new LinkCutTree::node(nxt, 0, c);
			kaede.link(kaede.pool[a], kaede.pool[nxt]);
			kaede.link(kaede.pool[nxt], kaede.pool[b]); nxt++;
		}
		else if(ty == 2){
			int a, b; scanf("%d%d",&a,&b);
			a = (a-1+sum)%n+1; b = (b-1+sum)%n+1;
			kaede.evert(kaede.pool[a]);
			auto *mid = kaede.cut(kaede.pool[b]);
			kaede.cut(mid);
		}
		else{
			int a; scanf("%d",&a);
			a = (a-1+sum)%n+1;
			kaede.evert(kaede.pool[a]); kaede.pool[a]->S.cnt1 ^= 1; kaede.update(kaede.pool[a]);
			ll ans = 1e18;
			if(kaede.pool[a]->D.cnt1 == 0){
				ans = 0;
			}
			else{
				int cent = kaede.find(kaede.pool[a], kaede.pool[a]->D.cnt1);
				kaede.evert(kaede.pool[cent]); ans = kaede.pool[cent]->D.sum1;
			}
			printf("%lld\n", ans);
			sum = (sum+ans)%n;
		}
	}
}
0