結果
| 問題 | No.619 CardShuffle |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2017-12-23 22:14:27 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,112 ms / 3,000 ms |
| コード長 | 8,617 bytes |
| コンパイル時間 | 2,307 ms |
| コンパイル使用メモリ | 215,792 KB |
| 最終ジャッジ日時 | 2025-01-05 06:18:40 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 35 |
ソースコード
#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
using ll = long long;
constexpr ll MOD = (ll)1e9 + 7LL;
template <typename Base>
class SegmentTree
{
public:
using BaseAlgebra = Base;
using AccMonoid = typename BaseAlgebra::AccMonoid;
using OpMonoid = typename BaseAlgebra::OpMonoid;
using T = typename BaseAlgebra::T;
using F = typename BaseAlgebra::OpMonoid::T;
SegmentTree(const int n) : data_num(n), height(__lg(2 * data_num - 1)), size(1 << (1 + height)), half(size >> 1), value(size, AccMonoid::identity()), action(size, OpMonoid::identity()) { assert(n > 0); }
SegmentTree(const std::vector<T>& val) : data_num(val.size()), height(__lg(2 * data_num - 1)), size(1 << (1 + height)), half(size >> 1), value(size), action(size, OpMonoid::identity())
{
for (int data = 0; data < half; data++) {
if (data < data_num) {
value[data + half] = val[data];
} else {
value[data + half] = AccMonoid::identity();
}
}
for (int node = half - 1; node >= 1; node--) {
value[node] = acc(value[2 * node], value[2 * node + 1]);
}
}
T get(const int a) const
{
assert(0 <= a and a < data_num);
return accumulate(a, a + 1);
}
void set(const int a, const T& val)
{
assert(0 <= a and a < data_num);
const int node = a + half;
value[node] = val;
for (int i = node / 2; i > 0; i /= 2) {
value[i] = acc(value[2 * i], value[2 * i + 1]);
}
}
void set(const int a, const T&& val)
{
assert(0 <= a and a < data_num);
const int node = a + half;
value[node] = val;
for (int i = node / 2; i > 0; i /= 2) {
value[i] = acc(value[2 * i], value[2 * i + 1]);
}
}
T accumulate(const int a, const int b) const // Accumulate (a,b]
{
assert(0 <= a and a < b and b <= data_num);
return accumulateRec(1, 0, half, a, b);
}
void modify(const int a, const int b, const F& f) // Apply f on (a,b]
{
assert(0 <= a and a < b and b <= data_num);
if (f == OpMonoid::identity()) {
return;
}
modifyRec(1, 0, half, a, b, f);
}
private:
void modifyRec(const int int_index, const int int_left, const int int_right, const int mod_left, const int mod_right, const F& f)
{
if (mod_left <= int_left and int_right <= mod_right) {
value[int_index] = act(f, value[int_index]);
action[int_index] = compose(f, action[int_index]);
} else if (int_right <= mod_left or mod_right <= int_left) {
// Do nothing
} else {
modifyRec(2 * int_index, int_left, (int_left + int_right) / 2, 0, half, action[int_index]);
modifyRec(2 * int_index, int_left, (int_left + int_right) / 2, mod_left, mod_right, f);
modifyRec(2 * int_index + 1, (int_left + int_right) / 2, int_right, 0, half, action[int_index]);
modifyRec(2 * int_index + 1, (int_left + int_right) / 2, int_right, mod_left, mod_right, f);
value[int_index] = acc(value[2 * int_index], value[2 * int_index + 1]);
action[int_index] = OpMonoid::identity();
}
}
T accumulateRec(const int int_index, const int int_left, const int int_right, const int mod_left, const int mod_right) const
{
if (mod_left <= int_left and int_right <= mod_right) {
return value[int_index];
} else if (int_right <= mod_left or mod_right <= int_left) {
return AccMonoid::identity();
} else {
return act(action[int_index], acc(accumulateRec(2 * int_index, int_left, (int_left + int_right) / 2, mod_left, mod_right),
accumulateRec(2 * int_index + 1, (int_left + int_right) / 2, int_right, mod_left, mod_right)));
}
}
const int data_num; // Num of valid data on leaves.
const int height;
const int size;
const int half;
vector<T> value; // Tree for value(length: size)
vector<F> action; // Tree for action(length: half)
bool has_lazy;
const AccMonoid acc{};
const OpMonoid compose{};
const BaseAlgebra act{};
};
struct ProductSum_Nothing {
using X = ll;
using T = tuple<ll, ll, ll>;
struct AccMonoid {
T operator()(const T& a, const T& b) const
{
const ll A = get<0>(a);
const ll B = get<1>(a);
const ll C = get<2>(a);
const ll D = get<0>(b);
const ll E = get<1>(b);
const ll F = get<2>(b);
if (A == -1 and B == -1 and C == -1) {
return b;
} else if (D == -1 and E == -1 and F == -1) {
return a;
}
if (A != -1 and C != -1) {
// (*A+B+C) (*D+E+F) = *A+(B+CD+E)+F
// (*A+B+C) (*D) = *A+B+CD
// (*A+B+C) (+E+F) = *A+(B+C+E)+F
if (D != -1 and F != -1) {
return make_tuple(A, (B + C * D + E) % MOD, F);
} else if (D != -1) {
return make_tuple(A, B, C * D);
} else {
return make_tuple(A, (B + C + E) % MOD, F);
}
} else if (A != -1) {
// (*A) (*D+E+F) = *AD+E+F
// (*A) (*D) = *AD
// (*A) (+E+F) = *A+E+F
if (D != -1 and F != -1) {
return make_tuple((A * D) % MOD, E, F);
} else if (D != -1) {
return make_tuple((A * D) % MOD, 0, -1);
} else {
return make_tuple(A, E, F);
}
} else {
// (+B+C) (*D+E+F) = +(B+CD+E)+F
// (+B+C) (*D) = +B+CD
// (+B+C) (+E+F) = +(B+C+E)+F
if (D != -1 and F != -1) {
return make_tuple(-1, (B + C * D + E) % MOD, F);
} else if (D != -1) {
return make_tuple(-1, B, (C * D) % MOD);
} else {
return make_tuple(-1, (B + C + E) % MOD, F);
}
}
}
constexpr static T identity() { return make_tuple(-1, -1, -1); }
};
struct OpMonoid {
using T = X;
T operator()(const T& f1, const T& f2) const { return f1 + f2; }
static constexpr T identity() { return 0; }
};
T operator()(const OpMonoid::T& /*f*/, const T& x) const { return x; }
};
int main()
{
int N;
cin >> N;
const int NUM = (N + 1) / 2;
const int OP = (N - 1) / 2;
vector<int> number(NUM, 0);
vector<bool> op(OP + 1, true);
for (int i = 0; i < N; i++) {
char c;
cin >> c;
if (i % 2 == 0) {
number[i / 2] = c - '0';
} else {
op[(i + 1) / 2] = c == '*';
}
}
using T = tuple<ll, ll, ll>;
vector<T> value(NUM);
for (int i = 0; i < NUM; i++) {
value[i] = (op[i] ? make_tuple(number[i], -1, -1) : make_tuple(-1, 0, number[i]));
}
SegmentTree<ProductSum_Nothing> seg(value);
int Q;
cin >> Q;
for (int i = 0; i < Q; i++) {
char c;
cin >> c;
ll X, Y;
cin >> X >> Y;
cerr << c << " " << X << " " << Y << endl;
if (c == '?') {
X /= 2, Y /= 2;
const auto ans = seg.accumulate(X, Y + 1);
cout << (max(0LL, get<0>(ans)) + max(0LL, get<1>(ans)) + max(0LL, get<2>(ans))) % MOD << endl;
} else {
if (X % 2 == 1) {
X /= 2, Y /= 2;
const ll vx = op[X] ? get<0>(seg.get(X)) : get<2>(seg.get(X));
const ll vy = op[Y] ? get<0>(seg.get(Y)) : get<2>(seg.get(Y));
seg.set(X, (op[X] ? make_tuple(vy, -1LL, -1LL) : make_tuple(-1LL, 0LL, vy)));
seg.set(Y, (op[Y] ? make_tuple(vx, -1LL, -1LL) : make_tuple(-1LL, 0LL, vx)));
} else {
X /= 2, Y /= 2;
const ll vx = op[X] ? get<0>(seg.get(X)) : get<2>(seg.get(X));
const ll vy = op[Y] ? get<0>(seg.get(Y)) : get<2>(seg.get(Y));
swap(op[X], op[Y]);
seg.set(X, (op[X] ? make_tuple(vx, -1LL, -1LL) : make_tuple(-1LL, 0LL, vx)));
seg.set(Y, (op[Y] ? make_tuple(vy, -1LL, -1LL) : make_tuple(-1LL, 0LL, vy)));
}
}
}
return 0;
}