#122181 (C++11（廃止可能性あり）) No.235 めぐるはめぐる (5)

提出ソース

結果

問題	No.235 めぐるはめぐる (5)
コンテスト
ユーザー	pekempey
提出日時	2016-10-07 12:26:32
言語	C++11（廃止可能性あり） (gcc 13.3.0)
結果	AC
実行時間	379 ms / 10,000 ms
コード長	6,081 bytes
コンパイル時間	2,544 ms
コンパイル使用メモリ	187,360 KB
実行使用メモリ	28,736 KB
最終ジャッジ日時	2024-11-21 19:09:11
合計ジャッジ時間	4,361 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
other	AC * 3

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
uint32_t inv;
int r2;

int freq[32];

int reduce(uint64_t x) {
	uint64_t y = uint64_t(uint32_t(x) * inv) * mod;
	return int(x >> 32) + mod - int(y >> 32);
}

int transform(int n) {
	return reduce(int64_t(n) * r2);
}

int normalize(int n) {
	return n >= mod ? n - mod : n;
}

void init_montgomery_reduction() {
	inv = 1;
	for (int i = 0; i < 5; ++i) inv *= 2 - inv * uint32_t(mod);
	r2 = -uint64_t(mod) % mod;
}

void add(int &a, int b) {
	(a += b - mod) < 0 ? a += mod : a;
}

int modadd(int a, int b) {
	return (a += b - mod) < 0 ? a + mod : a;
}

int modmul(int a, int b) {
	return reduce(int64_t(a) * b);
}

const int N = 1 << 18;
struct node {
	int w, sum, add;
};
node seg[N * 2];
int naive[N], ww[N];
int S[N], C[N];

void push(int k) {
	if (seg[k].add == 0) return;
	add(seg[k].sum, modmul(seg[k].add, seg[k].w));
	add(seg[k * 2 + 0].add, seg[k].add);
	add(seg[k * 2 + 1].add, seg[k].add);
	seg[k].add = 0;
}

int get_val(int k) {
	if (seg[k].add == 0) return seg[k].sum;
	return modadd(seg[k].sum, modmul(seg[k].add, seg[k].w));
}

void update(int l, int r, int v, int H) {
	if (H >= 6) {
		int ll = l + N;
		int rr = r + N - 1;
		bool L = false;
		bool R = false;
		for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
			if (l & 1) add(seg[l++].add, v), L = true;
			if (r & 1) add(seg[--r].add, v), R = true;
		}
		for (int i = 1; i <= H; i++) {
			seg[ll >> 1].sum = modadd(get_val(ll), get_val(ll ^ 1));
			if (R && ll != rr) {
				seg[rr >> 1].sum = modadd(get_val(rr), get_val(rr ^ 1));
			}
			ll >>= 1;
			rr >>= 1;
		}
	} else if (r - l >= 16) {
		const int M = 4;
		while (l < r && (l & 0x3) != 0) add(naive[l], modmul(ww[l], v)), l++;
		while (l < r && (r & 0x3) != 0) r--, add(naive[r], modmul(ww[r], v));
		for (int i = l; i < r; i += 4) {
			for (int j = 0; j < M; j++) {
				add(naive[i + j], modmul(ww[i + j], v));
			}
		}
	} else {
		for (int i = l; i < r; i++) {
			add(naive[i], modmul(ww[i], v));
		}
	}
}

int query(int l, int r, int H) {
	if (H >= 6) {
		int ll = l + N;
		int rr = r + N - 1;
		for (int i = H; i >= 1; i--) {
			push(ll >> i);
			if (ll >> i != rr >> i) push(rr >> i);
		}
		int res = 0;
		for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
			if (l & 1) add(res, get_val(l++));
			if (r & 1) add(res, get_val(--r));
		}
		return res;
	} else if (r - l >= 16) {
		const int M = 4;
		int res = 0;
		while (l < r && (l & 0x3) != 0) add(res, naive[l]), l++;
		while (l < r && (r & 0x3) != 0) r--, add(res, naive[r]);
		for (int i = l; i < r; i += 4) {
			for (int j = 0; j < M; j++) {
				add(res, naive[i + j]);
			}
		}
		return res;
	} else {
		int res = 0;
		for (int i = l; i < r; i++) {
			add(res, naive[i]);
		}
		return res;
	}
}

struct HLDecomposition {
	struct node {
		int vid, head, parent, len_path = 0;
	};

	vector<vector<int>> g;
	vector<int> heavy;
	vector<node> vs;

	HLDecomposition(int n) : g(n), vs(n), heavy(n) {}

	void add(int u, int v) {
		g[u].push_back(v);
		g[v].push_back(u);
	}

	void build() {
		dfs(0, -1);
		bfs();
	}

	int dfs(int curr, int prev) {
		vs[curr].parent = prev;
		heavy[curr] = -1;
		int sub = 1, max_sub = 0;
		for (int next : g[curr]) if (next != prev) {
			int sub_next = dfs(next, curr);
			sub += sub_next;
			if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;
		}
		return sub;
	}

	void bfs() {
		int k = 0;
		queue<int> q({ 0 });
		while (!q.empty()) {
			int h = q.front(); q.pop();
			for (int i = h; i != -1; i = heavy[i]) {
				vs[h].len_path++;
				vs[i].vid = k++;
				vs[i].head = h;
				for (int j : g[i]) if (j != vs[i].parent && j != heavy[i]) q.push(j);
			}
			vs[h].len_path = log2(vs[h].len_path * 2 - 1);
			freq[vs[h].len_path]++;
		}
	}

	void update_path(int u, int v, int z) {
		while (true) {
			if (vs[u].vid > vs[v].vid) swap(u, v);
			int uh = vs[u].head;
			int vh = vs[v].head;
			if (uh == vh) {
				update(vs[u].vid, vs[v].vid + 1, z, vs[vh].len_path);
				break;
			} else {
				update(vs[vh].vid, vs[v].vid + 1, z, vs[vh].len_path);
				v = vs[vh].parent;
			}
		}
	}

	int query_path(int u, int v) {
		int res = 0;
		while (true) {
			if (vs[u].vid > vs[v].vid) swap(u, v);
			int uh = vs[u].head;
			int vh = vs[v].head;
			if (vs[u].head == vs[v].head) {
				::add(res, query(vs[u].vid, vs[v].vid + 1, vs[vh].len_path));
				break;
			} else {
				::add(res, query(vs[vh].vid, vs[v].vid + 1, vs[vh].len_path));
				v = vs[vh].parent;
			}
		}
		return res;
	}

	int operator[](int k) {
		return vs[k].vid;
	}
};

// 入出力。Min_25 さんのコードを参考にしました
#define getchar getchar_unlocked
#define putchar putchar_unlocked

// - 0.30 sec
int in() {
	int n, c;
	while ((c = getchar()) < '0') if (c == EOF) return -1;
	n = c - '0';
	while ((c = getchar()) >= '0') n = n * 10 + c - '0';
	return n;
}
int in_t() {
	return transform(in());
}
// - 0.02 sec
void put_int(int n) {
	int res[11], i = 0;
	do { res[i++] = n % 10, n /= 10; } while (n);
	while (i) putchar(res[--i] + '0');
	putchar('\n');
}

double elapsed() {
	static clock_t curr;
	clock_t prev = curr;
	curr = clock();
	return (double)(curr - prev) / CLOCKS_PER_SEC;
}

int main() {
	init_montgomery_reduction();

	int n = in();

	for (int i = 0; i < n; i++) S[i] = in_t();
	for (int i = 0; i < n; i++) C[i] = in_t();

	HLDecomposition hld(n);
	for (int i = 1; i < n; i++) hld.add(in() - 1, in() - 1);
	hld.build();

	for (int i = 0; i < n; i++) {
		seg[hld[i] + N].sum = S[i];
		seg[hld[i] + N].w = C[i];
		naive[hld[i]] = S[i];
		ww[hld[i]] = C[i];
	}
	for (int i = N - 1; i >= 1; i--) {
		seg[i].sum = modadd(seg[i * 2 + 0].sum, seg[i * 2 + 1].sum);
		seg[i].w = modadd(seg[i * 2 + 0].w, seg[i * 2 + 1].w);
	}

	for (int i = 0; i < 32; i++) {
		cerr << i << " " << freq[i] << endl;
	}

	int q = in();
	while (q--) {
		int t = in();

		if (t == 0) {
			int u = in() - 1, v = in() - 1, z = in_t();
			hld.update_path(u, v, z);
		} else {
			int u = in() - 1, v = in() - 1;
			put_int(normalize(reduce(hld.query_path(u, v))));
		}
	}
}

yukicoder

結果

ソースコード