contest3.G.cpp

#include <iostream>
#include <vector>

using namespace std;

#define MAXN (1ll << 54)
#define MOD 1000000007
#define INF 0x3FFFFFFFFFFFFFFF

inline long long sum_under(long long X) {
  X %= MOD;
  return (X * (X + 1) / 2) % MOD;
}

inline long long mtweak(long long X) {
  if (X < 0) X += MOD;
  if (X >= MOD) X -= MOD;
  return X;
}

struct agg {
  agg() : mx(-INF), mn(INF), sm(0) {
  }

  agg operator+(const agg& rhs) const {
    agg res;
    res.mn = min(mn, rhs.mn);
    res.mx = max(mx, rhs.mx);
    res.sm = mtweak(sm + rhs.sm);
    return res;
  }

  long long mn;
  long long mx;
  long long sm;
};

struct node {
  node(long long A, long long B) : lft(NULL), rht(NULL), lazyadd(0) {
    x.mx = B;
    x.mn = A + 1;
    x.sm = mtweak(sum_under(B) - sum_under(A));
  }

  node* lft;
  node* rht;

  long long lazyadd;
  agg x;
};

agg query(node* nd, long long A, long long B, long long a, long long b,
          long long v) {
  if (b <= A || B <= a) return agg();
  if (a <= A && B <= b) {
    agg result = nd->x;
    nd->lazyadd += v;
    nd->x.mn += v;
    nd->x.mx += v;
    nd->x.sm = (nd->x.sm + ((B - A) % MOD) * (v % MOD)) % MOD;
    return result;
  }

  long long M = (B + A) / 2;
  if (!nd->lft) nd->lft = new node(A, M);
  if (!nd->rht) nd->rht = new node(M, B);

  if (nd->lazyadd) {
    query(nd->lft, A, M, A, M, nd->lazyadd);
    query(nd->rht, M, B, M, B, nd->lazyadd);
    nd->lazyadd = 0;
  }

  agg result = query(nd->lft, A, M, a, b, v);
  result = result + query(nd->rht, M, B, a, b, v);
  nd->x = nd->lft->x + nd->rht->x;
  return result;
}

static long long V, X, Y, Z;

static long long get_next() {
  long long tmp = V * X + Y;
  V = tmp % Z;
  return tmp;
}

static void add_seed(long long S) {
  V = (V * S) % Z;
}

int main() {
  long long N, M;
  cin >> N >> M;
  cin >> V >> X >> Y >> Z;

  node root(0, MAXN);
  for(int i = 0; i < M; i++) {
    long long x = get_next() % N;
    long long y = get_next() % N;
    long long v = get_next() % (2 * Z + 1) - Z;
    if (y < x) swap(x, y);
    y++;

    agg result = query(&root, 0, MAXN, x, y, v);
    cout << result.sm << ' ' << result.mn << ' ' << result.mx << '\n';
    add_seed(result.sm);
  }

  return 0;
}