1090.  戰地統計系統(War Field Statistical System)

---

2050年，人類與外星人之間的戰爭已趨于白熱化。就在這時，人類發明出一種超級武器，這種武器能夠同時對相鄰的多個目標進行攻擊。凡是防御力小于或等于 這種武器攻擊力的外星人遭到它的攻擊，就會被消滅。然而，擁有超級武器是遠遠不夠的，人們還需要一個戰地統計系統時刻反饋外星人部隊的信息。這個艱巨的任 務落在你的身上。請你盡快設計出這樣一套系統。

這套系統需要具備能夠處理如下2類信息的能力：

    1.外星人向[x1，x2]內的每個位置增援一支防御力為v的部隊。

    2.人類使用超級武器對[x1，x2]內的所有位置進行一次攻擊力為v的打擊。系統需要返回在這次攻擊中被消滅的外星人個數。

注：防御力為i的外星人部隊由i個外星人組成，其中第j個外星人的防御力為j。

輸入格式

從文件c.in第一行讀入n，m。其中n表示有n個位置，m表示有m條信息。

以下有m行，每行有4個整數k，x1，x2，v用來描述一條信息 。k表示這條信息屬于第k類。x1，x2，v為相應信息的參數。k=1 or 2。

注：你可以認為最初的所有位置都沒有外星人存在。

規模：0<n≤1000；0<x1≤x2≤n；0<v≤1000；0<m≤2000

輸出格式

結果輸出到文件c.out。按順序輸出需要返回的信息。

輸入樣例

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

輸出樣例

6
9

樣例說明

輸入樣例   對應輸出     輸出樣例
3 5             無              6
1 1 3 4         無              9
2 1 2 3         6
1 1 2 2         無
1 2 3 1         無
2 2 3 5         9

題目來源 ：OIBH 信息學練習賽 #6

題目標簽 ：

二維(1)   線段樹(1)  

這個題目的標簽是二維+線段樹,我估計有些哥們真的用二維線段樹來做了,查看了一下后面的代碼,發現大多數的人的代碼都超過2k,有的還達到s四五k之多.
我的思路是把這個題目轉化成矩形切割來做,x,y,v三個參數以及默認的一個初始值代表了一個矩形區域,左下角(x1,y1)=(x,1),右上角(x2,y2)=(y,v);
切割的大體方法是從USACO上的一個題目學來的,類似木塊上浮,從第一個矩形一直浮到最上面的矩形,每碰到一個遮蓋的矩形就分裂當前矩形,在上浮的過程中計算出每次詢問的答案.
如果你對矩形切割很了解,相信我的代碼還是比較容易理解的.