/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 576.0 KiB
#2 Accepted 154ms 4.258 MiB
#3 Accepted 67ms 676.0 KiB
#4 Accepted 109ms 1.363 MiB
#5 Accepted 152ms 4.527 MiB
#6 Accepted 197ms 14.902 MiB
#7 Accepted 401ms 103.98 MiB
#8 Accepted 397ms 103.977 MiB
#9 Accepted 403ms 103.902 MiB
#10 Accepted 411ms 103.977 MiB
#11 Accepted 413ms 103.961 MiB
#12 Accepted 421ms 103.926 MiB
#13 Accepted 156ms 110.57 MiB
#14 Accepted 219ms 110.551 MiB
#15 Accepted 218ms 110.723 MiB
#16 Accepted 216ms 110.723 MiB

Code

//#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#ifdef Mhmd_Bakr
#include "mhmd_bakr.h"
#endif

//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace boost::multiprecision;

// Author: Mohamed Bakr

#define ll long long
#define INT int32_t
#define int ll
#define vct vector
//#define int128 number<cpp_int_backend<128, 128, unsigned_magnitude, unchecked, void>>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sum(v) accumulate(all(v), 0LL)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define ln "\n"
#define lln cout<<ln
#define umap unordered_map
#define yes cout<<"YES"<<ln
#define no cout<<"NO"<<ln
#define precision(x,y) fixed<<setprecision(y)<<x
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define PI 3.141592653589793238462643383279502884197
#define toDeg(theta) theta*(180.0/PI)
#define toRad(theta) theta*(PI/180.0)

template <typename T, typename C>
istream& operator>>(istream& istream, pair<T, C>& pi) { cin >> pi.first >> pi.second; return istream; }
template <typename T, typename C>
ostream& operator<<(ostream& ostream, pair<T, C>& pi) { cout << pi.first << " " << pi.second;  return ostream; }
template <typename T>
istream& operator>>(istream& istream, vector<T>& v) { for (T& it : v) cin >> it; return istream; }
template <typename T>
ostream& operator<<(ostream& ostream, vector<T>& v) { for (T it : v) cout << it << " "; return ostream; }
template <typename T>
ostream& operator<<(ostream& ostream, set<T>& v) { for (T it : v) cout << it << " "; return ostream; }


bool prime(int num) { if (num <= 1) return false; int ch = 2; while (ch * ch <= num) { if (!(num % ch)) return false; ch++; }return true; }
int fact(int n) { if (n == 0) return 1; return n * fact(n - 1); }
int nPr(int n, int r) { int val = 1; for (int i = n - r + 1; i <= n; i++) val *= i; return val; }
int nCr(int n, int r) { return fact(n) / (fact(r) * fact(n - r)); }
int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
int lcm(int a, int b) { return (a / gcd(a, b)) * b; }
int biPow(int x, int y) { int val = 1; while (y) { if (y % 2) { val *= x; y--; } else { x *= x; y /= 2; } }return val; }
int modPow(int x, int y, int m) { int val = 1; x %= m; while (y) { if (y % 2) { val *= x; val %= m; y--; } else { x *= x; x %= m; y /= 2; } }return val % m; }
int sumRng(int l, int r) { return (r - l + 1) * (l + r) / 2; }

string mv[8] = { "U", "R", "D", "L", "UR","UL","DR","DL" };
int xd[9] = { -1, 0, 1,  0, -1, -1, 1,  1, 0 };
int yd[9] = { 0, 1, 0, -1,  1, -1, 1, -1, 0 };
int xk[9] = { -1, 1, 2, -2, -1, 1, 2, -2, 0 };
int yk[9] = { 2, -2, 1, -1, -2, 2, -1, 1, 0 };

struct segtree
{
	int n = 0;
	vct<vct<int>>cnt;
	segtree(const vct<int>& arr) {
		n = arr.size();
		cnt.assign(n * 4, vct<int>(26, 0));
		build(1, 1, n, arr);
	}
	void build(int node, int L, int R, const vct<int>& arr) {
		if (L == R) {
			cnt[node][arr[L - 1]] = 1;
			return;
		}
		int mid = (L + R) / 2;
		build(2 * node, L, mid, arr);
		build(2 * node + 1, mid + 1, R, arr);
		for (int i = 0; i < 26; i++) {
			cnt[node][i] = cnt[2 * node][i] + cnt[2 * node + 1][i];
		}
	}
	char query(int L, int R) {
		auto v = query(1, 1, n, L, R);
		int mx = 0;
		for (int i = 0; i < 26; i++)
			if (v[mx] < v[i]) mx = i;
		return char('a' + mx);
	}
	vct<int> query(int node, int L, int R, int l, int r) {
		if (R < l || r < L)	return vct<int>(26,0);
		if (l <= L && R <= r) return cnt[node];
		int mid = (L + R) / 2;
		auto ls = query(2 * node, L, mid, l, r);
		auto rs = query(2 * node + 1, mid + 1, R, l, r);
		auto v = vct<int>(26, 0);
		for (int i = 0; i < 26; i++)
			v[i] += ls[i] + rs[i];
		return v;
	}
	void update(int ind, int val) {
		update(1, 1, n, ind, val);
	}
	void update(int node, int L, int R, int ind, int val) {
		if (ind<L || ind>R) return;
		if (L == R) {
			for (int i = 0; i < 26; i++)
				cnt[node][i] = 0;
			cnt[node][val] = 1;
			return;
		}
		int mid = (L + R) / 2;
		update(2 * node, L, mid, ind, val);
		update(2 * node + 1, mid + 1, R, ind, val);
		for (int i = 0; i < 26; i++) {
			cnt[node][i] = cnt[2 * node][i] + cnt[2 * node + 1][i];
		}
	}
};

int n;
int ind = 1;
vct<int>gra[100005];
int inds[100005][2];
char s[100005];
vct<int>tour;
void dfstour(int u, int p = -1) {
	tour.push_back(s[u] - 'a');
	inds[u][0] = ind;
	for (int v : gra[u]) {
		if (v != p) {
			ind++;
			dfstour(v, u);
		}
	}
	inds[u][1] = ind;
}
void answer(int test)
{
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> s[i];
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		gra[u].push_back(v);
		gra[v].push_back(u);
	}
	dfstour(1);
	//dbg(tour);
	segtree seg(tour);
	int q; cin >> q;
	while (q--) {
		int op; cin >> op;
		if (op == 1) {
			int u; cin >> u;
			char c; cin >> c;
			seg.update(inds[u][0], c - 'a');
		}
		else {
			int u; cin >> u;
			cout << seg.query(inds[u][0], inds[u][1]) << ln;
		}
	}
}
bool multiTests = false;
INT main()
{
#ifdef Mhmd_Bakr
	//Contest : -
	//Problem : -
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	fastio;
	int tests = 1;
	if (multiTests) cin >> tests;
	for (int test = 1; test <= tests; test++)
	{
		//cout << "Case #" << test << ": ";
		answer(test);
	}
#ifdef Mhmd_Bakr
	End();
#endif
}

Information

Submit By
Type
Submission
Problem
P1091 Alphabetical Kingdom
Contest
Brain Booster #5
Language
C++20 (G++ 13.2.0)
Submit At
2024-09-05 16:34:51
Judged At
2024-11-11 03:00:13
Judged By
Score
100
Total Time
421ms
Peak Memory
110.723 MiB