Submission #10444798


Source Code Expand

Copy
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<typename T>
struct BIT{ //1-indexed
    vector<T> bit;
    int size;
    BIT(int n):size(n), bit(n+1, 0){}
    T sum(int i){
        T s=0;
        while(i>0){
            s+=bit[i];
            i-=(i&(-i));
        }
        return s;
    }
    void add(int i, T x){
        while(i<=size){
            bit[i]+=x;
            i+=(i&(-i));
        }
    }
};
int main()
{
    int n, q;
	string s;
	cin>>n>>s>>q;
	vector<BIT<int>> bit(26, BIT<int>(n));
	for(int i=0; i<n; i++){
		bit[s[i]-'a'].add(i+1, 1);
	}
	for(int i=0; i<q; i++){
		int t;
		cin>>t;
		if(t==1){
			int k; char c;
			cin>>k>>c;
			bit[s[k-1]-'a'].add(k, -1);
			bit[c-'a'].add(k, 1);
			s[k-1]=c;
		}else{
			int l, r; cin>>l>>r;
			int ans=0;
			for(int j=0; j<26; j++){
				if(bit[j].sum(r)-bit[j].sum(l-1)>0) ans++;
			}
			printf("%d\n", ans);
		}
	}

	return 0;
}

Submission Info

Submission Time
Task E - Simple String Queries
User chocorusk
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1464 Byte
Status AC
Exec Time 180 ms
Memory 53696 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 1 ms 256 KB
01-handmade-00 AC 118 ms 53636 KB
01-handmade-01 AC 1 ms 256 KB
01-handmade-02 AC 86 ms 53636 KB
01-handmade-03 AC 180 ms 53636 KB
01-handmade-04 AC 120 ms 53636 KB
01-handmade-05 AC 114 ms 53636 KB
01-handmade-06 AC 134 ms 53636 KB
01-handmade-07 AC 119 ms 53636 KB
01-handmade-08 AC 106 ms 53696 KB
01-handmade-09 AC 122 ms 53636 KB
01-handmade-10 AC 105 ms 53636 KB
01-handmade-11 AC 106 ms 53636 KB
02-small-00 AC 17 ms 256 KB
02-small-01 AC 23 ms 256 KB
02-small-02 AC 19 ms 256 KB
02-small-03 AC 27 ms 256 KB
02-small-04 AC 16 ms 384 KB
02-small-05 AC 16 ms 256 KB
02-small-06 AC 28 ms 256 KB
02-small-07 AC 19 ms 256 KB
02-small-08 AC 19 ms 256 KB
02-small-09 AC 18 ms 256 KB
02-small-10 AC 28 ms 256 KB
02-small-11 AC 16 ms 256 KB
02-small-12 AC 16 ms 256 KB
02-small-13 AC 27 ms 256 KB
02-small-14 AC 23 ms 256 KB
02-small-15 AC 22 ms 256 KB
02-small-16 AC 21 ms 256 KB
02-small-17 AC 17 ms 256 KB
02-small-18 AC 21 ms 256 KB
02-small-19 AC 24 ms 256 KB
03-large-00 AC 132 ms 53636 KB
03-large-01 AC 135 ms 53636 KB
03-large-02 AC 134 ms 53636 KB
03-large-03 AC 134 ms 53636 KB
03-large-04 AC 134 ms 53636 KB
03-large-05 AC 134 ms 53636 KB
03-large-06 AC 134 ms 53636 KB
03-large-07 AC 134 ms 53636 KB
03-large-08 AC 132 ms 53636 KB
03-large-09 AC 135 ms 53636 KB