//code by p1ckle/sft/yukicoder //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") //#pragma GCC target("avx,avx2") #include #define int long long int #define F first #define X first #define S second #define Y second #define mid ((start+end)/2) #define all(x) x.begin(), x.end() #define ub(a, b) upper_bound(all(a), b) - a.begin() #define lb(a, b) lower_bound(all(a), b) - a.begin() #define forf(a, b, c) for (int a = b; a <= c; a++) #define ford(a, b, c) for (int a = b; a < c; a++) #define forp(a, b) for (int a : b) #define pb push_back #define endl '\n' using namespace std; typedef vector vi; typedef pair pii; typedef vector> vpii; typedef long double ld; const int inf = 1e18, mod = 1e9+7; vpii dr4 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, dr8 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}}; int n, q; char c[250003]; unordered_map mp; array seg[1000003]; int pw[250003]; vector vs = {"ROCK", "ROC", "RO", "R", "OCK", "OC", "O", "CK", "C", "K"}; array merge(array l, array r) { array tmp; tmp[10] = l[10] + r[10]; tmp[0] = (l[0] + l[1]*r[9] + l[2]*r[7] + l[3]*r[4] + pw[l[10]]*r[0])%mod; tmp[1] = (l[1] + l[2]*r[8] + l[3]*r[5] + pw[l[10]]*r[1])%mod; tmp[2] = (l[2] + l[3]*r[6] + pw[l[10]]*r[2])%mod; tmp[3] = (l[3] + pw[l[10]]*r[3])%mod; tmp[4] = (l[4] + l[5]*r[9] + l[6]*r[7] + r[4])%mod; tmp[5] = (l[5] + l[6]*r[8] + r[5])%mod; tmp[6] = (l[6] + r[6])%mod; tmp[7] = (l[7] + l[8]*r[9] + r[7])%mod; tmp[8] = (l[8] + r[8])%mod; tmp[9] = (l[9] + r[9])%mod; return tmp; } void init(int start, int end, int idx) { if (start == end) { seg[idx][10] = 1; string ts = {}; ts += c[start]; if (mp.find(ts) != mp.end()) seg[idx][mp[ts]]++; return; } init(start, mid, idx*2); init(mid+1, end, idx*2+1); seg[idx] = merge(seg[idx*2], seg[idx*2+1]); } void updt(int start, int end, int idx, int tgt, char val) { if (start == end) { string ts = {}; ts += c[start]; if (mp.find(ts) != mp.end()) seg[idx][mp[ts]]--; c[start] = val; ts.clear(); ts += c[start]; if (mp.find(ts) != mp.end()) seg[idx][mp[ts]]++; return; } if (start > tgt || end < tgt) return; updt(start, mid, idx*2, tgt, val); updt(mid+1, end, idx*2+1, tgt, val); seg[idx] = merge(seg[idx*2], seg[idx*2+1]); } array query(int start, int end, int idx, int left, int right) { if (start > right || end < left) return {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; if (start >= left && end <= right) return seg[idx]; return merge(query(start, mid, idx*2, left, right), query(mid+1, end, idx*2+1, left, right)); } int a, b; char d; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); pw[0] = 1; forf (i, 1, 250000) pw[i] = (pw[i-1]*2)%mod; ford (i, 0, 10) mp.insert({vs[i], i}); cin >> n; forf (i, 1, n) cin >> c[i]; init(1, n, 1); cin >> q; while (q--) { cin >> a; if (a == 1) { cin >> b >> d; updt(1, n, 1, b, d); } else { cin >> a >> b; cout << query(1, n, 1, a, b)[0]%mod << endl; } } }

제출 #142504

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: