Lật bit trong khoảng

Submit solution
Points: 3 (partial)
Time limit: 1.0s
JAVA11 2.0s
Pypy 3 2.0s
Memory limit: 67M
JAVA11 977M
Pypy 3 977M
Author:
creator
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho một xâu nhị phân (bắt đầu từ chỉ số \(0\)). Bạn hãy thực hiện các thao tác dạng \(l\:r\): lật tất cả các bit trong vị trí từ \(l\) tới \(r\) trên xâu, cuối cùng in ra xâu nhị phân đó.

Ghi chú: Lật bit là phép biến đổi bit \(0\) thành bit \(1\), bit \(1\) thành bit \(0\).

Đầu vào

Dòng đầu tiên chứa một xâu nhị phân, độ dài \(L\) không quá \(10^6\).

Dòng tiếp theo chứa một số nguyên \(q\) \((1 \le q \le 10^6)\), số thao tác trên xâu.

\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) \((0 \le l \le r \le L - 1)\).

Chú ý: dữ liệu nhập-xuất lớn, bạn hãy sử dụng nhập xuất nhanh (fast io) đồng thời tránh flush khi xuất dữ liệu (VD: endl trong C++).

Đầu ra

Một xâu nhị phân duy nhất.

Subtask

\(30\%\) số test có \(L*q \le 10^6\).

Ví dụ

Đầu vào:

10010100
3
0 2
1 3
6 7

Đầu ra:

00000111

Giải thích:

Sau thao tác đầu tiên ta được xâu: \(01110100\).

Sau thao tác thứ hai ta được xâu: \(00000100\).

Sau thao tác cuối cùng ta được xâu: \(00000111\) \(\to\) xuất ra \(00000111\).

QDUY

Comments


  • 0
    TICHPX  commented on May 2, 2024, 8:02 a.m.

    thuật toán "trồng-chặt" với phép cuộn cuống chiếu partial_sum