fork download
copy 
  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
comments (?)
stdin
copy 
20 139 5 7
E 1 12
E 2 14
E32
E42
E54
H25
E 2 14
0 0 0 0
stdout
copy 
-
https://ideone.com/TStVLu
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!