fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
  5. #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
  6. #define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
  7. #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  8. #define SZ(S) ((int) ((S).size()))
  9.  
  10. #define DEBUG(x) { cout << #x << " = " << x << endl; }
  11. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  12. #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
  13.  
  14. const int MN = 100111;
  15. long long it[MN * 4];
  16. long long power[MN];
  17.  
  18. int b, MOD, l, n;
  19.  
  20. long long add(long long a, long long b, long long len) {
  21. return (a*power[len] + b) % MOD;
  22. }
  23.  
  24. #define CT(X) ((X) << 1)
  25. #define CP(X) (CT(X) + 1)
  26. #define MID ((l + r) >> 1)
  27. void update(int i, int l, int r, int u, long long val) {
  28. if (u < l || r < u) return ;
  29. if (l == r) { it[i] = val; return ; }
  30. update(CT(i), l, MID, u, val);
  31. update(CP(i), MID+1, r, u, val);
  32.  
  33. it[i] = add(it[CT(i)], it[CP(i)], r - MID);
  34. }
  35.  
  36. vector< pair<long long, pair<int,int> > > all;
  37. void visit(int i, int l, int r, int u, int v) {
  38. if (v < l || r < u) return ;
  39. if (u <= l && r <= v) {
  40. all.push_back(make_pair(it[i], make_pair(l, r)));
  41. return ;
  42. }
  43. visit(CT(i), l, MID, u, v);
  44. visit(CP(i), MID+1, r, u, v);
  45. }
  46. long long get(int u, int v) {
  47. all.clear();
  48. visit(1, 1, l, u, v);
  49. int len = 0;
  50. long long res = 0;
  51. FORD(i,all.size()-1,0) {
  52. res = add(all[i].first, res, len);
  53. len += all[i].second.second - all[i].second.first + 1;
  54. }
  55. return res;
  56. }
  57.  
  58. int main() {
  59. ios :: sync_with_stdio(false); cin.tie(NULL);
  60. cout << (fixed) << setprecision(6);
  61. while (cin >> b >> MOD >> l >> n && b) {
  62. power[0] = 1;
  63. FOR(i,1,l) power[i] = power[i-1] * b % MOD;
  64.  
  65. memset(it, 0, sizeof it);
  66. while (n--) {
  67. char typ; cin >> typ;
  68. if (typ == 'E') {
  69. int u, val; cin >> u >> val;
  70. update(1, 1, l, u, val);
  71. }
  72. else {
  73. int u, v; cin >> u >> v;
  74. cout << get(u, v) << "\n";
  75. }
  76. }
  77. cout << "-\n";
  78. }
  79. return 0;
  80. }
  81.  
  82.  
Success #stdin #stdout 0s 7344KB
stdin
20 139 5 7
E 1 12
E 2 14
E32
E42
E54
H25
E 2 14
0 0 0 0
stdout
-