結果

問題 No.3239 Omnibus
ユーザー ルビサファせだい
提出日時 2025-08-21 12:56:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,088 bytes
コンパイル時間 4,798 ms
コンパイル使用メモリ 285,512 KB
実行使用メモリ 77,460 KB
最終ジャッジ日時 2025-08-21 12:57:19
合計ジャッジ時間 16,976 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using ll = long long;
using ull = unsigned long long;
template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<>>;
ll ll_min = numeric_limits<ll>::min();
ll ll_max = numeric_limits<ll>::max();
ll ALPHABET_N = 26;
static const ll INF = ll_max / 10;
#define rep(i, n) for (ll i = (ll)0; i < (ll)n; i++)
#define rep_(i, k, n) for (ll i = (ll)k; i < (ll)n; i++)
#define all(a) a.begin(), a.end()
using namespace atcoder;

struct Node
{
	ll i_sum = 0;
	ll cnt_sum = 0;
};

Node op(Node a, Node b)
{
	Node res;
	res.i_sum = a.i_sum + b.i_sum;
	res.cnt_sum = a.cnt_sum + b.cnt_sum;
	return res;
}

Node e()
{
	Node res;
	res.i_sum = 0;
	res.cnt_sum = 0;
	return res;
}

enum EventType
{
	ADD,
	REMOVE,
	QUERY
};

struct Event
{
	ll t;
	EventType type;
	ll idx = -1;
	ll l = -1;
	ll r = -1;
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	vector<tuple<ll, ll, ll, string>> queries(q);
	unordered_map<string, vector<Event>> ump;
	rep(i, q)
	{
		ll t;
		cin >> t;
		if (t == 1)
		{
			ll k;
			string x;
			cin >> k >> x;
			queries[i] = {t, k - 1, -1, x};
		}
		else
		{
			ll l, r;
			string a;
			cin >> l >> r >> a;
			queries[i] = {t, l - 1, r, a};
			ump[a].push_back({i, QUERY, -1, l - 1, r});
		}
	}
	rep(i, n - 2)
	{
		string str = s.substr(i, 3);
		if (ump.find(str) == ump.end())
			continue;
		ump[str].push_back({-1, ADD, i});
	}
	rep(i, q)
	{
		auto [t, a, b, c] = queries[i];
		if (t == 1)
		{
			ll idx = a;
			char x = c[0];
			for (ll si = max(0LL, idx - 2); si <= min(n - 3, idx); si++)
			{
				string str = s.substr(si, 3);
				if (ump.find(str) == ump.end())
					continue;
				ump[str].push_back({i, REMOVE, si});
			}
			s[idx] = x;
			for (ll si = max(0LL, idx - 2); si <= min(n - 3, idx); si++)
			{
				string str = s.substr(si, 3);
				if (ump.find(str) == ump.end())
					continue;
				ump[str].push_back({i, ADD, si});
			}
		}
	}
	for (auto &[key, events] : ump)
	{
		sort(all(events), [](const Event &a, const Event &b)
			 { return a.t < b.t; });
	}
	segtree<Node, op, e> seg(n - 2);
	vector<pair<ll, ll>> t_ans;
	for (auto &[key, events] : ump)
	{
		unordered_set<ll> added;
		for (const auto &event : events)
		{
			if (event.type == ADD)
			{
				seg.set(event.idx, {event.idx + 1, 1});
				added.insert(event.idx);
			}
			else if (event.type == REMOVE)
			{
				seg.set(event.idx, {0, 0});
				added.erase(event.idx);
			}
			else if (event.type == QUERY)
			{
				ll l = event.l, r = event.r - 3;
				if (l <= r)
				{
					Node res = seg.prod(l, r + 1);
					ll ans = res.i_sum - (l * res.cnt_sum);
					t_ans.push_back({event.t, ans});
				}
				else
				{
					t_ans.push_back({event.t, 0});
				}
			}
		}
		for (const auto &idx : added)
		{
			seg.set(idx, {0, 0});
		}
	}
	sort(all(t_ans), [](const pair<ll, ll> &a, const pair<ll, ll> &b)
		 { return a.first < b.first; });
	rep(i, t_ans.size())
	{
		cout << t_ans[i].second << "\n";
	}
	return 0;
}
0