fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define endl '\n'
  4. #define f0(i,n) for(int i=0;i<n;++i)
  5. #define f1(i,n) for(int i=1;i<=n;++i)
  6. #define fi first
  7. #define se second
  8. #define pai pair<int,int>
  9. using namespace std;
  10. const int MOD=1e9+7;
  11. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  12. int rnd(int l,int r){
  13.     static uniform_int_distribution<int> d;
  14.     return d(rng,uniform_int_distribution<int>::param_type(l,r));
  15. }
  16. const int MAXN = 100005;
  17.  
  18. ll st[4 * MAXN];
  19. bool lazy_set[4 * MAXN];
  20. ll lazy_val[4 * MAXN];
  21.  
  22. int n;
  23. ll a[MAXN + 5];
  24. void build(int id, int l, int r) {
  25.     lazy_set[id] = false;
  26.     if (l == r) {
  27.         st[id] = a[l]-a[l-1];
  28.         return;
  29.     }
  30.     int mid = (l + r) >> 1;
  31.     build(id << 1, l, mid);
  32.     build(id << 1 | 1, mid + 1, r);
  33.     st[id] = st[id << 1] + st[id << 1 | 1];
  34. }
  35.  
  36. void push(int id, int l, int r) {
  37.     if (!lazy_set[id] || l == r) return;
  38.  
  39.     int mid = (l + r) >> 1;
  40.     ll v = lazy_val[id];
  41.  
  42.     st[id << 1] = (mid - l + 1) * v;
  43.     lazy_set[id << 1] = true;
  44.     lazy_val[id << 1] = v;
  45.  
  46.     st[id << 1 | 1] = (r - mid) * v;
  47.     lazy_set[id << 1 | 1] = true;
  48.     lazy_val[id << 1 | 1] = v;
  49.  
  50.     lazy_set[id] = false;
  51. }
  52. void update1(int id, int l, int r, int u, int v, ll val) {
  53.     if (r < u || v < l) return;
  54.  
  55.     if (u <= l && r <= v) {
  56.         st[id] = (r - l + 1) * val;
  57.         lazy_set[id] = true;
  58.         lazy_val[id] = val;
  59.         return;
  60.     }
  61.  
  62.     push(id, l, r);
  63.     int mid = (l + r) >> 1;
  64.     update1(id << 1, l, mid, u, v, val);
  65.     update1(id << 1 | 1, mid + 1, r, u, v, val);
  66.     st[id] = st[id << 1] + st[id << 1 | 1];
  67. }
  68. void update2(int id, int l, int r, int pos, ll val) {
  69.     if (l == r) {
  70.         st[id] = val;
  71.         lazy_set[id] = false;
  72.         return;
  73.     }
  74.  
  75.     push(id, l, r);
  76.     int mid = (l + r) >> 1;
  77.     if (pos <= mid) update2(id << 1, l, mid, pos, val);
  78.     else update2(id << 1 | 1, mid + 1, r, pos, val);
  79.     st[id] = st[id << 1] + st[id << 1 | 1];
  80. }
  81. ll query(int id, int l, int r, int u, int v) {
  82.     if (r < u || v < l) return 0;
  83.     if (u <= l && r <= v) return st[id];
  84.  
  85.     push(id, l, r);
  86.     int mid = (l + r) >> 1;
  87.     return query(id << 1, l, mid, u, v)
  88.          + query(id << 1 | 1, mid + 1, r, u, v);
  89. }
  90. int main(){
  91. 	//freopen(".INP","r",stdin);
  92. 	//freopen(".OUT","w",stdout);
  93.     ios_base::sync_with_stdio(false);
  94.     cin.tie(NULL); cout.tie(0);
  95.  
  96.     int n,q;
  97.     cin>>n>>q;
  98.     string s;
  99.     cin>>s;
  100.  
  101.     a[1]=1;
  102.     f1(i,n-1){
  103.     	if(s[i]!=s[i-1]) a[i+1]=a[i]+1;
  104.     	else a[i+1]=a[i];
  105. 	}
  106. 	build(1,1,n);
  107. 	while(q--){
  108. 		string t;
  109. 		cin>>t;
  110. 		if(t=="change"){
  111. 			int l,r;
  112. 			char c;
  113. 			cin>>l>>r>>c;
  114. 			if (l + 1 <= r) update1(1, 1, n, l + 1, r, 0);
  115.             if (l > 1) {
  116.                 ll v = (s[l-2] != c);
  117.                 update2(1, 1, n, l, v);
  118.             }
  119.             if (r < n) {
  120.                 ll v = (c != s[r]);
  121.                 update2(1, 1, n, r + 1, v);
  122.             }
  123.             for (int i = l-1; i <= r-1; i++) s[i] = c;
  124. 	    }
  125. 	    else { 
  126. 	        int l, r;
  127. 	        cin >> l >> r;
  128. 	        ll ans = 1;
  129. 	        if (l + 1 <= r) ans += query(1, 1, n, l + 1, r);
  130. 	        cout << ans <<endl;
  131. 	    }
  132.  
  133. 	}
  134.     return 0;
  135. }
  136.  
Success #stdin #stdout 0s 5568KB
comments (?)
stdin
copy 
11 5
GGBBBGGYRRR
get 1 11
get 3 9
get 4 7
change 4 8 B
get 1 11
stdout
copy 
5
4
2
3
https://ideone.com/TM5qF1
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!