2021 CCPC桂林 B.A Plus B Problem (线段树)

传送门

线段树大模拟!。考验线段树功底的时候来了，作为队伍的史山选手，写这么史也是情有可原的。

#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;
}