738. Shifting Letters Both Ways
A lowercase string is given, then q operations. Each operation is start end dir, and
shifts every letter from position start to position end inclusive one place through the
alphabet: FORWARD when dir is 1, BACKWARD when dir is 0. Positions are 0-based.
a shifted backward wraps to z, and z shifted forward wraps to a.
Print the final string.
abc, ops (0 1 0) (1 2 1) (0 2 1) -> ace
az, op (0 1 1) -> ba
zz, ops (0 1 0) (0 1 0) -> xx
## Each operation is a range add of plus or minus one
Turn the direction into a signed amount, +1 or -1, and every operation becomes a constant
range add. So it is two writes on a difference array, exactly as in problem 721, and one
running total recovers the shift that applies to each position.
Applying each operation across its range is O(n q).
## The negative remainder, which problem 726 warned about
Problem 726 could skip this because its shifts were never negative. Here the running total can be negative, and in most languages the remainder of a negative number is negative:
(-3) mod 26 is -3 in C, C++, Java and JavaScript
(-3) mod 26 is 23 in Python
A negative index into the alphabet is either a wrong letter or a crash, depending on the language. The fix is the standard one:
shift = ((run mod 26) + 26) mod 26
Taking the remainder twice costs nothing and makes the value non negative in every language.
This is the single most common portability bug in shift problems, and it is why zz with two
backward shifts is in the sample set: it produces a running total of -2.
## Reduce as you go, or once at the end
Either works here. Reducing the running total at every step keeps it small; reducing only when
forming the letter keeps the loop cleaner. With 2 * 10^5 operations the raw total fits in 32
bits comfortably, so this is a matter of taste rather than safety.
## The pair with problem 726
726 accumulates from the RIGHT, because each shift there applies to a prefix. This accumulates from the LEFT, because each operation here names its own range. Same alphabet arithmetic, opposite sweep direction, and the reason is in the statement rather than the technique.
## Boundaries
No operations returns the string unchanged. Two opposite shifts on the same range cancel.
## Cost
Time O(n + q). Space O(n).
Constraints - `1 ≤ length ≤ 200000` - `0 ≤ q ≤ 200000` - `0 ≤ start ≤ end < length` - `dir` is `0` or `1`
Input
The first line contains the lowercase string.
The second line contains an integer q.
Each of the next q lines contains three integers start, end and dir.
Output
Print the final string on one line, with no spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.