fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty