Problem: today_is_gonna_be_a_great_day (2023 round1)

*This could possibly be the best day ever!
And the forecast says that tomorrow will likely be a billion and 6 times better.
So make every minute count, jump up, jump in, and seize the day,
And let's make sure that in every single possible way… today is gonna be a great day!*

There's \(N\) days of summer vacation, and the \(i\)th day initially has greatness \(A_i\). However, the days just keep getting better! In particular, there will be \(Q\) changes, the \(i\)th of which changes the greatness of every day from \(L_i\) to \(R_i\) to be \(1\,000\,000\,006\) times what they were before!

After each query, you'd like to know: which day's greatness modulo \(1\,000\,000\,007\) is the largest? If multiple days tie, we're interested in the earliest of them. For example, if there are \(N = 4\) days with greatnesses \([4, 1, 4, 2]\), then days \(1\) and \(3\) have the largest remainder, so our answer would be \(1\). To keep the output size small, please print only the sum of answers to all queries.

**Constraints**

\(1 \le T \le 45\)
\(1 \le N \le 1{,}000{,}004\)
\(1 \le A_i \le 1{,}000{,}000{,}006\)
\(1 \le Q \le 500{,}000\)
\(1 \le L_i \le R_i \le N\)

The sum of \(N\) across all test cases is at most \(3{,}000{,}000\).

**Input Format**

Input begins with a single integer \(T\), the number of test cases. For each case, there is first a line containing a single integer \(N\). Then, there is a line containing \(N\) space-separated integers \(A_1, ..., A_N\). Then, there is a line containing a single integer \(Q\). \(Q\) lines follow, the \(i\)th of which contains two space-separated integers \(L_i\) and \(R_i\).

**Output Format**

For the \(i\)th test case, print a single line containing "`Case #i: `" followed by a single integer, the sum of the greatest day(s) after each of the \(Q\) queries.

**Sample Explanation**

In the first test case, there are \(N=3\) days with initial greatnesses of \([1, 20, 30]\). The first query modifies all \(3\) days, transforming their greatnesses \([1\,000\,000\,006, 999\,999\,987, 999\,999\,977]\), where the maximum is on day \(1\). After the second query, day \(3\) will have the largest greatness of \(999\,999\,977\). The overall answer is the sum of the greatest days, which is \(1 + 3 = 4\).



Sample input:
2
3
1 20 30
2
1 3
1 2
2
1 1
1
1 2


Sample output:
Case #1: 4
Case #2: 1


Solution: The key insight is that for the operation of multiplying a number \(x\) by \(1{,}000{,}000{,}006\) modulo \(1{,}000{,}000{,}007\), doing it twice will just get us \(x\) back again. Therefore, the \(i\)th day will only ever take on two greatness values: \(A_i\) and \((A_i * 1{,}000{,}000{,}006) \text{ mod } 1{,}000{,}000{,}007\). We can consider an update of \(L_i..R_i\) to be "flipping" every value in the range to their complementary value.

Let's build a [segment tree](https://en.wikipedia.org/wiki/Segment_tree) on the array. Each node is responsible for some subarray \(A_{l..r}\) and will maintain the following information:

* the maximum greatnesses value in that range (i.e. the current greatnesses)
* the day (index) of said maximum value
* the maximum of the flipped greatnesses in that range (i.e. what the greatnesses will become after an update)
* the day (index) of said flipped maximum

When merging two child nodes to a parent, we set the max initial value in the parent node to be the max of the children's initial values, breaking ties by lowest day index. Likewise for the flipped max and index.

Using the well-known lazy propagation technique, we can update ranges in time \(\mathcal{O}(\log N)\). For each node affected by an update, we can simply swap the first two fields with the last two. After each update, we can query the entire array (just access the root node) for the day of the current maximum greatness.

Across \(Q\) queries, we get an overall running time of \(\mathcal{O}(Q \log N)\).


Code: #include <iostream>
#include <vector>
using namespace std;

const long long MOD = (int)1e9 + 7;

struct Node {
  long long maxval, maxflip;
  int idx_of_maxval, idx_of_maxflip;

  Node() {}
  Node(int i, long long v):
    maxval(v), idx_of_maxval(i),
    maxflip(((long long)v * (MOD - 1)) % MOD), idx_of_maxflip(i) {}
};

template<class T, class D>
class segment_tree {
  static T join_values(const T &a, const T &b) {
    Node res;
    if (a.maxval > b.maxval ||
        (a.maxval == b.maxval && a.idx_of_maxval < b.idx_of_maxval)) {
      res.maxval = a.maxval;
      res.idx_of_maxval = a.idx_of_maxval;
    } else {
      res.maxval = b.maxval;
      res.idx_of_maxval = b.idx_of_maxval;
    }
    if (a.maxflip > b.maxflip ||
        (a.maxflip == b.maxflip && a.idx_of_maxflip < b.idx_of_maxflip)) {
      res.maxflip = a.maxflip;
      res.idx_of_maxflip = a.idx_of_maxflip;
    } else {
      res.maxflip = b.maxflip;
      res.idx_of_maxflip = b.idx_of_maxflip;
    }
    return res;
  }

  static void join_value_with_delta(T &v, const D &d, int len) {
    if (d) {  // Flip all values in v.lo .. v.hi.
      swap(v.maxval, v.maxflip);
      swap(v.idx_of_maxval, v.idx_of_maxflip);
    }
  }

  static D join_deltas(const D &d1, const D &d2) {
    return d1 ^ d2;
  }

  int len;
  std::vector<T> value;
  std::vector<D> delta;
  std::vector<bool> pending;

  template<class It>
  void build(int i, int lo, int hi, It arr) {
    if (lo == hi) {
      value[i] = Node(lo, *(arr + lo));
      return;
    }
    int mid = lo + (hi - lo)/2;
    build(i*2 + 1, lo, mid, arr);
    build(i*2 + 2, mid + 1, hi, arr);
    value[i] = join_values(value[i*2 + 1], value[i*2 + 2]);
  }

  void push_delta(int i, int lo, int hi) {
    if (pending[i]) {
      join_value_with_delta(value[i], delta[i], hi - lo + 1);
      if (lo != hi) {
        int l = 2*i + 1, r = 2*i + 2;
        delta[l] = pending[l] ? join_deltas(delta[l], delta[i]) : delta[i];
        delta[r] = pending[r] ? join_deltas(delta[r], delta[i]) : delta[i];
        pending[l] = pending[r] = true;
      }
      pending[i] = false;
    }
  }

  T query(int i, int lo, int hi, int tgt_lo, int tgt_hi) {
    push_delta(i, lo, hi);
    if (lo == tgt_lo && hi == tgt_hi) {
      return value[i];
    }
    int mid = lo + (hi - lo)/2;
    if (tgt_lo <= mid && mid < tgt_hi) {
      return join_values(
                query(i*2 + 1, lo, mid, tgt_lo, std::max(tgt_hi, mid)),
                query(i*2 + 2, mid + 1, hi, std::max(tgt_lo, mid + 1), tgt_hi));
    }
    if (tgt_lo <= mid) {
      return query(i*2 + 1, lo, mid, tgt_lo, std::min(tgt_hi, mid));
    }
    return query(i*2 + 2, mid + 1, hi, std::max(tgt_lo, mid + 1), tgt_hi);
  }

  void update(int i, int lo, int hi, int tgt_lo, int tgt_hi, const D &d) {
    push_delta(i, lo, hi);
    if (hi < tgt_lo || lo > tgt_hi) {
      return;
    }
    if (tgt_lo <= lo && hi <= tgt_hi) {
      delta[i] = d;
      pending[i] = true;
      push_delta(i, lo, hi);
      return;
    }
    update(2*i + 1, lo, (lo + hi)/2, tgt_lo, tgt_hi, d);
    update(2*i + 2, (lo + hi)/2 + 1, hi, tgt_lo, tgt_hi, d);
    value[i] = join_values(value[2*i + 1], value[2*i + 2]);
  }

 public:
  template<class It>
  segment_tree(It lo, It hi)
      : len(hi - lo), value(4*len), delta(4*len), pending(4*len, false) {
    build(0, 0, len - 1, lo);
  }

  int size() const { return len; }
  T query(int lo, int hi) { return query(0, 0, len - 1, lo, hi); }
  void update(int i, const D &d) { update(0, 0, len - 1, i, i, d); }
  void update(int lo, int hi, const D &d) { update(0, 0, len - 1, lo, hi, d); }
};

long long solve() {
  int N, Q;
  cin >> N;
  vector<long long> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  segment_tree<Node, bool> S(A.begin(), A.end());
  long long ans = 0;
  cin >> Q;
  for (int i = 0, l, r; i < Q; i++) {
    cin >> l >> r;
    l--;
    r--;
    S.update(l, r, 1);
    ans += S.query(0, N - 1).idx_of_maxval+1;
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}