HDU 1264 Counting Squares

　　题意就是给你多个矩形，然后算出这些矩形所框出来的总面积，框过多次的按一次算。

　　但是题目给的是二维的，线段树只是解决一维的问题比较简单。题目数据范围为0~100，所以我就建了一百棵线段树，这样就可以转化成一维的问题来解决了。-_-||

　　结果跑了70+ms 不知道还能再怎么优化……HDU里面有好多0ms的大神……

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 int st[110][10100];
 5 
 6 int change(int *t,int ml,int mr,int node,int l,int r)
 7 {

　　　　　if(t[node] == r-l+1)//加入该判断后，时间到了31ms，不过还是太慢……
　　　　　　　　return 0;

 8     if(l == r)
 9     {
10         if(t[node] == 1)
11         {
12             return 0;
13         }
14         else
15         {
16             t[node] = 1;
17             return 1;
18         }
19     }
20     int temp;
21     int m = (l+r)/2;
22     if(mr <= m)
23     {
24         temp = change(t,ml,mr,node+node,l,m);
25         t[node] += temp;
26         return temp;
27     }
28     if(m < ml)
29     {
30         temp = change(t,ml,mr,node+node+1,m+1,r);
31         t[node] += temp;
32         return temp;
33     }
34     temp = change(t,ml,m,node+node,l,m) + change(t,m+1,mr,node+node+1,m+1,r);
35     t[node] += temp;
36     return temp;
37 }
38 
39 int main()
40 {
41     int a,b,c,d,t;
42     memset(st,0,sizeof(st));
43     while(scanf("%d %d %d %d",&a,&b,&c,&d) != EOF)
44     {
45         if(a == -1 && b == -1 && c == -1 && d == -1)
46         {
47             int sum = 0;
48             for(int i = 1;i <= 100; i++)
49             {
50                 sum += st[i][1];
51             }
52             printf("%d\n",sum);
53             memset(st,0,sizeof(st));
54         }
55         else if(a == -2 && b == -2 && c == -2 && d == -2)
56         {
57             int sum = 0;
58             for(int i = 1;i <= 100; i++)
59             {
60                 sum += st[i][1];//当前这棵树的第一个节点储存的数据即为该维度的所框出的面积
61             }
62             printf("%d\n",sum);
63             break;
64         }
65         else
66         {
67             if(a > c)
68             {
69                 t = a;
70                 a = c;
71                 c = t;
72             }
73             if(b > d)
74             {
75                 t = b;
76                 b = d;
77                 d = t;
78             }
79             for(int i = a+1;i <= c; i++)
80             {
81                 change(st[i],b+1,d,1,1,100);
82             }
83         }
84     }
85     return 0;
86 }

0ms的方法找到了这中几乎要闪瞎我的双眼的却又在情理之中的做法……链接在一楼