fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #define N_KEYS 9
  5.  
  6. using namespace std;
  7. typedef vector<int> vi;
  8.  
  9. struct node {
  10.     // node.sum(delta) = sum of properties in path root to node
  11.     // 1) leaf value = mod_n_keys(leaf.sum(delta))
  12.     // 2) node index 0 = mod_n_keys(node.sum(delta))
  13.     int delta, last_calculated_shift;
  14.     vi freq;
  15.  
  16.     node() : delta(0) {
  17.         freq.resize(N_KEYS);
  18.     }
  19. };
  20.  
  21. int N;
  22. vector<node> tree;
  23.  
  24. void print_sequence(int idx, int start, int end, int delta) {
  25.     int value = delta + tree[idx].delta;
  26.  
  27.     if (start == end) {
  28.         cout << value % N_KEYS << endl;
  29.         return;
  30.     }
  31.  
  32.     int mid = (start + end) >> 1;
  33.     print_sequence(idx*2+1, start, mid, value);
  34.     print_sequence(idx*2+2, mid+1, end, value);
  35. }
  36.  
  37. int mod_n_keys(int v) {
  38.     v %= N_KEYS;
  39.     if (v < 0) {
  40.         v += N_KEYS;
  41.     }
  42.     return v;
  43. }
  44.  
  45. void frequency(int idx, int start, int end, int A, int B, vi &frequencies, int shift, vi &nodes) {
  46.     if (A > end || B < start) {
  47.         return;
  48.     }
  49.  
  50.     node &x = tree[idx];
  51.     shift += x.delta;
  52.     x.last_calculated_shift = shift;
  53.  
  54.     // if [A,B] contains [start,end]
  55.     if (start >= A && end <= B) {
  56.         vi &arr = x.freq;
  57.  
  58.         for (int i=0; i<N_KEYS; i++) {
  59.             frequencies[i] += arr[mod_n_keys(i - shift)];
  60.         }
  61.  
  62.         nodes.push_back(idx);
  63.         return;
  64.     }
  65.  
  66.     int mid = (start + end) >> 1;
  67.     frequency(idx*2+1, start, mid, A, B, frequencies, shift, nodes);
  68.     frequency(idx*2+2, mid+1, end, A, B, frequencies, shift, nodes);
  69. }
  70.  
  71. int index_max_element(vi &f) {
  72.     int ans = 0;
  73.     for (int i=1, l=N_KEYS; i<l; i++) {
  74.         if (f[i] >= f[ans]) {
  75.             ans = i;
  76.         }
  77.     }
  78.     return ans;
  79. }
  80.  
  81. void updateUpward(int idx, vi &diff) {
  82.     if (idx == 0) return;
  83.     idx = (idx-1)/2;
  84.     node &p = tree[idx];
  85.     vi &arr = p.freq;
  86.  
  87.     for (int i=0; i<N_KEYS; i++) {
  88.         arr[mod_n_keys(i - p.last_calculated_shift)] += diff[i];
  89.     }
  90.  
  91.     updateUpward(idx, diff);
  92. }
  93.  
  94. void update(vi &nodes, int most_freq_note) {
  95.     for (int j=0, q=nodes.size(); j<q; j++) {
  96.         int idx = nodes[j];
  97.         node &x = tree[idx];
  98.         vi &arr = x.freq;
  99.  
  100.         // set the difference of frequencies after this update
  101.         vi diff(N_KEYS);
  102.         for (int i=0; i<N_KEYS; i++) {
  103.  
  104.             int y = mod_n_keys(i - x.last_calculated_shift); // arr[y] = valueAt_i
  105.             int newValueAt_i = arr[mod_n_keys(y - most_freq_note)];
  106.  
  107.             diff[i] = newValueAt_i - arr[y];
  108.         }
  109.  
  110.         // update node decoration
  111.         x.delta += most_freq_note;
  112.  
  113.         // propagate "diff" difference array upwards
  114.         updateUpward(idx, diff);
  115.     }
  116. }
  117.  
  118. void initial_values(int idx, int start, int end) {
  119.     int range = end - start + 1;
  120.     tree[idx].freq[1] = range; // Initially all notes are 1
  121.  
  122.     if (range > 1) {
  123.         int mid = (start + end) >> 1;
  124.         initial_values(idx*2+1, start, mid);
  125.         initial_values(idx*2+2, mid+1, end);
  126.     }
  127. }
  128.  
  129. void setup(int N) {
  130.     int size = 2 * pow(2, ceil(log2(N))) - 1;
  131.     tree.resize(size);
  132.  
  133.     initial_values(0, 0, N-1);
  134. }
  135.  
  136. int main() {
  137.     ios_base::sync_with_stdio(false);
  138.     cin.tie(0);
  139.  
  140.     int Q;
  141.     cin >> N >> Q;
  142.     setup(N);
  143.  
  144.     while (Q--) {
  145.         int A, B;
  146.         cin >> A >> B;
  147.  
  148.         vi freq(N_KEYS, 0);
  149.         vi nodes;
  150.         frequency(0, 0, N-1, A, B, freq, 0, nodes);
  151.  
  152.         int most_freq_note = index_max_element(freq);
  153.         if (most_freq_note) update(nodes, most_freq_note);
  154.     }
  155.  
  156.     print_sequence(0, 0, N-1, 1);
  157.     return 0;
  158. }
  159.  
Success #stdin #stdout 0s 16056KB
comments (?)
stdin
copy 
15 15
10 12
4 5
1 14
6 10
9 11
11 12
9 13
8 9
5 7
11 13
8 10
11 12
11 13
8 14
3 9
stdout
copy 
1
2
2
1
2
6
7
7
8
6
4
4
8
0
4
https://ideone.com/GwxGyZ
language:
C++ (gcc 8.3)
created:
6 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!