Lật bit trong khoảng

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 \leq q \leq 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 \leq l \leq r \leq 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 \leq 10^{6}$ .

Ví dụ

Đầu vào:

Copy

Đầu ra:

Copy

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

1

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