https://twitter.com/takesyhi_rs/status/1428258934704402439

Advanced Imos.cpp

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/segtree>
using namespace atcoder;
#define rep(i, l, r) for (auto i = (l); i < (r); i++)
#define all(a) a.begin(), a.end()
#define chmin(dest, src) if ((dest) > (src)) dest = (src)
#define chmax(dest, src) if ((dest) < (src)) dest = (src)
using ll = int;

const ll MOD = 1000000007;

struct S {
  ll mul; // 掛ける
  ll add; // 足す
};

S op(S f, S g) {
  return {f.mul * g.mul % MOD, (f.mul * g.add + f.add) % MOD};
}

S e() {
  return {1, 0};
}

struct Query {
  int index;
  int L;
  ll X;
  ll Y;
};

int main() {
  int N, Q; cin >> N >> Q;
  vector<ll> a(N);
  rep (i, 0, N) cin >> a[i];
  vector<Query> queries(Q);
  rep (i, 0, Q) {
    int L; ll X, Y; cin >> L >> X >> Y; L--;
    queries[i] = {i, L, X, Y};
  }

  // クエリを L の昇順にソート
  sort(all(queries), [](Query f, Query g) { return f.L == g.L ? f.index < g.index : f.L < g.L; });
  int q = 0;
  
  // セグ木を初期化
  segtree<S, op, e> seg(Q);

  // 平面走査
  rep (i, 0, N) {
    while (q < Q && queries[q].L <= i) {
      seg.set(Q - 1 - queries[q].index, { queries[q].X, queries[q].Y });
      q++;
    }

    S f = seg.all_prod();
    cerr << f.mul << "\t" << f.add << endl;
    a[i] = (f.mul * a[i] + f.add) % MOD;
    if (a[i] < 0) a[i] += MOD;
  }
  
  rep (i, 0, N) {
    if (i) cout << " ";
    cout << a[i];
  }
  cout << endl;
  
  return 0;
}