The Great Cookie Swap¶

Indicative time limit: 0.5 s (reference environment: environment and measurements; for guidance only)
Actual time limit: 2 times the reference solution's baseline runtime on its slowest official test file in the target judging environment, rounded up in 0.5 s increments; if the judge supports only coarser increments, round up again to a supported value.
Memory limit: 1024 MB

Story¶

Every guest at a tea party brings cookies and reports how many they can eat. The host announces, “This is a swap. Please don't just sit down and eat your own box.”

Each cookie must pass directly from its owner to another guest. It cannot be passed on again or take a round trip back to its owner. Guests occasionally revise their quantities or appetites. The host also selects a consecutive group of seats and asks how many cookies that group could distribute internally.

These are planning exercises. After each estimate, not a single cookie has disappeared.

(This story was rewritten by GPT-6 Astra.)

Formal Problem Statement¶

There are \(n\) participants numbered from \(1\) to \(n\) . Participant \(i\) has receiving capacity \(d_i\) (demand) and providing capacity \(s_i\) (supply), both measured in items. Each item passes directly from its provider to its recipient; these must be different participants. Both quantities are upper bounds and need not be fully used.

Process \(m\) operations in order. Each is one of the following three types:

1 x d : set \(d_x=d\) .
2 x s : set \(s_x=s\) .
3 l r : allow only participants in \([l,r]\) to exchange items, and find the maximum total delivered.

Formally, for every pair of distinct participants \(i,j\) in the queried range, choose a nonnegative integer \(f_{ij}\) representing the number of items delivered from \(i\) to \(j\) . Require \(\sum_{j\ne i}f_{ij}\le s_i\) for each provider and \(\sum_{i\ne j}f_{ij}\le d_j\) for each recipient, and maximize \(\sum_{i\ne j}f_{ij}\) . All indices and sums here are restricted to \([l,r]\) .

A participant may both provide and receive, and two different participants may provide items to each other. Queries do not consume any quantities; only the first two operations change the state.

Input Format¶

The first line contains \(n,m\) .

The second line contains \(2n\) integers \(d_1,s_1,d_2,s_2,\ldots,d_n,s_n\) .

Each of the next \(m\) lines contains three integers describing an operation.

Output Format¶

For each type-3 operation, print one integer on its own line. If there are no type-3 operations, produce no output.

Sample 1¶

Input¶

3 5
1 1 2 2 2 3
3 1 3
3 1 2
1 1 2
3 1 3
3 1 2

Output¶

Explanation¶

The first query can deliver \(5\) cookies: participant \(1\) gives one to \(2\) , participant \(2\) gives two to \(3\) , and participant \(3\) gives one each to \(1\) and \(2\) .

After the update, participant \(1\) may receive up to \(2\) cookies, and the maximum totals for the two ranges become \(6\) and \(3\) .

Sample 2¶

Input¶

2 4
100 100 1 1
3 1 2
3 1 1
1 2 100
3 1 2

Output¶

2
0
101

Explanation¶

Initially, each participant can give one cookie to the other, for a total of \(2\) . A singleton cannot deliver items to itself, so its answer is \(0\) .

After the update, participant \(1\) can give \(100\) cookies to \(2\) , while participant \(2\) can still give one to \(1\) . The last query therefore has answer \(101\) .

Constraints and Guarantees¶

\(1\le n,m\le300\,000\) .
\(0\le d_i,s_i,d,s\le1\,000\,000\,000\) , all integers.
Updates satisfy \(1\le x\le n\) .
Queries satisfy \(1\le l\le r\le n\) .

Test Groups¶

Score share	Additional conditions
10%	\(n,m\le10\) ; all quantities are at most \(50\)
10%	\(n,m\le100\)
20%	\(n,m\le300\)
20%	\(n,m\le3\,000\)
20%	\(n,m\le50\,000\)
20%	No additional conditions