結果
| 問題 |
No.619 CardShuffle
|
| コンテスト | |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2017-12-23 00:15:22 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,263 bytes |
| コンパイル時間 | 2,359 ms |
| コンパイル使用メモリ | 215,104 KB |
| 最終ジャッジ日時 | 2025-01-05 06:14:28 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 1 WA * 34 |
ソースコード
#include <bits/stdc++.h>
#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
using ll = long long;
using ld = long double;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
os << "sz:" << v.size() << "\n[";
for (const auto& p : v) {
os << p << ",";
}
os << "]\n";
return os;
}
template <typename S, typename T, typename U>
ostream& operator<<(ostream& os, const tuple<S, T, U>& t)
{
if (get<1>(t) == -1) {
if (get<2>(t) == -1) {
os << "*" << get<0>(t) << " ";
} else {
os << "+" << get<2>(t) << " ";
}
} else {
os << "*" << get<0>(t) << "+" << get<1>(t) << "+" << get<2>(t) << " ";
}
return os;
}
constexpr ll MOD = (ll)1e9 + 7LL;
constexpr ld PI = static_cast<ld>(3.1415926535898);
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;
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);
}
void print() const
{
cout << "#VALUE" << endl;
for (int i = 0; i < size; i++) {
cout << value[i] << " ";
}
cout << endl;
}
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>;
// (*A+B+C) (*D+E+F) = *A+(B+CD+E)+F
// (*A+B+C) (*D) = *A+B+CD
// (*A+B+C) (+F) = *A+(B+C)+F
// (*A) (*D+E+F) = *AD+E+F
// (*A) (*D) = (*AD)
// (*A) (+F) = *A+0+F
// (+C) (*D+E+F) = +(CD+E+F)
// (+C) (*D) = +CD
// (+C) (+F) = +(C+F)
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 (B == -1 and E == -1) {
if (C == -1 and F == -1) {
return make_tuple((A * D) % MOD, -1, -1);
} else if (C == -1) {
return make_tuple(A, 0, F);
} else if (F == -1) {
return make_tuple(-1, -1, (C * D) % MOD);
} else {
return make_tuple(-1, -1, (C + F) % MOD);
}
} else if (B == -1) {
if (C == -1) {
return make_tuple((A * D) % MOD, E, F);
} else {
return make_tuple(-1, -1, (C * D + E + F) % MOD);
}
} else if (E == -1) {
if (F == -1) {
return make_tuple(A, B, (C * D) % MOD);
} else {
return make_tuple(A, (B + C) % MOD, F);
}
} else {
return make_tuple(A, (B + C * D + E) % MOD, F);
}
}
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, -1, 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;
X--, Y--;
if (c == '?') {
X /= 2;
Y /= 2;
const auto ans = seg.accumulate(X, Y + 1);
cout << get<0>(ans) + get<1>(ans) + get<2>(ans) << endl;
} else {
if (X % 2 == 0) {
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, -1LL, vy)));
seg.set(Y, (op[Y] ? make_tuple(vx, -1LL, -1LL) : make_tuple(-1LL, -1LL, vx)));
} else {
X /= 2;
Y /= 2;
X++;
Y++;
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, -1LL, vx)));
seg.set(Y, (op[Y] ? make_tuple(vy, -1LL, -1LL) : make_tuple(-1LL, -1LL, vy)));
}
}
}
return 0;
}