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上的一个题目学来的,类似木块上浮,从第一个矩形一直浮到最上面的矩形,每碰到一个遮盖的矩形就分裂当前矩形,在上浮的过程中计算出每次询问的答案.
如果你对矩形切割很了解,相信我的代码还是比较容易理解的.
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