Submission #10440078


Source Code Expand

Copy
#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144 * 2LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL);
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
void init() {
	iostream::sync_with_stdio(false);

}

int seg_tree[seg_size * 4LL];
int seg_find(int now, int n_l, int n_r, int w_l, int w_r) {
	if (w_l <= n_l && n_r <= w_r) return seg_tree[now];
	if (w_r <= n_l || n_r <= w_l) return 0;
	return (seg_find(now * 2, n_l, (n_l + n_r) / 2, w_l, w_r) | seg_find(now * 2 + 1, (n_l + n_r) / 2, n_r, w_l, w_r));
}

int seg_set(int now) {
	seg_tree[now] = seg_tree[now * 2] | seg_tree[now * 2 + 1];
	if (now > 1) seg_set(now / 2);
	return 0;
}

void solve(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	int query;
	cin >> query;
	REP(i, s.length()) {
		seg_tree[i + seg_size] = (1 << (s[i] - 'a'));
		seg_set((i + seg_size) / 2);
	}
	REP(i, query) {
		int a;
		cin >> a;
		if (a == 1) {
			int b;
			cin >> b;
			string c;
			cin >> c;
			b--;
			seg_tree[b + seg_size] = (1 << (c[0] - 'a'));
			seg_set((b + seg_size) / 2);
		}
		else {
			int b, c;
			cin >> b >> c;
			b--;
			int hoge = seg_find(1, 0, seg_size, b, c);
			int ans = 0;
			REP(q, 27) {
				if ((1 << q) & hoge) {
					ans++;
				}
			}
			cout << ans << endl;
		}
	}
}

#undef int

int main() {
	init();
	solve();
}

Submission Info

Submission Time
Task E - Simple String Queries
User kotamanegi
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1790 Byte
Status AC
Exec Time 68 ms
Memory 4892 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 1
AC × 43
Set Name Test Cases
Sample 00-sample-00
All 00-sample-00, 01-handmade-00, 01-handmade-01, 01-handmade-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 01-handmade-11, 02-small-00, 02-small-01, 02-small-02, 02-small-03, 02-small-04, 02-small-05, 02-small-06, 02-small-07, 02-small-08, 02-small-09, 02-small-10, 02-small-11, 02-small-12, 02-small-13, 02-small-14, 02-small-15, 02-small-16, 02-small-17, 02-small-18, 02-small-19, 03-large-00, 03-large-01, 03-large-02, 03-large-03, 03-large-04, 03-large-05, 03-large-06, 03-large-07, 03-large-08, 03-large-09
Case Name Status Exec Time Memory
00-sample-00 AC 2 ms 2304 KB
01-handmade-00 AC 52 ms 4892 KB
01-handmade-01 AC 2 ms 2304 KB
01-handmade-02 AC 34 ms 4892 KB
01-handmade-03 AC 68 ms 4892 KB
01-handmade-04 AC 63 ms 4892 KB
01-handmade-05 AC 53 ms 4892 KB
01-handmade-06 AC 53 ms 4892 KB
01-handmade-07 AC 52 ms 4892 KB
01-handmade-08 AC 67 ms 4892 KB
01-handmade-09 AC 66 ms 4892 KB
01-handmade-10 AC 66 ms 4892 KB
01-handmade-11 AC 67 ms 4892 KB
02-small-00 AC 16 ms 2304 KB
02-small-01 AC 21 ms 2432 KB
02-small-02 AC 17 ms 2304 KB
02-small-03 AC 24 ms 2432 KB
02-small-04 AC 14 ms 2304 KB
02-small-05 AC 14 ms 2304 KB
02-small-06 AC 25 ms 2432 KB
02-small-07 AC 17 ms 2304 KB
02-small-08 AC 17 ms 2304 KB
02-small-09 AC 16 ms 2304 KB
02-small-10 AC 26 ms 2304 KB
02-small-11 AC 15 ms 2304 KB
02-small-12 AC 15 ms 2304 KB
02-small-13 AC 25 ms 2304 KB
02-small-14 AC 21 ms 2304 KB
02-small-15 AC 20 ms 2304 KB
02-small-16 AC 19 ms 2304 KB
02-small-17 AC 15 ms 2304 KB
02-small-18 AC 19 ms 2304 KB
02-small-19 AC 22 ms 2304 KB
03-large-00 AC 52 ms 4892 KB
03-large-01 AC 52 ms 4892 KB
03-large-02 AC 52 ms 4892 KB
03-large-03 AC 52 ms 4892 KB
03-large-04 AC 52 ms 4892 KB
03-large-05 AC 52 ms 4892 KB
03-large-06 AC 52 ms 4892 KB
03-large-07 AC 52 ms 4892 KB
03-large-08 AC 53 ms 4892 KB
03-large-09 AC 52 ms 4892 KB