The official construction has a very clean structure: split the $4\times W$ board into two disjoint cycles—an inner cycle containing exactly one 0 and $995$ ones, and an outer cycle containing only zeros. The target $N$ is then split as

$$N=q\cdot 995+r,\qquad 0\le r<995.$$

The inner cycle contributes exactly $r$ inversions, and where we cut the outer cycle contributes exactly $q\cdot995$. This is the whole trick.

This problem looks intimidating because it mixes Hamiltonian paths, inversion counts, and interaction, but the intended construction is surprisingly elegant.

The official editorial uses exactly the following idea: split the board into an inner cycle containing $995$ ones and one zero, and an outer cycle containing $1004$ zeros. (atcoder.jp)

---

1. First understand what an inversion means

Our sequence contains only 0 and 1.

An inversion is a pair

$$i<j,\qquad a_i>a_j.$$

Since the only values are 0 and 1, the only possible inversion is

$$1\quad\text{before}\quad0.$$

For example:

text
1 1 0 1 0

The first 1 creates inversions with both zeros.

The second 1 also creates inversions with both zeros.

The fourth element 1 creates an inversion with the last zero.

Total:

$$2+2+1=5.$$

So throughout this problem, all we care about is:

How many 1-before-0 pairs does our Hamiltonian path create?

---

2. The grid we print

We use this $4\times W$ grid:

text
000000000000...000
001111111111...110
011111111111...110
000000000000...000

For $W=500$:

• row 1: all zeros
• row 2: 00 + 497 ones + 0
• row 3: 0 + 498 ones + 0
• row 4: all zeros

This is exactly the construction in the official editorial. (atcoder.jp)

In C++:

cpp
cout << string(W, '0') << '\n';
cout << "00" + string(W - 3, '1') + "0" << '\n';
cout << "0" + string(W - 2, '1') + "0" << '\n';
cout << string(W, '0') << '\n';

Why this strange pattern?

Because now we can divide all 2000 cells into two cycles.

---

3. The inner cycle

Using 1-based coordinates, take

text
(2,2) → (2,3) → ... → (2,499)
                              ↓
(3,2) ← (3,3) ← ... ← (3,499)

and then

text
(3,2) → (2,2)

closes the cycle.

So the inner cycle is:

text
(2,2)
(2,3)
...
(2,499)
(3,499)
(3,498)
...
(3,2)

Number of cells:

$$498+498=996.$$

Look at their values.

The first cell

$$(2,2)$$

is 0.

Every other inner cell is 1.

Therefore the inner cycle contains:

$$995\text{ ones}+1\text{ zero}.$$

Define

$$B=995=2W-5.$$

This number $B$ is the most important number in the solution.

---

4. The outer cycle

All remaining cells form another cycle:

text
(2,1)
 ↓
(3,1)
 ↓
(4,1) → (4,2) → ... → (4,500)
                            ↑
                         (3,500)
                            ↑
                         (2,500)
                            ↑
(1,1) ← ... ← (1,499) ← (1,500)
 ↑
 back to (2,1)

Every one of these cells contains 0.

Number of outer cells:

$$2000-996=1004.$$

So we have:

• inner cycle: 995 ones + 1 zero
• outer cycle: 1004 zeros

This is the magic structure. (atcoder.jp)

---

5. Split the requested N

For every query, the judge gives us $N$.

Write

$$N=qB+r$$

where

$$B=995,\qquad 0\le r<995.$$

In C++:

cpp
long long q = N / B;
long long r = N % B;

We will make:

$$\underbrace{r}_{\text{from inner cycle}} + \underbrace{qB}_{\text{from outer zeros}} =N.$$

This decomposition is the heart of the solution.

---

6. How the inner cycle creates exactly r inversions

Originally, if we start the inner cycle at (2,2), its values are

text
0 1 1 1 1 ... 1

There are $B=995$ ones.

Suppose we rotate the cycle so that $r$ of the ones move before the zero.

Then the sequence becomes

$$1^r,\;0,\;1^{B-r}.$$

For example, if $r=4$:

text
1 1 1 1 0 1 1 1 1 ...

How many inversions?

Only the four 1s before the zero contribute.

Therefore:

$$\boxed{\text{inner inversions}=r}.$$

Implementation:

cpp
vector<pair<int,int>> curInner;

for (int i = inner.size() - r; i < inner.size(); i++)
    curInner.push_back(inner[i]);

for (int i = 0; i < inner.size() - r; i++)
    curInner.push_back(inner[i]);

An easier C++ implementation uses rotate, which I'll use in the final code.

---

7. But we currently have TWO cycles

We need one Hamiltonian path containing all 2000 cells.

At this point we have:

text
INNER CYCLE

    +------------------+
    |                  |
    +------------------+


OUTER CYCLE

+------------------------+
|                        |
|                        |
+------------------------+

We need to connect them.

We cut one edge from the inner cycle and one appropriate edge from the outer cycle:

text
outerA ----- outerB

innerA ----- innerB

and reconnect them as

text
outerA ----- innerA

innerB ----- outerB

Now instead of two cycles, we have one big cycle containing every cell.

The editorial implementation simply searches through the outer cycle until it finds the matching place. (atcoder.jp)

We want:

cpp
distance(inner.front(), outer[i-1]) == 1
distance(inner.back(),  outer[i])   == 1

The Manhattan distance is:

cpp
int dist(pair<int,int> a, pair<int,int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

Because of the geometry of these two nested cycles, such an edge always exists.

---

8. After connecting them, what does the sequence look like?

Rotate the outer cycle appropriately and call it outer2.

Remember:

every element of outer2 is zero.

The combined cycle conceptually looks like

text
outer zeros → inner → back to outer zeros

The inner values are

$$1^r,0,1^{B-r}.$$

Now we decide where to cut this big cycle to produce a path.

This is where $q$ is used.

---

9. Put q outer zeros AFTER all the inner ones

We make the final path:

text
outer[q ... end]
inner
outer[0 ... q-1]

Therefore the values are

$$0^{1004-q}, \quad 1^r,0,1^{B-r}, \quad 0^q.$$

Now count inversions.

The first zeros create nothing:

$$0^{1004-q}$$

doesn't matter.

Inside the inner section, we already know there are

$$r$$

inversions.

Finally there are $q$ zeros at the end.

Every one of our $B=995$ ones occurs before every one of those $q$ zeros.

So they create:

$$Bq$$

inversions.

Therefore

$$\boxed{\text{inversions}=Bq+r}.$$

But we defined

$$N=Bq+r.$$

Hence:

$$\boxed{\text{inversions}=N}.$$

That's the entire mathematical proof.

---

10. Why q always fits

The outer cycle contains

$$1004$$

zeros.

We need $q\le1004$.

Our maximum query is

$$N=999900.$$

And

$$\left\lfloor\frac{999900}{995}\right\rfloor=1004.$$

So:

$$0\le q\le1004.$$

Exactly what we need.

This relationship is deliberately built into the problem.

---

11. Visualization of the final sequence

Suppose, for a tiny imaginary example,

$$B=7$$

and we want

$$N=17.$$

Then

$$17=2\cdot7+3.$$

Thus

text
q = 2
r = 3

Make the inner sequence:

text
1 1 1 0 1 1 1 1

It has 3 inversions.

Then put two outer zeros after it:

text
... 1 1 1 0 1 1 1 1 0 0

There are 7 ones.

Each trailing zero creates 7 inversions:

$$2\times7=14.$$

Total:

$$14+3=17.$$

That's precisely what we're doing on the $4\times500$ grid.

---

12. Full C++ solution

Here is a complete interactive implementation.

cpp
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int manhattan(pii a, pii b) {
    return abs(a.first - b.first)
         + abs(a.second - b.second);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W, Q;
    cin >> H >> W >> Q;

    // ------------------------------------------------------------
    // Phase 1:
    // Print the 0/1 assignment.
    // ------------------------------------------------------------

    cout << string(W, '0') << '\n';
    cout << "00" + string(W - 3, '1') + "0" << '\n';
    cout << "0"  + string(W - 2, '1') + "0" << '\n';
    cout << string(W, '0') << '\n';

    cout << flush;

    // We use 0-based coordinates internally.
    //
    // inner:
    //
    // (1,1) -> (1,2) -> ... -> (1,W-2)
    //                            |
    // (2,1) <- (2,2) <- ... <- (2,W-2)
    //
    // This is a cycle of length 2*(W-2).
    //
    // Its first cell (1,1) contains 0.
    // Every other cell contains 1.

    vector<pii> inner;

    for (int col = 1; col <= W - 2; col++) {
        inner.push_back({1, col});
    }

    for (int col = W - 2; col >= 1; col--) {
        inner.push_back({2, col});
    }

    // outer:
    //
    // All remaining cells.
    //
    // Every cell here contains 0.
    //
    // Start:
    // (1,0) -> (2,0)
    //        -> bottom row left to right
    //        -> (2,W-1) -> (1,W-1)
    //        -> top row right to left
    //        -> back to (1,0)

    vector<pii> outer;

    outer.push_back({1, 0});
    outer.push_back({2, 0});

    for (int col = 0; col < W; col++) {
        outer.push_back({3, col});
    }

    outer.push_back({2, W - 1});
    outer.push_back({1, W - 1});

    for (int col = W - 1; col >= 0; col--) {
        outer.push_back({0, col});
    }

    // Number of 1s.
    //
    // W = 500:
    // B = 995.
    const int B = 2 * W - 5;

    // ------------------------------------------------------------
    // Phase 2:
    // Answer Q queries.
    // ------------------------------------------------------------

    for (int query = 0; query < Q; query++) {

        long long N;
        cin >> N;

        // The judge sends -1 if something earlier was invalid.
        if (N == -1) {
            return 0;
        }

        // N = q * B + r
        long long q = N / B;
        int r = N % B;

        // --------------------------------------------------------
        // Step 1:
        // Rotate inner cycle so its value sequence becomes
        //
        // 1^r, 0, 1^(B-r)
        //
        // giving exactly r inversions.
        // --------------------------------------------------------

        vector<pii> in = inner;

        if (r != 0) {
            rotate(in.begin(),
                   in.end() - r,
                   in.end());
        }

        // --------------------------------------------------------
        // Step 2:
        // Find an edge of the outer cycle that can be replaced
        // by connections to the two endpoints of the opened
        // inner cycle.
        //
        // We want:
        //
        // outer[i-1] -- in.front()
        //
        // in.back()  -- outer[i]
        // --------------------------------------------------------

        int L = (int)outer.size();

        int cut = -1;

        for (int i = 0; i < L; i++) {
            int prv = (i - 1 + L) % L;

            if (manhattan(in.front(), outer[prv]) == 1 &&
                manhattan(in.back(),  outer[i])   == 1) {
                cut = i;
                break;
            }
        }

        // The construction guarantees this exists.
        assert(cut != -1);

        // Rotate outer so that:
        //
        // out.front() = outer[cut]
        // out.back()  = outer[cut-1]
        //
        // Therefore
        //
        // out.back() -> in.front()
        //
        // and
        //
        // in.back() -> out.front()
        //
        // close one big Hamiltonian cycle.

        vector<pii> out;

        for (int i = cut; i < L; i++) {
            out.push_back(outer[i]);
        }

        for (int i = 0; i < cut; i++) {
            out.push_back(outer[i]);
        }

        // q can be as large as 1004, exactly outer.size().
        assert(q <= (long long)out.size());

        // --------------------------------------------------------
        // Step 3:
        //
        // Final path:
        //
        // out[q ... end]
        // inner
        // out[0 ... q-1]
        //
        // Its values are:
        //
        // 0^(L-q)
        // 1^r 0 1^(B-r)
        // 0^q
        //
        // inversion count
        // = r + q*B
        // = N.
        // --------------------------------------------------------

        vector<pii> answer;
        answer.reserve(H * W);

        for (int i = (int)q; i < L; i++) {
            answer.push_back(out[i]);
        }

        for (pii p : in) {
            answer.push_back(p);
        }

        for (int i = 0; i < q; i++) {
            answer.push_back(out[i]);
        }

        assert((int)answer.size() == H * W);

        // Convert our 0-based coordinates to the required
        // 1-based coordinates.
        for (auto [row, col] : answer) {
            cout << row + 1 << ' ' << col + 1 << '\n';
        }

        // Important for an interactive problem.
        cout << flush;
    }

    return 0;
}

This implements the same construction described in AtCoder's official editorial, rewritten here in C++. (atcoder.jp)

---

13. Let's walk through the code carefully

The key vectors are:

cpp
vector<pii> inner;
vector<pii> outer;

They don't represent arbitrary paths. They represent the two cycles.

Inner

cpp
for (int col = 1; col <= W - 2; col++) {
    inner.push_back({1, col});
}

Remember these are 0-based coordinates, so this is:

text
(2,2), (2,3), ..., (2,499)

in the problem's coordinates.

Then:

cpp
for (int col = W - 2; col >= 1; col--) {
    inner.push_back({2, col});
}

becomes:

text
(3,499), (3,498), ..., (3,2)

Therefore:

text
(2,2) → ... → (2,499)
                    ↓
(3,2) ← ... ← (3,499)

And (3,2) is adjacent to (2,2), so it's a cycle.

---

14. Why exactly 995 ones?

Row 2 contains:

text
00 + 497 ones + 0

so 497 ones.

Row 3 contains:

text
0 + 498 ones + 0

so 498 ones.

Therefore:

$$497+498=995.$$

Hence:

cpp
B = 2 * W - 5;

For $W=500$:

$$B=1000-5=995.$$

---

15. Understanding rotate

This may be the most confusing C++ line:

cpp
rotate(in.begin(), in.end() - r, in.end());

Suppose:

text
in = [0,1,1,1,1,1,1,1]

and

text
r = 3

Then the final three elements move to the front:

text
1 1 1 0 1 1 1 1

Exactly what we want.

So:

text
original:
0 1111111

after rotating r=3:
111 0 1111

And there are exactly three inversions.

---

16. The most subtle part: connecting the cycles

This condition:

cpp
if (manhattan(in.front(), outer[prv]) == 1 &&
    manhattan(in.back(),  outer[i])   == 1)

means geometrically:

text
outer[prv]       outer[i]
     |              |
     |              |
 in.front() ... in.back()

So instead of the two old edges:

text
outer[prv] --- outer[i]

in.back() --- in.front()

we use:

text
outer[prv] --- in.front()

in.back() --- outer[i]

Then the two separate cycles become:

text
ONE GIANT CYCLE

containing all 2000 cells.

This is why we can safely perform cyclic shifts afterward without breaking adjacency.

---

17. Why does the final vector remain a Hamiltonian path?

Our big structure is a Hamiltonian cycle.

A cycle looks like:

text
A → B → C → D → E → A

If we decide not to use one edge, for example E → A, we get:

text
A → B → C → D → E

which is a Hamiltonian path.

We can cut the cycle anywhere.

Our choice of where to cut is precisely what controls $q$.

So

cpp
out[q ...]
inner
out[... q-1]

is just a cyclic rotation of the same giant cycle.

Therefore:

• every cell appears exactly once,
• consecutive cells are adjacent,
• there are exactly 2000 cells.

---

18. Complete mathematical proof

For a query $N$, let

$$N=qB+r,\qquad B=995,\qquad0\le r<B.$$

The path values are

$$0^{1004-q} 1^r 0 1^{995-r} 0^q.$$

Now calculate inversions.

Part A: leading zeros

$$0^{1004-q}$$

create zero inversions.

Part B: the special inner zero

There are $r$ ones before it:

$$1^r0.$$

So:

$$r$$

inversions.

Part C: final q zeros

There are exactly $995$ ones before each of them.

Each contributes:

$$995$$

inversions.

For $q$ zeros:

$$995q.$$

Total:

$$r+995q.$$

Since

$$N=995q+r,$$

we get

$$\boxed{\text{inversion count}=N}.$$

That proves correctness.

---

19. Complexity

For each query we process roughly 2000 cells.

So:

$$O(HW)$$

per query.

Since

$$HW=2000,\qquad Q=200,$$

the total computational work is only around

$$400000$$

operations plus output.

Memory is also:

$$O(HW).$$

So algorithmically this is tiny; the difficult part is finding the construction.

---

20. What you should learn from this problem

The important contest-programming insight isn't really "Hamiltonian path algorithms." We never search for a Hamiltonian path.

The real pattern is:

$$\boxed{\text{Design the graph traversal so the numeric property becomes easy.}}$$

The construction deliberately creates two controllable quantities:

$$r\in[0,994]$$

using the position of one special zero, and

$$q\in[0,1004]$$

using how many outer zeros we put after all 995 ones.

They combine like digits in base 995:

$$\boxed{N=995q+r}.$$

So you can mentally summarize the entire 1000-point solution as:

Make 995 ones. One inner zero controls the remainder modulo 995. Outer zeros control multiples of 995. Connect the two cycles into one Hamiltonian cycle and cut it at the correct position.

That is the core idea behind the official solution. (atcoder.jp)

A key simplification is emerging: for each query, we can precompute two days $a$ and $b$. The L-greedy schedule gains day $a$, while the set of days left unused by the R-greedy schedule gains day $b$. Therefore the entire complicated scheduling state changes only by

$$e_i \mathrel{+}=1\quad(a\le i<b)$$

or

$$e_i \mathrel{-}=1\quad(b\le i<a),$$

where $e_i$ is one prefix-count difference. The rest of the solution is maintaining $\sum |e_i|$.

The formula also gives a very useful incremental answer:

$$\Delta\text{answer} = a+b-L_p-R_p + \Delta\!\left(\sum_i |e_i|\right).$$

So we never construct an actual schedule for any query. We only maintain one integer array implicitly in a lazy segment tree. I’ve also checked this reduction against all four samples and small brute-force schedules.

This one is substantially harder than E because the difficult part is not finding one optimal schedule—it is maintaining the optimum through $10^6$ changes.

The intended solution is an amortized $O(N\log N)$ algorithm. The main ideas below follow the official editorial's characterization using two greedy schedules and the array $e_i$. (AtCoder)

---

1. Forget the queries for a moment

Suppose we already know which jobs are L and which are R.

Let the days occupied by L jobs be

$$z_1<z_2<\cdots<z_k.$$

The total cost is

$$\sum_{i\in L}(x_i-L_i) + \sum_{i\in R}(R_i-x_i).$$

Because every day $1,\dots,N$ is used exactly once,

$$\sum_{\text{all jobs}} x_i=\frac{N(N+1)}2.$$

Let

$$Z=\sum_{i\in L}x_i.$$

Then the days used by R jobs sum to

$$\frac{N(N+1)}2-Z.$$

Therefore

$$\begin{aligned} \text{cost} &= Z-\sum_{i\in L}L_i + \sum_{i\in R}R_i -\left(\frac{N(N+1)}2-Z\right)\\ &= 2Z-\frac{N(N+1)}2 -\sum_{i\in L}L_i +\sum_{i\in R}R_i. \end{aligned}$$

Everything except $Z$ is fixed.

So:

$$\boxed{\text{We want the L jobs to be scheduled as early as possible.}}$$

---

2. Define $d_i$

Let

$$d_i$$

be the maximum possible number of L jobs performed during days

$$1,2,\dots,i.$$

There exists one schedule that simultaneously achieves every $d_i$; this is the key fixed-state result used by the official solution. (AtCoder)

How do we calculate $d_i$?

We construct two sets.

---

3. First greedy schedule: only the L jobs

Ignore every R job.

Schedule all L jobs as early as possible.

Suppose the occupied days are

$$x_1<x_2<\cdots<x_k.$$

Define

$$A_i=\#\{j:x_j\le i\}.$$

Obviously, no complete schedule can have more than $A_i$ L jobs in the first $i$ days.

---

4. Second greedy schedule: only the R jobs

Now ignore all L jobs.

Schedule the R jobs as late as possible.

There are $N-k$ such jobs, so exactly $k$ days remain unused.

Call those unused days

$$y_1<y_2<\cdots<y_k.$$

Define

$$B_i=\#\{j:y_j\le i\}.$$

The first $i$ days can contain at most $B_i$ L jobs; otherwise there would not be enough room for all the R jobs.

The important theorem is

$$\boxed{d_i=\min(A_i,B_i)}.$$

The editorial gives the equivalent construction of putting the $j$-th L job at day

$$\max(x_j,y_j).$$

Thus all these bounds can indeed be achieved simultaneously. (AtCoder)

---

5. Introduce the magic array $e_i$

Define

$$e_i=A_i-B_i.$$

Then

$$\min(A_i,B_i) = \frac{A_i+B_i-|A_i-B_i|}{2}.$$

Therefore

$$d_i= \frac{A_i+B_i-|e_i|}{2}.$$

This means that if we can maintain

$$\boxed{S=\sum_{i=1}^N |e_i|}$$

we can recover the optimal cost.

This is exactly the quantity maintained by the official solution. (AtCoder)

---

6. Deriving a very convenient formula for the answer

Let

$$X=\sum_j x_j,\qquad Y=\sum_j y_j.$$

Because an $x_j$ contributes to $A_i$ for

$$i=x_j,x_j+1,\dots,N,$$

we have

$$\sum_i A_i = \sum_j(N-x_j+1) = k(N+1)-X.$$

Similarly,

$$\sum_i B_i=k(N+1)-Y.$$

Hence

$$2\sum_i d_i = 2k(N+1)-X-Y-S.$$

Now if the actual L days are $z_1,\dots,z_k$,

$$\sum_i d_i = \sum_j(N-z_j+1) = k(N+1)-Z.$$

Therefore

$$2Z=X+Y+S.$$

Substitute this into the cost formula:

$$\boxed{ \text{answer} = X+Y+S -\frac{N(N+1)}2 -\sum_{L}L_i +\sum_R R_i }$$

This formula is extremely useful.

---

7. What happens when one job $p$ changes R → L?

Two things happen to our greedy schedules.

The L-only schedule gains one occupied day.

Call it

$$a.$$

The R-only schedule loses one job, so it gains one unused day.

Call it

$$b.$$

Then:

$$X\leftarrow X+a, \qquad Y\leftarrow Y+b.$$

Also,

$$-\sum_L L_i$$

changes by $-L_p$, while

$$+\sum_R R_i$$

changes by $-R_p$.

Consequently,

$$\boxed{ \Delta\text{answer} = a+b-L_p-R_p+\Delta S }$$

where

$$S=\sum |e_i|.$$

So now our whole problem becomes:

Find $a,b$, and efficiently update $S$.

---

8. Finding $a$ using DSU

Suppose the new L job is $p$.

It cannot be executed before $L_p$.

In the greedy earliest schedule, its insertion eventually adds exactly the first currently unused day

$$\ge L_p.$$

Why?

Imagine inserting it into the sorted greedy schedule. If day $L_p$ is occupied, that job gets pushed one step to the right, which may push another job, etc. The only newly occupied day is the first free day.

Therefore

$$a=\text{first unused day }\ge L_p.$$

This is the classic "next available position" DSU:

cpp
a = find(L[p]);
parent[a] = find(a + 1);

Each day is deleted once.

Complexity:

$$O(N\alpha(N)).$$

---

9. Finding $b$ is easier backwards

Forward in time, removing an R job from a latest-possible schedule is annoying.

Instead process the queries backwards.

At the end, all jobs are L, so there are no R jobs.

Now add jobs back as R in the order

$$P_N,P_{N-1},\dots,P_1.$$

When we add an R job $p$, scheduling R jobs as late as possible means we occupy

$$\boxed{\text{the last unused day }\le R_p}.$$

Use another DSU supporting predecessor:

cpp
b[t] = findPrev(R[p]);
parent[b[t]] = findPrev(b[t] - 1);

That occupied day in the reverse process is exactly the new unused day that appears in the corresponding forward query.

So all $a_t,b_t$ can be precomputed in almost-linear time.

---

10. How $e_i$ changes

Remember:

$$e_i=A_i-B_i.$$

Adding $a$ to the $x$-set means

$$A_i\mathrel{+}=1 \qquad\text{for every }i\ge a.$$

Therefore

$$e_i\mathrel{+}=1 \qquad i\ge a.$$

Adding $b$ to the $y$-set means

$$B_i\mathrel{+}=1 \qquad i\ge b,$$

so

$$e_i\mathrel{-}=1 \qquad i\ge b.$$

The common suffix cancels.

Therefore if $a<b$,

$$\boxed{e_a,e_{a+1},\dots,e_{b-1}\mathrel{+}=1}$$

and if $b<a$,

$$\boxed{e_b,e_{b+1},\dots,e_{a-1}\mathrel{-}=1}.$$

So every query becomes exactly one range update by $+1$ or $-1$.

This is the second major simplification.

---

11. Why maintaining $\sum |e_i|$ is tricky

Normal lazy propagation easily maintains

• range sum,
• range minimum,
• range maximum,

under range addition.

But

$$\sum |e_i|$$

is nonlinear.

However, notice what happens when adding exactly $1$.

For $e_i\to e_i+1$:

If $e_i\ge0$

$$|e_i+1|-|e_i|=+1.$$

If $e_i<0$

$$|e_i+1|-|e_i|=-1.$$

So for a +1 update:

$$\Delta S= \begin{cases} +\text{length} & e_i\ge0\\ -\text{length} & e_i<0. \end{cases}$$

Similarly for $e_i\to e_i-1$:

$$\Delta S= \begin{cases} +\text{length} & e_i\le0\\ -\text{length} & e_i>0. \end{cases}$$

That means we can split the updated interval into maximal pieces having the same relevant sign.

---

12. Segment tree

The segment tree stores, for every node:

text
minimum e_i
maximum e_i
lazy addition

Suppose we perform +1.

If currently we're in a nonnegative segment, we want to find the first position where

$$e_i<0.$$

We can search using the node's minimum:

text
minimum >= 0

means there is no negative value there, so skip the entire node.

Similarly:

• first $e_i<0$: use minimum,
• first $e_i\ge0$: use maximum,
• first $e_i>0$: use maximum,
• first $e_i\le0$: use minimum.

For each homogeneous piece we:

1. update S by +length or -length,
2. lazily add $+1$ or $-1$.

The official editorial uses precisely this idea: process intervals having the same sign together, find boundaries with a segment tree, and apply the unit range updates. (AtCoder)

---

13. Doesn't this while-loop become $O(N^2)$?

For arbitrary range updates, yes.

That's the cleverest part of this problem.

For this specific sequence of updates, the official editorial proves that the total number of sign intervals processed over all $N$ queries is only $O(N)$. Therefore the segment-tree work is

$$O(N\log N).$$

The amortized proof interprets each change as rotations in the L/R sequence of the optimal schedule and uses a potential based on the union of intervals from an R job's current execution day to its deadline. Interior rotation pieces decrease that potential, and only constantly many boundary pieces can occur per query. Thus the total number of processed pieces is linear. (AtCoder)

This amortization is why the while loop in the code is safe.

---

14. Starting answer

Initially every job is R.

Then $X=Y=S=0$.

So

$$\text{answer}_0 = \sum_i R_i-\frac{N(N+1)}2.$$

After query $t$, job $p=P_t$ changes type, so:

cpp
answer += a[t] + b[t] - L[p] - R[p]
          + (newS - oldS);

And we're done.

---

15. Complete C++17 solution

cpp
#include <bits/stdc++.h>
using namespace std;

/*
    DSU that finds the first unused position >= x.

    After position x is used:
        parent[x] = find(x + 1)
*/
struct NextDSU {
    vector<int> parent;

    NextDSU(int n) : parent(n + 2) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        int r = x;

        while (parent[r] != r)
            r = parent[r];

        while (parent[x] != x) {
            int y = parent[x];
            parent[x] = r;
            x = y;
        }

        return r;
    }

    void erase(int x) {
        parent[x] = find(x + 1);
    }
};


/*
    DSU that finds the last unused position <= x.

    After position x is used:
        parent[x] = find(x - 1)
*/
struct PrevDSU {
    vector<int> parent;

    PrevDSU(int n) : parent(n + 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        int r = x;

        while (parent[r] != r)
            r = parent[r];

        while (parent[x] != x) {
            int y = parent[x];
            parent[x] = r;
            x = y;
        }

        return r;
    }

    void erase(int x) {
        parent[x] = find(x - 1);
    }
};


/*
    Segment tree over e[0 ... N-1].

    Maintains:
        minimum
        maximum
        lazy range addition

    All e[i] initially = 0.
*/
struct SegTree {
    int n;

    vector<int> mn;
    vector<int> mx;
    vector<int> lazy;

    SegTree(int n)
        : n(n),
          mn(4 * n + 5),
          mx(4 * n + 5),
          lazy(4 * n + 5) {}


    void apply_node(int v, int delta) {
        mn[v] += delta;
        mx[v] += delta;
        lazy[v] += delta;
    }


    void push(int v) {
        if (lazy[v] == 0)
            return;

        int x = lazy[v];

        apply_node(v * 2, x);
        apply_node(v * 2 + 1, x);

        lazy[v] = 0;
    }


    void pull(int v) {
        mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
    }


    // add delta to [ql, qr)
    void add(int ql, int qr, int delta) {
        if (ql >= qr)
            return;

        add(1, 0, n, ql, qr, delta);
    }


    void add(
        int v,
        int l,
        int r,
        int ql,
        int qr,
        int delta
    ) {
        if (qr <= l || r <= ql)
            return;

        if (ql <= l && r <= qr) {
            apply_node(v, delta);
            return;
        }

        push(v);

        int mid = (l + r) / 2;

        add(v * 2, l, mid, ql, qr, delta);
        add(v * 2 + 1, mid, r, ql, qr, delta);

        pull(v);
    }


    int get(int pos) {
        return get(1, 0, n, pos);
    }


    int get(int v, int l, int r, int pos) {
        if (r - l == 1)
            return mn[v];

        push(v);

        int mid = (l + r) / 2;

        if (pos < mid)
            return get(v * 2, l, mid, pos);

        return get(v * 2 + 1, mid, r, pos);
    }


    /*
        kind:

        0 : find first e[i] <  0
        1 : find first e[i] >= 0
        2 : find first e[i] >  0
        3 : find first e[i] <= 0
    */

    bool contains_target(int v, int kind) const {
        if (kind == 0)
            return mn[v] < 0;

        if (kind == 1)
            return mx[v] >= 0;

        if (kind == 2)
            return mx[v] > 0;

        return mn[v] <= 0;
    }


    // Find first target inside [ql, qr).
    // Return qr if there is none.
    int first(int ql, int qr, int kind) {
        if (ql >= qr)
            return qr;

        int result =
            first(1, 0, n, ql, qr, kind);

        if (result == -1)
            return qr;

        return result;
    }


    int first(
        int v,
        int l,
        int r,
        int ql,
        int qr,
        int kind
    ) {
        if (qr <= l || r <= ql)
            return -1;

        if (!contains_target(v, kind))
            return -1;

        if (r - l == 1)
            return l;

        push(v);

        int mid = (l + r) / 2;

        int result =
            first(v * 2, l, mid, ql, qr, kind);

        if (result != -1)
            return result;

        return first(
            v * 2 + 1,
            mid,
            r,
            ql,
            qr,
            kind
        );
    }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> L(N + 1);
    vector<int> R(N + 1);

    long long sumR = 0;

    for (int i = 1; i <= N; i++) {
        cin >> L[i] >> R[i];
        sumR += R[i];
    }

    vector<int> P(N + 1);

    for (int i = 1; i <= N; i++)
        cin >> P[i];


    /*
        ------------------------------------------------
        Step 1:
        Precompute a[t].

        a[t] = the new day added to the earliest
               L-only schedule in query t.
        ------------------------------------------------
    */

    vector<int> a(N + 1);
    vector<int> b(N + 1);

    NextDSU nextDSU(N);

    for (int t = 1; t <= N; t++) {
        int p = P[t];

        a[t] = nextDSU.find(L[p]);

        nextDSU.erase(a[t]);
    }


    /*
        ------------------------------------------------
        Step 2:
        Precompute b[t] backwards.

        Add R jobs in reverse query order.

        b[t] = latest currently free day <= R[p].
        ------------------------------------------------
    */

    PrevDSU prevDSU(N);

    for (int t = N; t >= 1; t--) {
        int p = P[t];

        b[t] = prevDSU.find(R[p]);

        prevDSU.erase(b[t]);
    }


    /*
        ------------------------------------------------
        Step 3:
        Process queries while maintaining

            S = sum |e[i]|.
        ------------------------------------------------
    */

    SegTree seg(N);

    long long absSum = 0;

    long long totalDays =
        1LL * N * (N + 1) / 2;

    /*
        Initially everything is R:

        answer =
            sum R[i] - (1 + 2 + ... + N)
    */
    long long answer =
        sumR - totalDays;

    cout << answer;


    for (int t = 1; t <= N; t++) {
        int A = a[t];
        int B = b[t];

        long long oldAbsSum = absSum;


        /*
            e gets:

            +1 on [A, B) if A < B
            -1 on [B, A) if B < A

            Convert day numbers to 0-based indices.
        */
        if (A != B) {
            int l = min(A, B) - 1;
            int r = max(A, B) - 1;

            int delta =
                (A < B ? +1 : -1);

            int pos = l;

            /*
                For +1:
                    good = e >= 0

                For -1:
                    good = e <= 0

                On a good position |e| increases by 1.
                Otherwise |e| decreases by 1.
            */
            int value = seg.get(pos);

            bool good;

            if (delta == +1)
                good = (value >= 0);
            else
                good = (value <= 0);


            while (pos < r) {
                int kind;

                if (delta == +1) {
                    if (good) {
                        /*
                            Current block: e >= 0.
                            Find first e < 0.
                        */
                        kind = 0;
                    } else {
                        /*
                            Current block: e < 0.
                            Find first e >= 0.
                        */
                        kind = 1;
                    }
                } else {
                    if (good) {
                        /*
                            Current block: e <= 0.
                            Find first e > 0.
                        */
                        kind = 2;
                    } else {
                        /*
                            Current block: e > 0.
                            Find first e <= 0.
                        */
                        kind = 3;
                    }
                }


                int nxt =
                    seg.first(pos, r, kind);

                long long len = nxt - pos;


                if (good)
                    absSum += len;
                else
                    absSum -= len;


                seg.add(
                    pos,
                    nxt,
                    delta
                );


                pos = nxt;

                /*
                    The next maximal sign interval
                    has the opposite category.
                */
                good = !good;
            }
        }


        /*
            answer change:

              +a
              +b
              -L[p]
              -R[p]
              +change in sum |e|
        */

        int p = P[t];

        answer +=
            1LL * A
            + B
            - L[p]
            - R[p]
            + (absSum - oldAbsSum);


        cout << ' ' << answer;
    }

    cout << '\n';

    return 0;
}

---

16. Walk through Sample 1

We have

text
N = 3

job 1: [1,3]
job 2: [1,3]
job 3: [2,3]

P = [2,1,3]

Initially all are R.

$$\sum R_i=9$$

and

$$1+2+3=6.$$

Thus

$$ans_0=9-6=3.$$

Correct.

Query 1: job 2 becomes L

For the L greedy schedule,

$$a=1.$$

For the R schedule,

$$b=1.$$

So $a=b$, meaning $e$ doesn't change.

Therefore

$$\Delta S=0.$$

The answer changes by

$$a+b-L_2-R_2 = 1+1-1-3=-2.$$

So

$$3-2=1.$$

Correct.

Query 2

Again,

$$a=2,\quad b=2.$$

So

$$\Delta S=0$$

and

$$2+2-1-3=0.$$

Answer stays

$$1.$$

Query 3

$$a=3,\quad b=3.$$

Change:

$$3+3-2-3=1.$$

Answer:

$$2.$$

We obtain

text
3 1 1 2

exactly.

---

17. Complexity

The two DSU passes cost

$$O(N\alpha(N)).$$

Each processed sign interval costs

$$O(\log N)$$

with the segment tree.

The nontrivial amortization from the official editorial shows only $O(N)$ such intervals occur overall. (AtCoder)

So total complexity is

$$\boxed{O(N\log N)}$$

with

$$\boxed{O(N)}$$

memory.

For $N=10^6$, that is exactly what we need.

The best mental summary of this problem is:

$$\boxed{ \text{schedule} \rightarrow \text{two greedy day sets} \rightarrow e_i=A_i-B_i \rightarrow \sum|e_i| \rightarrow \text{range }\pm1+\text{sign blocks} }$$

The particularly important jump is realizing that one type change does not require dynamically rebuilding a schedule: after precomputing $a$ and $b$, it becomes just one interval update of the array $e$.