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