fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename T>
  5. void out(T x) { cout << x << endl; exit(0); }
  6. #define watch(x) cout << (#x) << " is " << (x) << endl
  7.  
  8.  
  9.  
  10.  
  11. using ll = long long;
  12. const ll mod = 1e9+7;
  13. const int maxn = 1e5 + 5;
  14.  
  15.  
  16. using matrix = array<ll,4>;
  17.  
  18. void add(ll& x, ll y) {
  19.     if (x>=mod) x%=mod;
  20.     if (y>=mod) y%=mod;
  21.     x += y;
  22.     if (x>=mod) x%=mod;
  23. }
  24.  
  25. void mul(ll& x, ll y) {
  26.     if (x>=mod) x%=mod;
  27.     if (y>=mod) y%=mod;
  28.     long long tmp = 1ll*x*y;
  29.     tmp %= mod;
  30.     x = tmp;
  31. }
  32.  
  33. ll addr(ll x, ll y) {
  34.     if (x>=mod) x%=mod;
  35.     if (y>=mod) y%=mod;
  36.     x += y;
  37.     if (x>=mod) x%=mod;
  38.     return x;
  39. }
  40.  
  41. ll mulr(ll x, ll y) {
  42.     if (x>=mod) x%=mod;
  43.     if (y>=mod) y%=mod;
  44.     long long tmp = 1ll*x*y;
  45.     tmp %= mod;
  46.     return tmp;
  47. }
  48.  
  49.  
  50.  
  51. matrix mul(matrix a, matrix b) {
  52.     matrix res;
  53.     res[0]=addr(mulr(a[0],b[0]),mulr(a[1],b[2]));
  54.     res[1]=addr(mulr(a[0],b[1]),mulr(a[1],b[3]));
  55.     res[2]=addr(mulr(a[2],b[0]),mulr(a[3],b[2]));
  56.     res[3]=addr(mulr(a[2],b[1]),mulr(a[3],b[3]));
  57.     return res;    
  58. }
  59.  
  60.  
  61. matrix id2() {
  62.     return {1,0,0,1};
  63. }
  64.  
  65. matrix matA() {
  66.     // 1 1
  67.     // 0 1
  68.     return {1,1,0,1};
  69. }
  70.  
  71. matrix matB() {
  72.     // 1 0
  73.     // 1 1
  74.     return {1,0,1,1};
  75. }
  76.  
  77. void flip(matrix& M) {
  78.     M = {M[3],M[2],M[1],M[0]};
  79. }
  80.  
  81.  
  82. int n, q;
  83. string s;
  84.  
  85. using node = matrix;
  86.  
  87. node t[4*maxn];
  88. bool o[4*maxn];
  89.  
  90. node merge(node a, node b) {
  91.     return mul(b, a);
  92. }
  93.  
  94. void build(int v, int tl, int tr) {
  95.     if (tl==tr) {
  96. 	t[v] = s[tl] == 'A' ? matA() : matB();
  97.     } else {
  98. 	int tm=(tl+tr)/2;
  99. 	build(2*v,tl,tm);
  100. 	build(2*v+1,tm+1,tr);
  101. 	t[v] = merge(t[2*v], t[2*v+1]);
  102.     }
  103. }
  104.  
  105. void push(int v) {
  106.     if (!o[v]) return;
  107.     flip(t[2*v]);
  108.     flip(t[2*v+1]);
  109.     o[2*v]=!o[2*v];
  110.     o[2*v+1]=!o[2*v+1];
  111.     o[v]=false;
  112. }
  113.  
  114.  
  115. void flip(int v, int tl, int tr, int l, int  r) {
  116.     if (r<tl || l>tr) {
  117. 	return;
  118.     }
  119.     if (l<=tl && tr<=r) {
  120. 	flip(t[v]);
  121. 	o[v] = !o[v];
  122. 	return;
  123.     }
  124.     int tm=(tl+tr)/2;
  125.     push(v);
  126.     flip(2*v,tl,tm,l,r);
  127.     flip(2*v+1,tm+1,tr,l,r);
  128.     t[v]=merge(t[2*v],t[2*v+1]);
  129. }
  130.  
  131. matrix qry(int v, int tl, int tr, int l, int r) {
  132.     if (l>tr || r<tl) {
  133. 	return id2();
  134.     }
  135.     if (l<=tl && tr<=r) {
  136. 	return t[v];
  137.     }
  138.     int tm=(tl+tr)/2;
  139.     push(v);
  140.     return mul(qry(2*v+1,tm+1,tr,l,r), qry(2*v,tl,tm,l,r));
  141. }
  142.  
  143.  
  144.  
  145.  
  146. int main() {
  147.     ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  148.  
  149.     cin>>n>>q;
  150.     cin>>s;
  151.     s="."+s;
  152.     build(1,1,n);
  153.  
  154.     while (q--) {
  155. 	int typ;
  156. 	cin>>typ;
  157. 	if (typ==2) {
  158. 	    int l,r; ll a,b;
  159. 	    cin>>l>>r>>a>>b;
  160. 	    matrix M = qry(1,1,n,l,r);
  161. 	    ll resa = addr(mulr(M[0],a), mulr(M[1],b));
  162. 	    ll resb = addr(mulr(M[2],a), mulr(M[3],b));
  163. 	    cout<<resa<<" "<<resb<<"\n";
  164. 	}
  165. 	if (typ==1) {
  166. 	    int l,r;
  167. 	    cin>>l>>r;
  168. 	    flip(1,1,n,l,r);
  169. 	}
  170.     }
  171.  
  172.  
  173.     return 0;
  174. }
Internal error #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Vucvnt
language:
C++14 (gcc 8.3)
created:
3 years 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!