主題
題目連結：
題目大意：
輸入第一列給定兩正整數 N 、 M（1 ≦ N 、 M ≦ 10 ^ 6），代表一開始有 N 個空寶箱（編號為 1 到 N）以及 M 次的操作。
操作有兩種：
一：在連續區間 [P, Q] 的這些寶箱中各自放入 S 個金幣；
二：把連續區間 [P, Q] 的這些寶箱內各自最後擁有的金幣數（也就是先前以及未來的第一種操作得到的金幣總額）變為 S 倍。
接著有 M 列輸入，每列給定四正整數 P 、 Q 、 R 、 S（1 ≦ P 、Q ≦ N ， R = 1 或 2），代表要在區間 [P, Q] 上執行操作 R（R = 1 代表第一種、R = 2 代表第二種）。
試問 M 次操作結束後，金幣含量最多（保證不超過 20 億）的寶箱編號為何，且有多少金幣？如果有多個寶箱金幣數量相同，則挑編號最小的輸出。
範例輸入：
範例輸入 #1
5 4
3 5 2 2
1 4 1 2
5 5 2 2
2 5 1 3
範例輸入 #2
6 5
1 6 1 1
2 3 1 2
3 5 2 2
2 2 1 3
4 5 1 2
範例輸入 #3
10 5
2 9 1 99
1 7 2 1249
5 10 2 1
5 6 1 999999
6 7 1 500000
範例輸出：
範例輸出 #1
5 12
範例輸出 #2
2 6
範例輸出 #3
6 1873622402
解題思維：
與這題的精神相同——我們將每個操作的區間拆成「左」和「右」端點（也就是把 P 、 Q 分開）然後按照端點位置由小到大排序。如果有多個端點位置相同，則將「左端點」排前面。
接著從位置最小的端點開始掃到位置最大的，期間利用兩變數 X 、 Y 用來表示當前位置的基礎金幣數以及倍率（一開始 X = 0 、 Y = 1）。
當我們遇到「左」端點時，代表接下來的位置將會上一個所在位置多套用一次操作。當該端點之 R = 1 時，代表我們要將 X 加上 S；反之 R = 2 時，要將 Y 加上 S。而因為此時有機會是金幣「最大值」發生的地方（因為 X 或是 Y 增加了），所以我們要計算現在的 X × Y 之值。如果此時的 X × Y 大於先前找到的最大值，那麼就將最大值更新成該值並將最大值發生位置變更為現在所在位置。而如果 X × Y 與先前最大值相同，則因為我們要挑最左側的位置，因此最大值發生的位置維持原樣即可。
如果我們遇到的是「右」端點，則代表有一個操作將要結束了（將相同位置的「左」排於「右」前就是為了避免有的操作還沒執行就已經先被抵銷了）。當該端點之 R = 1 時，將 X 減去 S；反之 R = 2 時則將 Y 減去 S。可以看到最大值不會發生於此，所以不予理會。
因此掃的過程中便可以依據 X × Y 之值求得金幣最大值以及發生的位置，即所求。
值得一提的是，本題使用的精神有一個名字——掃描線演算法（Sweep Line Algorithm），開頭提及的題目也是。而這題也可以算是掃描線。又或是凸包的求法（如這題），尤其是 Andrew's Monotone Chain Convex Hull Algorithm 更是典型的掃描線。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
