线段树大模拟!。考验线段树功底的时候来了，作为队伍的史山选手，写这么史也是情有可原的。
#include <bits/stdc++.h>
using ll = long long;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
typedef std::pair<int, int> PII;
#define ls u << 1
#define rs u << 1 | 1
std::string str[2];
int n, m;
int a[N];
struct node {
int l, r;
int lazy;
int val, cnt0, cnt9;
}tr[N << 2];
inline void pushup(int u) {
tr[u].cnt0 = tr[ls].cnt0 + tr[rs].cnt0;
tr[u].cnt9 = tr[ls].cnt9 + tr[rs].cnt9;
}
inline void build(int u, int L, int R) {
tr[u].l = L, tr[u].r = R;
tr[u].lazy = -1;
if (L == R) {
tr[u].val = a[L];
if(a[L] == 0) tr[u].cnt0 = 1;
else if (a[L] == 9) tr[u].cnt9 = 1;
return ;
}
int mid = L + R >> 1;
build(ls, L, mid);
build(rs, mid + 1, R);
pushup(u);
}
inline void pushdown(int u) {
if (tr[u].lazy == -1) return ;
tr[ls].lazy = tr[rs].lazy = tr[u].lazy;
tr[ls].val = tr[rs].val = tr[u].lazy;
if (tr[u].lazy == 0) {
tr[ls].cnt0 = tr[ls].r - tr[ls].l + 1;
tr[rs].cnt0 = tr[rs].r - tr[rs].l + 1;
tr[ls].cnt9 = tr[rs].cnt9 = 0;
} else if (tr[u].lazy == 9) {
tr[ls].cnt9 = tr[ls].r - tr[ls].l + 1;
tr[rs].cnt9 = tr[rs].r - tr[rs].l + 1;
tr[ls].cnt0 = tr[rs].cnt0 = 0;
}
tr[u].lazy = -1;
}
inline void modify(int u, int l, int r, int val) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].lazy = val;
tr[u].val = val;
if (val == 9) {
tr[u].cnt9 = tr[u].r - tr[u].l + 1;
tr[u].cnt0 = 0;
} else if (val == 0){
tr[u].cnt9 = 0;
tr[u].cnt0 = tr[u].r - tr[u].l + 1;
} else {
tr[u].cnt9 = tr[u].cnt0 = 0;
}
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(ls, l, r, val);
if (r > mid) modify(rs, l, r, val);
pushup(u);
}
inline int querycnt(int u, int l, int r, int val) {
if (tr[u].l >= l && tr[u].r <= r) {
if (val == 9) return tr[u].cnt9;
return tr[u].cnt0;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if (l <= mid) sum = querycnt(ls, l, r, val);
if (r > mid) sum += querycnt(rs, l, r, val);
return sum;
}
inline int Query(int u, int l, int r, int val) {
if (tr[u].l == tr[u].r) {
if (val == 0 && tr[u].cnt0 == 1) return -1;
if (val == 9 && tr[u].cnt9 == 1) return -1;
return tr[u].l;
}
pushdown(u);
if (tr[u].l >= l && tr[u].r <= r) {
if (val == 0) {
if (tr[u].cnt0 == tr[u].r - tr[u].l + 1) return -1;
else {
int t = Query(rs, l, r, val);
if (t != -1) return t;
return Query(ls, l, r, val);
}
} else {
if (tr[u].cnt9 == tr[u].r - tr[u].l + 1) return -1;
else {
int t = Query(rs, l, r, val);
if (t != -1) return t;
return Query(ls, l, r, val);
}
}
}
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return Query(ls, l, r, val);
if (l > mid) return Query(rs, l, r, val);
int t = Query(rs, l, r, val);
if (t != -1) return t;
return Query(ls, l, r, val);
}
inline int queryx(int u, int x) {
if (tr[u].l == tr[u].r) return tr[u].val;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) return queryx(ls, x);
return queryx(rs, x);
}
inline void solve() {
std::cin >> n >> m;
std::cin >> str[0] >> str[1];
str[0] = " " + str[0];
str[1] = " " + str[1];
int c = 0;
for (int i = n; i; i --) {
a[i] = str[0][i] - '0' + str[1][i] - '0' + c;
if (a[i] >= 10) c = 1, a[i] -= 10;
else c = 0;
}
build(1, 1, n);
int tmp = a[0];
while (m --) {
int op, pos, v;
std::cin >> op >> pos >> v;
op --;
if (str[op][pos] - '0' == v) {
std::cout << queryx(1, pos) << ' ' << 0 << '\n';
continue;
}
if (str[op][pos] - '0' < v) {//加法
int ans = 1;
int c = v - str[op][pos] + '0';
int now = queryx(1, pos);
if (c + now < 10) modify(1, pos, pos, c + now), ans ++;
else {
modify(1, pos, pos, c + now - 10);
ans ++;
if (pos != 1) {
int all = querycnt(1, 1, pos - 1, 9);
if (all == pos - 1) {
if (all) {
modify(1, 1, pos - 1, 0);
ans += all;
}
} else {
int p = Query(1, 1, pos - 1, 9);
ans += pos - p - 1;
if (p < pos - 1) modify(1, p + 1, pos - 1, 0);
ans ++;
int tt = queryx(1, p);
modify(1, p, p, tt + 1);
}
}
}
std::cout << queryx(1, pos) << ' ' << ans << '\n';
} else {//减法
int ans = 1;
int c = str[op][pos] - '0' - v;
int now = queryx(1, pos);
if (now >= c) {
ans ++;
modify(1, pos, pos, now - c);
} else {
ans ++;
modify(1, pos, pos, now + 10 - c);
if (pos != 1) {
int all = querycnt(1, 1, pos - 1, 0);
if (all == pos - 1) {
if (all) {
ans += all;
modify(1, 1, pos - 1, 9);
}
} else {
int p = Query(1, 1, pos - 1, 0);
ans += pos - p - 1;
if (p < pos - 1) modify(1, p + 1, pos - 1, 9);
ans ++;
int tt = queryx(1, p);
modify(1, p, p, tt - 1);
}
}
}
std::cout << queryx(1, pos) << ' ' << ans << '\n';
}
str[op][pos] = char(v + '0');
}
}
int main(void) {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int _ = 1;
//std::cin >> _;
while (_ --) solve();
return 0;
}
邹某某加了一堆优化的代码，快了600ms。
#include <bits/stdc++.h>
#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
using ll = long long;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
typedef std::pair<int, int> PII;
#define ls u << 1
#define rs u << 1 | 1
#define endl '\n'
namespace OY {
namespace IO {
using size_type = size_t;
static constexpr size_type INPUT_BUFFER_SIZE = 1 << 16, OUTPUT_BUFFER_SIZE = 1 << 16, MAX_INTEGER_SIZE = 20, MAX_FLOAT_SIZE = 50;
#ifdef OY_LOCAL
static constexpr char input_file[] = "in.txt", output_file[] = "out.txt";
#else
static constexpr char input_file[] = "", output_file[] = "";
#endif
struct InputHelper {
FILE *m_file_ptr;
char m_buf[INPUT_BUFFER_SIZE], *m_end, *m_cursor;
bool m_ok;
InputHelper &set_bad() { return m_ok = false, *this; }
template <size_type BlockSize>
void _reserve() {
size_type a = m_end - m_cursor;
if (a >= BlockSize) return;
memmove(m_buf, m_cursor, a), m_cursor = m_buf;
size_type b = a + fread(m_buf + a, 1, INPUT_BUFFER_SIZE - a, m_file_ptr);
if (b < INPUT_BUFFER_SIZE) m_end = m_buf + b, *m_end = EOF;
}
template <typename Tp, typename BinaryOperation>
InputHelper &fill_integer(Tp &ret, BinaryOperation op) {
if (!isdigit(*m_cursor)) return set_bad();
ret = op(Tp(0), *m_cursor - '0');
size_type len = 1;
while (isdigit(*(m_cursor + len))) ret = op(ret * 10, *(m_cursor + len++) - '0');
m_cursor += len;
return *this;
}
explicit InputHelper(const char *inputFileName) : m_ok(true), m_cursor(m_buf + INPUT_BUFFER_SIZE), m_end(m_buf + INPUT_BUFFER_SIZE) { m_file_ptr = *inputFileName ? fopen(inputFileName, "rt") : stdin; }
~InputHelper() { fclose(m_file_ptr); }
static InputHelper &get_instance() {
static InputHelper s_obj(input_file);
return s_obj;
}
static bool is_blank(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }
static bool is_endline(char c) { return c == '\n' || c == EOF; }
const char &getchar_checked() {
_reserve<1>();
return *m_cursor;
}
const char &getchar_unchecked() const { return *m_cursor; }
void next() { ++m_cursor; }
template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &num) {
while (is_blank(getchar_checked())) next();
_reserve<MAX_INTEGER_SIZE>();
if (getchar_unchecked() != '-') return fill_integer(num, std::plus<Tp>());
next();
return fill_integer(num, std::minus<Tp>());
}
template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &num) {
while (is_blank(getchar_checked())) next();
_reserve<MAX_INTEGER_SIZE>();
return fill_integer(num, std::plus<Tp>());
}
template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &num) {
bool neg = false, integer = false, decimal = false;
while (is_blank(getchar_checked())) next();
_reserve<MAX_FLOAT_SIZE>();
if (getchar_unchecked() == '-') {
neg = true;
next();
}
if (!isdigit(getchar_unchecked()) && getchar_unchecked() != '.') return set_bad();
if (isdigit(getchar_unchecked())) {
integer = true;
num = getchar_unchecked() - '0';
while (next(), isdigit(getchar_unchecked())) num = num * 10 + (getchar_unchecked() - '0');
}
if (getchar_unchecked() == '.')
if (next(), isdigit(getchar_unchecked())) {
if (!integer) num = 0;
decimal = true;
Tp unit = 0.1;
num += unit * (getchar_unchecked() - '0');
while (next(), isdigit(getchar_unchecked())) num += (unit *= 0.1) * (getchar_unchecked() - '0');
}
if (!integer && !decimal) return set_bad();
if (neg) num = -num;
return *this;
}
InputHelper &operator>>(char &c) {
while (is_blank(getchar_checked())) next();
if (getchar_checked() == EOF) return set_bad();
c = getchar_checked(), next();
return *this;
}
InputHelper &operator>>(std::string &s) {
while (is_blank(getchar_checked())) next();
if (getchar_checked() == EOF) return set_bad();
s.clear();
do {
s += getchar_checked();
next();
} while (!is_blank(getchar_checked()) && getchar_unchecked() != EOF);
return *this;
}
explicit operator bool() { return m_ok; }
};
struct OutputHelper {
FILE *m_file_ptr = nullptr;
char m_buf[OUTPUT_BUFFER_SIZE], *m_end, *m_cursor;
char m_temp_buf[MAX_FLOAT_SIZE], *m_temp_buf_cursor, *m_temp_buf_dot;
uint64_t m_float_reserve, m_float_ratio;
void _write() { fwrite(m_buf, 1, m_cursor - m_buf, m_file_ptr), m_cursor = m_buf; }
template <size_type BlockSize>
void _reserve() {
size_type a = m_end - m_cursor;
if (a >= BlockSize) return;
_write();
}
OutputHelper(const char *outputFileName, size_type prec = 6) : m_cursor(m_buf), m_end(m_buf + OUTPUT_BUFFER_SIZE), m_temp_buf_cursor(m_temp_buf) { m_file_ptr = *outputFileName ? fopen(outputFileName, "wt") : stdout, precision(prec); }
static OutputHelper &get_instance() {
static OutputHelper s_obj(output_file);
return s_obj;
}
~OutputHelper() { flush(), fclose(m_file_ptr); }
void precision(size_type prec) { m_float_reserve = prec, m_float_ratio = uint64_t(pow(10, prec)), m_temp_buf_dot = m_temp_buf + prec; }
OutputHelper &flush() { return _write(), fflush(m_file_ptr), *this; }
void putchar(const char &c) {
if (m_cursor == m_end) _write();
*m_cursor++ = c;
}
template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
OutputHelper &operator<<(Tp ret) {
_reserve<MAX_INTEGER_SIZE>();
size_type len = 0;
if (ret >= 0)
do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;
while (ret);
else {
putchar('-');
do *(m_cursor + len++) = '0' - ret % 10, ret /= 10;
while (ret);
}
for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));
m_cursor += len;
return *this;
}
template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
OutputHelper &operator<<(Tp ret) {
_reserve<MAX_INTEGER_SIZE>();
size_type len = 0;
do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;
while (ret);
for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));
m_cursor += len;
return *this;
}
template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
OutputHelper &operator<<(Tp ret) {
if (ret < 0) {
putchar('-');
return *this << -ret;
}
ret *= m_float_ratio;
uint64_t integer = ret;
if (ret - integer >= 0.4999999999) integer++;
do {
*m_temp_buf_cursor++ = '0' + integer % 10;
integer /= 10;
} while (integer);
if (m_temp_buf_cursor > m_temp_buf_dot) {
do putchar(*--m_temp_buf_cursor);
while (m_temp_buf_cursor > m_temp_buf_dot);
putchar('.');
} else {
putchar('0'), putchar('.');
for (size_type i = m_temp_buf_dot - m_temp_buf_cursor; i--;) putchar('0');
}
do putchar(*--m_temp_buf_cursor);
while (m_temp_buf_cursor > m_temp_buf);
return *this;
}
OutputHelper &operator<<(const char &ret) {
putchar(ret);
return *this;
}
OutputHelper &operator<<(const char *ret) {
while (*ret) putchar(*ret++);
return *this;
}
OutputHelper &operator<<(const std::string &ret) { return *this << ret.data(); }
};
InputHelper &getline(InputHelper &ih, std::string &line) {
line.clear();
if (ih.getchar_checked() == EOF) return ih.set_bad();
while (!InputHelper::is_endline(ih.getchar_checked())) line += ih.getchar_unchecked(), ih.next();
if (ih.getchar_unchecked() != EOF) ih.next();
return ih;
}
}
}
using OY::IO::getline;
std::string str[2];
int n, m;
int a[N];
struct node {
int l, r;
int lazy;
int val, cnt0, cnt9;
}tr[N << 2];
inline void pushup(int u) {
tr[u].cnt0 = tr[ls].cnt0 + tr[rs].cnt0;
tr[u].cnt9 = tr[ls].cnt9 + tr[rs].cnt9;
}
inline void build(int u, int L, int R) {
tr[u].l = L, tr[u].r = R;
tr[u].lazy = -1;
if (L == R) {
tr[u].val = a[L];
if(a[L] == 0) tr[u].cnt0 = 1;
else if (a[L] == 9) tr[u].cnt9 = 1;
return ;
}
int mid = L + R >> 1;
build(ls, L, mid);
build(rs, mid + 1, R);
pushup(u);
}
inline void pushdown(int u) {
if (tr[u].lazy == -1) return ;
tr[ls].lazy = tr[rs].lazy = tr[u].lazy;
tr[ls].val = tr[rs].val = tr[u].lazy;
if (tr[u].lazy == 0) {
tr[ls].cnt0 = tr[ls].r - tr[ls].l + 1;
tr[rs].cnt0 = tr[rs].r - tr[rs].l + 1;
tr[ls].cnt9 = tr[rs].cnt9 = 0;
} else if (tr[u].lazy == 9) {
tr[ls].cnt9 = tr[ls].r - tr[ls].l + 1;
tr[rs].cnt9 = tr[rs].r - tr[rs].l + 1;
tr[ls].cnt0 = tr[rs].cnt0 = 0;
}
tr[u].lazy = -1;
}
inline void modify(int u, int l, int r, int val) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].lazy = val;
tr[u].val = val;
if (val == 9) {
tr[u].cnt9 = tr[u].r - tr[u].l + 1;
tr[u].cnt0 = 0;
} else if (val == 0){
tr[u].cnt9 = 0;
tr[u].cnt0 = tr[u].r - tr[u].l + 1;
} else {
tr[u].cnt9 = tr[u].cnt0 = 0;
}
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(ls, l, r, val);
if (r > mid) modify(rs, l, r, val);
pushup(u);
}
inline int querycnt(int u, int l, int r, int val) {
if (tr[u].l >= l && tr[u].r <= r) {
if (val == 9) return tr[u].cnt9;
return tr[u].cnt0;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if (l <= mid) sum = querycnt(ls, l, r, val);
if (r > mid) sum += querycnt(rs, l, r, val);
return sum;
}
inline int Query(int u, int l, int r, int val) {
if (tr[u].l == tr[u].r) {
if (val == 0 && tr[u].cnt0 == 1) return -1;
if (val == 9 && tr[u].cnt9 == 1) return -1;
return tr[u].l;
}
pushdown(u);
if (tr[u].l >= l && tr[u].r <= r) {
if (val == 0) {
if (tr[u].cnt0 == tr[u].r - tr[u].l + 1) return -1;
else {
int t = Query(rs, l, r, val);
if (t != -1) return t;
return Query(ls, l, r, val);
}
} else {
if (tr[u].cnt9 == tr[u].r - tr[u].l + 1) return -1;
else {
int t = Query(rs, l, r, val);
if (t != -1) return t;
return Query(ls, l, r, val);
}
}
}
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return Query(ls, l, r, val);
if (l > mid) return Query(rs, l, r, val);
int t = Query(rs, l, r, val);
if (t != -1) return t;
return Query(ls, l, r, val);
}
inline int queryx(int u, int x) {
if (tr[u].l == tr[u].r) return tr[u].val;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) return queryx(ls, x);
return queryx(rs, x);
}
inline void solve() {
OY::IO::InputHelper::get_instance() >> n >> m;
OY::IO::InputHelper::get_instance() >> str[0] >> str[1];
str[0] = " " + str[0];
str[1] = " " + str[1];
int c = 0;
for (int i = n; i; i --) {
a[i] = str[0][i] - '0' + str[1][i] - '0' + c;
if (a[i] >= 10) c = 1, a[i] -= 10;
else c = 0;
}
build(1, 1, n);
int tmp = a[0];
while (m --) {
int op, pos, v;
OY::IO::InputHelper::get_instance() >> op >> pos >> v;
op --;
if (str[op][pos] - '0' == v) {
OY::IO::OutputHelper::get_instance() << queryx(1, pos) << ' ' << 0 << '\n';
continue;
}
if (str[op][pos] - '0' < v) {//加法
int ans = 1;
int c = v - str[op][pos] + '0';
int now = queryx(1, pos);
if (c + now < 10) modify(1, pos, pos, c + now), ans ++;
else {
modify(1, pos, pos, c + now - 10);
ans ++;
if (pos != 1) {
int all = querycnt(1, 1, pos - 1, 9);
if (all == pos - 1) {
if (all) {
modify(1, 1, pos - 1, 0);
ans += all;
}
} else {
int p = Query(1, 1, pos - 1, 9);
ans += pos - p - 1;
if (p < pos - 1) modify(1, p + 1, pos - 1, 0);
ans ++;
int tt = queryx(1, p);
modify(1, p, p, tt + 1);
}
}
}
OY::IO::OutputHelper::get_instance() << queryx(1, pos) << ' ' << ans << '\n';
} else {//减法
int ans = 1;
int c = str[op][pos] - '0' - v;
int now = queryx(1, pos);
if (now >= c) {
ans ++;
modify(1, pos, pos, now - c);
} else {
ans ++;
modify(1, pos, pos, now + 10 - c);
if (pos != 1) {
int all = querycnt(1, 1, pos - 1, 0);
if (all == pos - 1) {
if (all) {
ans += all;
modify(1, 1, pos - 1, 9);
}
} else {
int p = Query(1, 1, pos - 1, 0);
ans += pos - p - 1;
if (p < pos - 1) modify(1, p + 1, pos - 1, 9);
ans ++;
int tt = queryx(1, p);
modify(1, p, p, tt - 1);
}
}
}
OY::IO::OutputHelper::get_instance() << queryx(1, pos) << ' ' << ans << '\n';
}
str[op][pos] = char(v + '0');
}
}
int main(void) {
int _ = 1;
//OY::IO::InputHelper::get_instance() >> _;
while (_ --) solve();
return 0;
}