#1080146 (C++23) No.3129 Multiple of Twin Subarray

提出ソース
結果

問題	No.3129 Multiple of Twin Subarray
ユーザー	zoidzium (zz)
提出日時	2025-04-25 22:28:13
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,118 ms / 2,000 ms
コード長	30,517 bytes
コンパイル時間	4,344 ms
コンパイル使用メモリ	314,328 KB
実行使用メモリ	37,744 KB
最終ジャッジ日時	2025-04-25 22:28:50
合計ジャッジ時間	35,455 ms
ジャッジサーバーID （参考情報）	judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 46
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vl = vector<ll>;
using vul = vector<ull>;
using vs = vector<string>;
using vvs = vector<vs>;
using vd = vector<double>;
using vvl = vector<vl>;
using vvd = vector<vd>;
using xy = pair<ll, ll>;
using vxy = vector<xy>;
using vvxy = vector<vxy>;
using vvvl = vector<vvl>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define cnt(i, n, m) for (ll i = (n); i <= (m); i++)
#define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;
#define square(a) ((a) * (a))
#define bfind(a, b) (((a) >> (b)) & 1ll)
#define bset(a, b, c) (((c) != 0) ? (a) | (1ll << (b)) : ~((~(a)) | (1 << (b))))
#define nth(a, b) (((a) >> (b)) & 1)

namespace zz_zout {
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline) {};

template <typename T>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const T& x) {
  if (showBit == 0) {
    cout << header << x << space << endline;
  } else {
    cout << header;
    bitset<64> bit(x);
    rep(i, showBit) cout << bit[i];
    cout << space << endline;
  }
};

template <typename E1, typename E2>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const pair<E1, E2>& x) {
  cout << header << "< ";
  out(showBit, 0, "", " ", "", x.first);
  out(showBit, 0, "", " ", "", x.second);
  cout << ">" << space << endline;
};

template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const vector<E>& x) {
  cout << header << "[" << space;
  if (Hier) cout << endline;
  for (E xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "]" << space << endline;
};

template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const set<E>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (E xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const multiset<E>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (E xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const unordered_set<E>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (E xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const unordered_multiset<E>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (E xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};

template <typename E1, typename E2>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const map<E1, E2>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (pair<E1, E2> xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E1, typename E2>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const multimap<E1, E2>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (pair<E1, E2> xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E1, typename E2>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const unordered_map<E1, E2>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (pair<E1, E2> xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};
template <typename E1, typename E2>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const unordered_multimap<E1, E2>& x) {
  cout << header << "{" << space;
  if (Hier) cout << endline;
  for (pair<E1, E2> xx : x) {
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "}" << space;
  if (Hier) cout << endline;
};

template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const stack<E>& x) {
  cout << header << "(" << space;
  if (Hier) cout << endline;
  stack<E> sta = x;
  while (!sta.empty()) {
    E xx = sta.top();
    sta.pop();
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "]" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const queue<E>& x) {
  cout << header << "(" << space;
  if (Hier) cout << endline;
  queue<E> que = x;
  while (!que.empty()) {
    E xx = que.front();
    que.pop();
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "]" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const deque<E>& x) {
  cout << header << "(" << space;
  if (Hier) cout << endline;
  deque<E> que = x;
  while (!que.empty()) {
    E xx = que.front();
    que.pop_front();
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << ")" << space;
  if (Hier) cout << endline;
};
template <typename E>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline,
         const priority_queue<E>& x) {
  cout << header << "(" << space;
  if (Hier) cout << endline;
  priority_queue<E> que = x;
  while (!que.empty()) {
    E xx = que.top();
    que.pop();
    if (Hier) {
      if (Hier > 0) {
        out(showBit, Hier - 1, header + "  ", space, endline, xx);
      }
    } else {
      out(showBit, 0, "", space, "", xx);
    }
  }
  if (Hier) cout << header;
  cout << "]" << space;
  if (Hier) cout << endline;
};

template <typename T, typename... U>
void out(const ll& showBit, const ll& Hier, const string& header,
         const string& space, const string& endline, const T& x,
         const U&... y) {
  out(showBit, Hier, header, space, endline, x);
  out(showBit, Hier, header, space, endline, y...);
};

void zout() { cout << endl; };
template <int Hier = 0, int showBit = 0, typename... T>
void zout(const T&... x) {
  string endline = "\n";
  if (Hier == 0) endline = "";
  out(showBit, Hier, "", "  ", endline, x...);
  if (Hier == 0) cout << endl;
};

}  // namespace zz_zout
using namespace zz_zout;

namespace zz_time {
std::chrono::_V2::system_clock::time_point START_TIME =
    std::chrono::system_clock::now();

ll currentTime(std::chrono::_V2::system_clock::time_point st = START_TIME) {
  std::chrono::_V2::system_clock::time_point now =
      std::chrono::system_clock::now();
  return (ll)(std::chrono::duration_cast<std::chrono::milliseconds>(now - st)
                  .count());
};
};  // namespace zz_time
using namespace zz_time;

namespace zz_random {
std::random_device RANDOM_DEVICE;
std::mt19937 RANDOM_MT;
void setSeed(const ll& seed = RANDOM_DEVICE()) {
  RANDOM_MT = std::mt19937(seed);
};

std::uniform_int_distribution<int> createIntDistribution(const ll& L = 0,
                                                         const ll& R = 1) {
  return std::uniform_int_distribution<int>(L, R);
};
std::uniform_real_distribution<double> createDoubleDistribution(
    const double& L = 0.0, const double& R = 1.0) {
  return std::uniform_real_distribution<double>(L, R);
};
std::normal_distribution<double> createNormalDistribution(
    const double& average = 0.0, const double& standard_deviation = 1.0) {
  return std::normal_distribution<double>(average, standard_deviation);
}
bool getProbability(const double& p = 0.5) {
  return (createDoubleDistribution()(RANDOM_MT) <= 0.5);
}
};  // namespace zz_random
using namespace zz_random;

namespace zz_modulo {
class pp {
 public:
  ll e = 0;
  ll mod = 2;
  ll inv = 0;

  pp& operator=(const pp& x);
  pp operator+();
  pp operator-();
  template <typename T>
  pp& operator+=(const T& y);
  template <typename T>
  pp& operator-=(const T& y);
  template <typename T>
  pp& operator*=(const T& y);
  template <typename T>
  pp& operator/=(T& y);
  ll exp(ll x, ll I, ll modulo);
  pp exp(pp& x, ll I);
  pp exp(ll I);
  void cal_inv();
  pp inversion();
  string str() const;

  pp(const ll& elm = 0, const ll& modulo = 998244353, const ll& inversion = 0) {
    mod = modulo;
    e = elm;
    if (e < 0) {
      e = mod - ((-e) % mod);
    } else {
      e %= mod;
    }
    mod = modulo;
    if (inversion < 0) {
      cal_inv();
    } else if (inversion != 0) {
      inv = inversion;
    }
  };

  static vector<pp> create_vp(ll N, const ll& modulo);
  static pp chineseRemainderTheorem(vector<pp> vx);
  static pp garner(vector<pp> vx, const ll& mod);
};

pp& pp::operator=(const pp& x) {
  this->e = x.e;
  this->mod = x.mod;
  this->inv = x.inv;
  return *this;
};
pp operator+(const pp& x, const pp& y) {
  ll elm = x.e + y.e;
  if (elm > x.mod) elm -= x.mod;
  return pp(elm, x.mod);
};
template <typename T>
pp operator+(const pp& x, const T& y) {
  pp z(y, x.mod);
  return (x + z);
};
template <typename T>
pp operator+(const T& x, const pp& y) {
  pp z(x, y.mod);
  return (z + y);
};
template <typename T>
pp& pp::operator+=(const T& y) {
  *this = (*this) + y;
  return *this;
};

pp pp::operator+() { return *this; };

pp operator-(const pp& x, const pp& y) {
  ll elm = x.e - y.e;
  if (elm < 0) elm += x.mod;
  return pp(elm, x.mod);
};
template <typename T>
pp operator-(const pp& x, const T& y) {
  pp z(y, x.mod);
  return (x - z);
};
template <typename T>
pp operator-(const T& x, const pp& y) {
  pp z(x, y.mod);
  return (z - y);
};
template <typename T>
pp& pp::operator-=(const T& y) {
  *this = (*this) - y;
  return *this;
};

pp pp::operator-() { return (0 - (*this)); };

pp operator*(const pp& x, const pp& y) {
  return pp((x.e * y.e) % x.mod, x.mod, (x.inv * y.inv) % x.mod);
};
template <typename T>
pp operator*(const pp& x, const T& y) {
  pp z(y, x.mod);
  return (x * z);
};
template <typename T>
pp operator*(const T& x, const pp& y) {
  pp z(x, y.mod);
  return (z * x);
};
template <typename T>
pp& pp::operator*=(const T& y) {
  *this = (*this) * y;
  return *this;
};

pp operator/(const pp& x, pp& y) { return (x * y.inversion()); }
template <typename T>
pp operator/(const pp& x, T& y) {
  pp z(y, x.mod);
  return (x / z);
};
template <typename T>
pp operator/(const T& x, pp& y) {
  pp z(x, y.mod);
  return (z / y);
};
template <typename T>
pp& pp::operator/=(T& y) {
  *this = (*this) / y;
  return *this;
};

bool operator==(const pp& x, const pp& y) { return (x.e == y.e); }
template <typename T>
bool operator==(const T& x, const pp& y) {
  return (x == y.e);
};
template <typename T>
bool operator==(const pp& x, const T& y) {
  return (x.e == y);
};

bool operator!=(const pp& x, const pp& y) { return !(x == y); }
template <typename T>
bool operator!=(const T& x, const pp& y) {
  return !(x == y);
};
template <typename T>
bool operator!=(const pp& x, const T& y) {
  return !(x == y);
};

ll pp::exp(ll x, ll I, ll modulo) {
  ll y = 1;
  if (x < 0) {
    x = (modulo - ((-x) % modulo));
  } else {
    x %= modulo;
  }
  while (I > 0) {
    if (I & 1) {
      y = (y * x) % modulo;
    }
    x = (x * x) % modulo;
    I /= 2;
  };
  return y;
};

pp pp::exp(pp& x, ll I) {
  x.cal_inv();
  pp xx = x;
  pp y(1, xx.mod, 1);
  while (I > 0) {
    if (I & 1) {
      y = (y * xx);
    }
    xx = (xx * xx);
    I /= 2;
  };
  return y;
}

pp pp::exp(ll I) { return exp(*this, I); }

void pp::cal_inv() {
  if (this->inv <= 0) this->inv = exp(this->e, this->mod - 2, this->mod);
};

pp pp::inversion() {
  cal_inv();
  return pp(this->inv, this->mod, this->e);
}

string pp::str() const {
  return ("<epi " + to_string(e) + " \t" + to_string(mod) + " \t" +
          to_string(inv) + " >");
}

using vp = vector<zz_modulo::pp>;

vector<pp> pp::create_vp(ll N, const ll& modulo) {
  // m=m%i+m/i * i
  // 0- (m % i) = (m/i)*i
  cout << "!!" << endl;
  N = max<ll>(1, N);
  vector<pp> vec(N + 1);
  vec[0].e = 0;
  vec[0].mod = modulo;
  vec[0].inv = 1;
  vec[1].e = 1;
  vec[1].mod = modulo;
  vec[1].inv = 1;
  cnt(i, 2, N) {
    vec[i] = pp(i, modulo);
    cout << "@[" << i << "]=" << vec[i].str() << endl;
    cout << "---" << vec[modulo / i].str() << flush;
    cout << "  " << vec[modulo % i].str() << endl;
    vec[i].inv = (0 - ((modulo / i) * vec[modulo % i].inversion())).e;
    cout << " [" << i << "]=" << vec[i].str() << endl;
  }
  return vec;
};

pp chineseRemainderTheorem(vector<pp>& vx) {
  ll m = 1;
  each(ite, vx) m *= ite->mod;
  pp ans(0, m);
  each(ite, vx) {
    // ll Ai = R[i];
    // ll Mi = MMM / MM[i];
    // ll Ni = pp(Mi, MM[i]).inversion().e;

    // ANS += Ai * Mi * Ni;

    ll Ai = ite->e;
    ll Mi = m / ite->mod;
    ll Ni = pp(Mi, ite->mod, -1).inv;
    ans += pp(Ai * Mi * Ni, m);
    // zout(ans.str(), ite->str(), m, Ai, Mi, Ni);
  }

  return ans;
};

pp garner(vector<pp>& vx, const ll& mod) {
  ll N = vx.size();
  vector<vector<pp>> R(N, vector<pp>(N));
  rep(i, N) {
    cnt(j, i, N - 1) {
      if (i == j) {
        R[i][i] = vx[i].inversion();
      } else {
        R[i][j] = pp(vx[i].e, vx[j].mod, -1).inversion();
      }
      // zout("#ij=", i, j);
    }
  }
  vector<pp> X(N);
  rep(i, N) {
    X[i] = vx[i];
    rep(j, i) {
      // zout("ij=", i, j);
      X[i] = (X[i] - X[j].e) * R[j][i];
    }
    // cout << "x[" << i << "]=" << X[i].str() << endl;
  }
  // rep(i, N) zout(X[i].str());
  pp ANS(0, mod), P(1, mod);
  rep(i, N) {
    ANS += P.e * X[i].e;
    P *= vx[i].mod;
  }
  return ANS;
};

};  // namespace zz_modulo
using namespace zz_modulo;

namespace zz_prime {
class prime {
 public:
  static vl sieve;
  static vl p;
  static void set(ll N = 1000000) {
    N = max<ll>(2, N) + 1;
    sieve = vl(N, 0);
    p.clear();
    sieve[0] = 1;
    sieve[1] = 1;
    cnt(i, 2, N - 1) {
      if (sieve[i] == 0) {
        p.push_back(i);
        ll j = i;
        while (j < N) {
          if (sieve[j] == 0) sieve[j] = i;
          j += i;
        }
      }
    }
  };

  static bool isprime(ll x) {
    if (x <= 1) return false;
    if (sieve.empty()) set();
    if (x < sieve.size()) return (sieve[x] == x);
    each(ite, p) {
      if (x < (*ite) * (*ite)) return true;
      if ((x % (*ite)) == 0) return false;
    }
    return true;
  };

  static vxy factor(ll x) {
    x = max<ll>(1, x);
    if (sieve.empty()) set();

    map<ll, ll> MAP;
    each(ite, p) {
      if (x < sieve.size()) break;

      while ((x % (*ite)) == 0) {
        MAP[*ite]++;
        x /= *ite;
      }
    }

    if (x < sieve.size()) {
      while (x > 1) {
        MAP[sieve[x]]++;
        x /= sieve[x];
      }
    } else {
      MAP[x]++;
    }
    vxy fact;
    each(ite, MAP) fact.push_back(*ite);
    return fact;
  };

  static vl divisors(const vxy& fact) {
    vl ans(1, 1);
    function<void(const ll&, const ll&)> Func =
        [&fact, &ans, &Func](const ll& I, const ll& Elm) -> void {
      if (fact.empty()) return;
      ll Add = 1;

      if ((I + 1) < fact.size()) {
        Func(I + 1, Elm);
      } else {
        if (Elm != 1) ans.emplace_back(Elm);
      }

      cnt(i, 1, fact[I].second) {
        Add *= fact[I].first;
        if ((I + 1) < fact.size()) {
          Func(I + 1, Elm * Add);
        } else {
          ans.emplace_back(Elm * Add);
        }
      };
    };
    Func(0, 1);
    sort(ans.begin(), ans.end());
    return ans;
  };
};

vl prime::p;
vl prime::sieve;
}  // namespace zz_prime
using namespace zz_prime;

/////////////////////////////////////////////////
namespace lazeSegment {

template <class S, class F>
class lazySeg {
 private:
 public:
  vector<S> A;
  vector<F> B;
  vxy Rng;

 public:
  const ll N;
  const ll Size;

  lazySeg(ll n = 300000)
      : N([&n] {
          ll x = 1;
          while (x < n) x *= 2;
          return x;
        }()),
        Size(2 * N - 1) {
    A = vector<S>(Size, S::e());
    B = vector<F>(Size, F::id());
    Rng = vxy(Size);
    Rng[0] = make_pair(0, N);
    cnt(i, 1, Size - 1) {
      if (i % 2 == 1) {
        Rng[i] =
            make_pair(Rng[(i - 1) / 2].first,
                      (Rng[(i - 1) / 2].first + Rng[(i - 1) / 2].second) / 2);
      } else {
        Rng[i] =
            make_pair((Rng[(i - 1) / 2].first + Rng[(i - 1) / 2].second) / 2,
                      Rng[(i - 1) / 2].second);
      }
    }
  };

  template <typename... Arg>
  S s(Arg... arg) {
    return S(arg...);
  };
  template <typename... Arg>
  F f(Arg... arg) {
    return F(arg...);
  };

  S get(ll L, ll R, bool dbg = false) {
    S s = S::e();
    if (R <= L) return s;
    L = max<ll>(0, L);
    R = min<ll>(R, N);
    if (N <= L) return s;
    if (R <= 0) return s;
    function<void(const ll&)> Func = [this, &L, &R, &dbg, &s,
                                      &Func](const ll& at) {
      if (at < (N - 1)) {
        B[at * 2 + 1] = B[at] * B[at * 2 + 1];
        B[(at + 1) * 2] = B[at] * B[(at + 1) * 2];
      }
      A[at] = B[at] * A[at];
      B[at] = F::id();

      if ((R <= Rng[at].first) || (Rng[at].second <= L)) {
        if (dbg) cout << " 1 return" << endl;
        return;
      }
      if ((L <= Rng[at].first) && (Rng[at].second <= R)) {
        if (dbg) cout << " 2 in" << endl;
        s = A[at] * s;
      } else {
        if (dbg) cout << " 3 cross" << endl;
        Func((at + 1) * 2);
        Func(at * 2 + 1);
        A[at] = A[at * 2 + 1] * A[(at + 1) * 2];
      }
    };
    Func(0);

    return s;
  };

  void set(ll L, ll R, F Act, bool dbg = false) {
    if (dbg)
      cout << "set(" << L << " " << R << " " << Act.str() << " " << dbg << ")"
           << endl;
    if (R <= L) return;
    L = max<ll>(0, L);
    R = min<ll>(R, N);
    if (N <= L) return;
    if (R <= 0) return;

    function<void(const ll&)> Func = [this, &L, &R, &Act, &dbg,
                                      &Func](const ll& at) {
      if ((L <= Rng[at].first) && (Rng[at].second <= R)) {
        B[at] = Act * B[at];
      }
      if (at < (N - 1)) {
        B[at * 2 + 1] = B[at] * B[at * 2 + 1];
        B[(at + 1) * 2] = B[at] * B[(at + 1) * 2];
      }
      A[at] = B[at] * A[at];
      B[at] = F::id();

      if (dbg)
        cout << "@=" << at << " [" << L << "," << R << ")  Rng=["
             << Rng[at].first << "," << Rng[at].second << ") S=" << A[at].str()
             << " F=" << B[at].str() << endl;

      if ((R <= Rng[at].first) || (Rng[at].second <= L)) {
        if (dbg) cout << " 1 return" << endl;
        return;
      }
      if ((L <= Rng[at].first) && (Rng[at].second <= R)) {
        if (dbg) cout << " 2 in" << endl;
      } else {
        if (dbg) cout << " 3 cross" << endl;

        Func((at + 1) * 2);
        Func(at * 2 + 1);
        A[at] = A[at * 2 + 1] * A[(at + 1) * 2];
      }
    };
    Func(0);
  };

  S operator[](const ll& at) { return get(at, at + 1); };

  string str(const ll& at, const ll rngShow = true, const ll sShow = true,
             const ll fShow = true, const ll length = 0) {
    // S s = get(at, s + 1);
    string T(1, '_');

    if (rngShow)
      T += "[" + to_string(Rng[at].first) + "," + to_string(Rng[at].second) +
           ")";
    if (sShow) {
      if (*T.rbegin() != '_') T.push_back(' ');
      T += A[at].str();
    }
    if (fShow) {
      if (*T.rbegin() != '_') T.push_back(' ');
      T += B[at].str();
    }
    T.push_back('_');
    if (length > 0) {
      while (T.size() < length) T.push_back('_');
    }
    return T;
  }
  void show(const bool Hier = false, const ll rngShow = true,
            const ll sShow = true, const ll fShow = true, const ll length = 0) {
    if (Hier) {
      rep(i, Size) {
        cout << str(i, rngShow, sShow, fShow, length) << flush;
        if (Rng[i].second == N) cout << endl;
      }
    } else {
      rep(i, Size) cout << str(i, rngShow, sShow, fShow, length) << endl;
    }
  }
};

class SS {
 public:
  ll EsumMax;
  ll EsumAll;

  ll EsumLft;
  ll EsumRgt;

  SS(const ll& x, const ll& y, const ll& z, const ll& w)
      : EsumMax(x), EsumAll(y), EsumLft(z), EsumRgt(w) {};
  static SS e() {
    return SS(-100000000000, -100000000000, -100000000000, -100000000000);
  };
  friend SS operator*(const SS& l, const SS& r) {
    return SS(max<ll>(l.EsumRgt + r.EsumLft, max<ll>(l.EsumMax, r.EsumMax)),
              l.EsumAll + r.EsumAll,
              max<ll>(l.EsumLft, l.EsumAll + max<ll>(0, r.EsumLft)),
              max<ll>(r.EsumRgt, max<ll>(0, l.EsumRgt) + r.EsumAll));
  }
  string str() {
    return "<" + to_string(EsumMax) + "," + to_string(EsumAll) + "," +
           to_string(EsumLft) + "," + to_string(EsumRgt) + ">";
  };
  friend string str(SS x) { return x.str(); }
};
class FF {
 public:
  ll a;
  ll b;
  FF(const ll& x, const ll& y) : a(x), b(y) {};
  static FF id() { return FF(1, 0); };
  friend FF operator*(const FF& l, const FF& r) {
    return FF(l.a * r.a, l.a * r.b + l.b);
  };
  friend SS operator*(const FF& l, const SS& r) {
    return SS(l.a * r.EsumMax + l.b, l.a * r.EsumAll + l.b,
              l.a * r.EsumLft + l.b, l.a * r.EsumRgt + l.b);
  };
  string str() { return ("<" + to_string(a) + "," + to_string(b) + ">"); };
  friend string str(FF x) { return x.str(); }
};

class S_sum {
 public:
  ll e_sum;
  ll len;
  S_sum(const ll& x, const ll& y) : e_sum(x), len(y) {};
  static S_sum e() { return S_sum(0, 1); };
  friend S_sum operator*(const S_sum& l, const S_sum& r) {
    return S_sum(l.e_sum + r.e_sum, l.len + r.len);
  }
  string str() { return "<" + to_string(e_sum) + "," + to_string(len) + ">"; };
  friend string str(S_sum x) { return x.str(); }
};
class F_sum {
 public:
  ll a;
  ll b;
  F_sum(const ll& x, const ll& y) : a(x), b(y) {};
  static F_sum id() { return F_sum(1, 0); };
  friend F_sum operator*(const F_sum& l, const F_sum& r) {
    return F_sum(l.a * r.a, l.a * r.b + l.b);
  };
  friend S_sum operator*(const F_sum& l, const S_sum& r) {
    return S_sum(l.a * r.e_sum + l.b * r.len, r.len);
  };
  string str() { return ("<" + to_string(a) + "," + to_string(b) + ">"); };
  friend string str(F_sum x) { return x.str(); }
};

class S_sum998244353 {
 public:
  ll e_sum;
  ll len;
  S_sum998244353(const ll& x, const ll& y) : e_sum(x), len(y) {};
  static S_sum998244353 e() { return S_sum998244353(0, 1); };
  friend S_sum998244353 operator*(const S_sum998244353& l,
                                  const S_sum998244353& r) {
    return S_sum998244353((l.e_sum + r.e_sum) % 998244353,
                          (l.len + r.len) % 998244353);
  }
  string str() { return "<" + to_string(e_sum) + "," + to_string(len) + ">"; };
  friend string str(S_sum998244353 x) { return x.str(); }
};
class F_sum998244353 {
 public:
  ll a;
  ll b;
  F_sum998244353(const ll& x, const ll& y) : a(x), b(y) {};
  static F_sum998244353 id() { return F_sum998244353(1, 0); };
  friend F_sum998244353 operator*(const F_sum998244353& l,
                                  const F_sum998244353& r) {
    return F_sum998244353((l.a * r.a) % 998244353,
                          (((l.a * r.b) % 998244353) + l.b) % 998244353);
  };
  friend S_sum998244353 operator*(const F_sum998244353& l,
                                  const S_sum998244353& r) {
    return S_sum998244353(
        (((l.a * r.e_sum) % 998244353) + ((l.b * r.len) % 998244353)) %
            998244353,
        r.len);
  };
  string str() { return ("<" + to_string(a) + "," + to_string(b) + ">"); };
  friend string str(F_sum998244353 x) { return x.str(); }
};

class S_func998244353 {
 public:
  ll a;
  ll b;
  S_func998244353(const ll& x, const ll& y) : a(x), b(y) {};
  static S_func998244353 e() { return S_func998244353(1, 0); };
  friend S_func998244353 operator*(const S_func998244353& l,
                                   const S_func998244353& r) {
    return S_func998244353((r.a * l.a) % 998244353,
                           (((r.a * l.b) % 998244353) + r.b) % 998244353);
  }
  string str() { return "<" + to_string(a) + "," + to_string(b) + ">"; };
  friend string str(S_func998244353 x) { return x.str(); }
};
struct F_func998244353 {
 public:
  ll a;
  ll b;
  ll c;
  ll d;
  F_func998244353(const ll& x, const ll& y, const ll& z, const ll& w)
      : a(x), b(y), c(z), d(w) {};
  static F_func998244353 id() { return F_func998244353(1, 0, 1, 0); };
  friend F_func998244353 operator*(const F_func998244353& l,
                                   const F_func998244353& r) {
    return F_func998244353(
        (r.a * l.a) % 998244353, (((r.a * l.b) % 998244353) + r.b) % 998244353,
        (r.c * l.c) % 998244353, (((r.c * l.d) % 998244353) + r.d) % 998244353);
  };
  friend S_func998244353 operator*(const F_func998244353& l,

                                   const S_func998244353& r) {
    return S_func998244353((((l.a * r.a) % 998244353) + l.b) % 998244353,
                           (((l.c * r.b) % 998244353) + l.d) % 998244353);
  };
  string str() {
    return ("<" + to_string(a) + "," + to_string(b) + "," + to_string(c) + "," +
            to_string(d) + ">");
  };
  friend string str(F_func998244353 x) { return x.str(); }
};

class S_bitflp {
 public:
  ll zero;
  ll one;
  ll zo;
  ll oz;
  S_bitflp(const ll& x, const ll& y, const ll& z, const ll& w)
      : zero(x), one(y), zo(z), oz(w) {};
  static S_bitflp e() { return S_bitflp(0, 0, 0, 0); };
  friend S_bitflp operator*(const S_bitflp& l, const S_bitflp& r) {
    return S_bitflp(l.zero + r.zero, l.one + r.one,
                    l.zo + r.zo + l.zero * r.one, l.oz + r.oz + l.one * r.zero);
  }

  string str() {
    return "<" + to_string(zero) + "," + to_string(one) + "," + to_string(zo) +
           "," + to_string(oz) + ">";
  };
  friend string str(S_bitflp x) { return x.str(); }
};

class F_bitflp {
 public:
  ll flp;
  ll set_a;
  ll set_b;
  F_bitflp(const ll& x, const ll& y, const ll& z)
      : flp(x), set_a(y), set_b(z) {};
  static F_bitflp id() { return F_bitflp(0, 1, 0); };
  friend F_bitflp operator*(const F_bitflp& l, const F_bitflp& r) {
    return F_bitflp((l.flp + r.flp) % 2, l.set_a, l.set_b);
  };
  friend S_bitflp operator*(const F_bitflp& l, const S_bitflp& r) {
    if (l.flp == 0) {
      if (l.set_a != 1) {
        return S_bitflp(l.set_b == 0, l.set_b == 1, 0, 0);
      }
      return r;
    }
    return S_bitflp(r.one, r.zero, r.oz, r.zo);
  };
  string str() { return ("<" + to_string(flp) + ">"); };
  friend string str(F_bitflp x) { return x.str(); }
};

using sum = lazySeg<lazeSegment::S_sum, lazeSegment::F_sum>;
using ssff = lazySeg<lazeSegment::SS, lazeSegment::FF>;

using sum998244353 =
    lazySeg<lazeSegment::S_sum998244353, lazeSegment::F_sum998244353>;

using func998244353 =
    lazySeg<lazeSegment::S_func998244353, lazeSegment::F_func998244353>;

using bitflip =
    lazeSegment::lazySeg<lazeSegment::S_bitflp, lazeSegment::F_bitflp>;
};  // namespace lazeSegment

/////////////////////////////////////////////////

int main() {
  ll N;
  cin >> N;
  vl A(N);
  rep(i, N) cin >> A[i];

  lazeSegment::ssff SEG(N);

  rep(i, N) SEG.set(i, i + 1, SEG.f(0, A[i]));
  // SEG.show(1, 1, 1, 0);
  ll ANS = -LONG_LONG_MAX;
  rep(i, N - 1) {
    ll L = SEG.get(0, i + 1).EsumMax;
    ll R = SEG.get(i + 1, N).EsumMax;
    // zout(i, L, R, L * R);
    ANS = max<ll>(ANS, L * R);
  }

  rep(i, N) SEG.set(i, i + 1, SEG.f(0, -A[i]));
  // SEG.show(1, 1, 1, 0);
  // ll ANS = -LONG_LONG_MAX;
  rep(i, N - 1) {
    ll L = SEG.get(0, i + 1).EsumMax;
    ll R = SEG.get(i + 1, N).EsumMax;
    // zout(i, L, R, L * R);
    ANS = max<ll>(ANS, L * R);
  }

  cout << ANS << endl;
  return 0;
}
yukicoder

結果

ソースコード
