1090. 戰(zhàn)地統(tǒng)計(jì)系統(tǒng)(War Field Statistical System)
2050年，人類與外星人之間的戰(zhàn)爭(zhēng)已趨于白熱化。就在這時(shí)，人類發(fā)明出一種超級(jí)武器，這種武器能夠同時(shí)對(duì)相鄰的多個(gè)目標(biāo)進(jìn)行攻擊。凡是防御力小于或等于
這種武器攻擊力的外星人遭到它的攻擊，就會(huì)被消滅。然而，擁有超級(jí)武器是遠(yuǎn)遠(yuǎn)不夠的，人們還需要一個(gè)戰(zhàn)地統(tǒng)計(jì)系統(tǒng)時(shí)刻反饋外星人部隊(duì)的信息。這個(gè)艱巨的任
務(wù)落在你的身上。請(qǐng)你盡快設(shè)計(jì)出這樣一套系統(tǒng)。
這套系統(tǒng)需要具備能夠處理如下2類信息的能力：
1.外星人向[x1，x2]內(nèi)的每個(gè)位置增援一支防御力為v的部隊(duì)。
2.人類使用超級(jí)武器對(duì)[x1，x2]內(nèi)的所有位置進(jìn)行一次攻擊力為v的打擊。系統(tǒng)需要返回在這次攻擊中被消滅的外星人個(gè)數(shù)。
注：防御力為i的外星人部隊(duì)由i個(gè)外星人組成，其中第j個(gè)外星人的防御力為j。
輸入格式
從文件c.in第一行讀入n，m。其中n表示有n個(gè)位置，m表示有m條信息。
以下有m行，每行有4個(gè)整數(shù)k，x1，x2，v用來描述一條信息 。k表示這條信息屬于第k類。x1，x2，v為相應(yīng)信息的參數(shù)。k=1 or 2。
注：你可以認(rèn)為最初的所有位置都沒有外星人存在。
規(guī)模：0<n≤1000；0<x1≤x2≤n；0<v≤1000；0<m≤2000
輸出格式
結(jié)果輸出到文件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
樣例說明
輸入樣例 對(duì)應(yīng)輸出 輸出樣例
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 信息學(xué)練習(xí)賽 #6
題目標(biāo)簽 ：
二維(1)
線段樹(1)
這個(gè)題目的標(biāo)簽是二維+線段樹,我估計(jì)有些哥們真的用二維線段樹來做了,查看了一下后面的代碼,發(fā)現(xiàn)大多數(shù)的人的代碼都超過2k,有的還達(dá)到s四五k之多.
我的思路是把這個(gè)題目轉(zhuǎn)化成矩形切割來做,x,y,v三個(gè)參數(shù)以及默認(rèn)的一個(gè)初始值代表了一個(gè)矩形區(qū)域,左下角(x1,y1)=(x,1),右上角(x2,y2)=(y,v);
切割的大體方法是從USACO上的一個(gè)題目學(xué)來的,類似木塊上浮,從第一個(gè)矩形一直浮到最上面的矩形,每碰到一個(gè)遮蓋的矩形就分裂當(dāng)前矩形,在上浮的過程中計(jì)算出每次詢問的答案.
如果你對(duì)矩形切割很了解,相信我的代碼還是比較容易理解的.
1 #include<iostream>
2 using namespace std;
3 const int MAXM=3000+100;
4 struct rect
5 {
6 int x1,y1,x2,y2;
7 rect(){};
8 rect(int x1,int y1,int x2,int y2) : x1(x1),y1(y1),x2(x2),y2(y2) {}
9 }temp,q[MAXM];
10
11 int pos[MAXM],cp=0,ans[MAXM],n,m;
12 bool mark[MAXM];
13
14 inline bool is_parted(rect& a,rect& b)
15 {
16 return (a.x2<b.x1 || a.x1>b.x2 || a.y2<b.y1 || a.y1>b.y2);
17 }
18
19 void Cut(int p,rect cur)
20 {
21 if (p>cp) return;
22 while ( p<=cp && is_parted(cur,q[pos[p]]) ) ++p;
23 if (p>cp) return;
24 rect ques=q[pos[p]];
25 int area=(cur.y2-cur.y1+1)*(cur.x2-cur.x1+1);
26 if (cur.x1<ques.x1){
27 area-=(ques.x1-cur.x1)*(cur.y2-cur.y1+1);
28 rect temp=cur;
29 cur.x1=ques.x1;
30 temp.x2=ques.x1-1;
31 Cut(p+1,temp);
32 }
33 if (cur.x2>ques.x2){
34 area-=(cur.x2-ques.x2)*(cur.y2-cur.y1+1);
35 rect temp=cur;
36 cur.x2=ques.x2;
37 temp.x1=ques.x2+1;
38 Cut(p+1,temp);
39 }
40 if (cur.y2>ques.y2){
41 area-=(cur.y2-ques.y2)*(cur.x2-cur.x1+1);
42 rect temp=cur;
43 cur.y2=ques.y2;
44 temp.y1=ques.y2+1;
45 Cut(p+1,temp);
46 }
47 if (cur.y1<ques.y1){
48 area-=(ques.y1-cur.y1)*(cur.x2-cur.x1+1);
49 rect temp=cur;
50 cur.y1=ques.y1;
51 temp.y2=ques.y1-1;
52 Cut(p+1,temp);
53 }
54 ans[p]+=area;
55 }
56
57 int main()
58 {
59 freopen("c.in","r",stdin);
60 freopen("c.out","w",stdout);
61 memset(mark,0,sizeof(mark));
62 cin >> n >> m;
63 for (int i=0;i<m;++i){
64 int k,x,y,v;
65 cin >> k >> x >> y >> v;
66 q[i]=rect(x,1,y,v);
67 if (k==2){
68 mark[i]=1;
69 pos[++cp]=i;
70 }
71 }
72
73 memset(ans,0,sizeof(ans));
74 int p=1;
75 for (int i=0;i<m;++i){
76 if (mark[i]) { ++p; continue; }
77 Cut(p,q[i]);
78 }
79 for (int i=1;i<=cp;++i) cout << ans[i] << endl;
80
81 return 0;
82 }
83