題意
     一開始想到用二維線段樹，但是我沒寫過二維的，只寫過一維的。后來問了下別人，說一維也行(一開始我也想到是不是可以用一維的,但是很快就被我自己給否定了,我認(rèn)為那樣時(shí)間會(huì)不夠的,后來再第11個(gè)點(diǎn)還真的不夠)。于是就寫了一個(gè)一維的線段樹。把每一行進(jìn)行一次線段樹操作。這樣空間也可以開出來，變成復(fù)雜度也不高。可是交上去之后在第11個(gè)點(diǎn)超時(shí)了。給的是2S,我的運(yùn)行了2.67S。有人說可以從后往前染色，那樣的話，如果某個(gè)區(qū)域已經(jīng)染色了，那么后面就不用在染色了，因?yàn)樵谌旧菦]有意義的。無奈不會(huì)實(shí)現(xiàn),想著用并查集稍微加速下，可是發(fā)現(xiàn)不怎么好合并(哪位高人看了給指點(diǎn)指點(diǎn),看到一牛人寫了點(diǎn),不過由于水平問題,實(shí)在不知并查集怎么實(shí)現(xiàn)這個(gè)問題的),于是一直TLE,今天看了nocow的題解,發(fā)現(xiàn)基本是用矩形切割做的.推薦看薛茅的論文，開始對(duì)這個(gè)東西我還一無所知。終于在那看到個(gè)線段樹的，第11組數(shù)據(jù)也只有0.7S。后來看了下，發(fā)現(xiàn)那個(gè)程序也是用一維的線段樹搞的,不過比我的實(shí)現(xiàn)的好,首先不是每一行都進(jìn)行一次線段樹操作,那樣時(shí)間肯定是不夠的。我們來看下面這幅圖，
圖中的黑色框是原矩形,紅色的是我們投影的那些值(這里沒有畫大矩形的兩條邊)。
我們首先對(duì)垂直X軸的邊投影(其中包括原來大矩形的兩條邊),得到一些列的值,那么以后只要對(duì)這些值中相鄰的兩個(gè)之間(圖中的紅色線條之間的區(qū)域)進(jìn)行一次線段樹的操作這樣的話可以減少不少的操作，也就是說原來的一行進(jìn)行一次，可以把某些行進(jìn)行合并，因?yàn)檫@些行(每兩條相鄰的紅色線段之間的行)的顏色都一樣的。這樣操作之后最大一組數(shù)據(jù)用時(shí)0.7S.
似乎這題的標(biāo)準(zhǔn)解法是矩形切割。到時(shí)再去看看。

下面再看看矩形切割的方法。(代碼不是我的。官方的，我只加了點(diǎn)注釋)
直接上代碼
下面的一個(gè)圖貼在代碼里面會(huì)亂，在這貼下吧(我無語了,還是會(huì)亂,只好截圖了)

CODE
  1#include <stdio.h>
  2#include <stdlib.h>
  3#include <string.h>
  4
  5FILE *fp,*fo;/**//*輸入輸出文件*/
  6
  7struct rect
  8{/**//*矩形結(jié)構(gòu)體*/
  9    int c;
 10    int x1,y1,x2,y2;
 11};
 12
 13int c[2501];/**//*顏色的多少*/
 14rect r[10001];
 15
 16int intersect(rect a,const rect &b,rect out[4])
 17{
 18    /**//* do they at all intersect? */
 19    if(b.x2<a.x1||b.x1>=a.x2)
 20        return 0;
 21    if(b.y2<a.y1||b.y1>=a.y2)
 22        return 0;
 23    /**//*上面表示不相交*/
 24    /**//* they do */
 25
 26    rect t;
 27
 28    if(b.x1<=a.x1&&b.x2>=a.x2&&b.y1<=a.y1&&b.y2>=a.y2)
 29            return -1; /**//*全部覆蓋前面的某個(gè)矩形*/
 30
 31    /**//* cutting `a' down to match b */
 32    /**//***********************
 33      +--------+                         +-+--+--+
 34      |             |                          |    |2 |     |
 35      |             |                         +  +--+   |
 36      |    +-+   |  -->                   |   |    |     |
 37      |    +-+   |                          |1 |    |3   |
 38      |             |                          |  +--+    |
 39      |             |                          |   | 4 |     |
 40     +--------+                         +-+--+--+
 41     ***********************/
 42    int nout=0;/**//*記錄分成多少塊*/
 43    if(b.x1>=a.x1) {/**//*上右圖中的1*/
 44        t=a,t.x2=b.x1;
 45        if(t.x1!=t.x2)
 46            out[nout++]=t;
 47        a.x1=b.x1;
 48    }
 49    if(b.x2<a.x2) {/**//*上右圖中的3*/
 50        t=a,t.x1=b.x2;
 51        if(t.x1!=t.x2)
 52            out[nout++]=t;
 53        a.x2=b.x2;
 54    }
 55    if(b.y1>=a.y1) {/**//*上右圖中的4*/
 56        t=a,t.y2=b.y1;
 57        if(t.y1!=t.y2)
 58            out[nout++]=t;
 59        a.y1=b.y1;
 60    }
 61    if(b.y2<a.y2) {/**//*上右圖中的2*/
 62        t=a,t.y1=b.y2;
 63        if(t.y1!=t.y2)
 64            out[nout++]=t;
 65        a.y2=b.y2;
 66    }
 67    return nout;
 68}
 69
 70int main(void) {
 71    fp=fopen("rect1.in","rt");
 72    fo=fopen("rect1.out","wt");
 73
 74    int a,b,n;
 75    fscanf(fp,"%d %d %d",&a,&b,&n);
 76    /**//*把原始矩形加進(jìn)去*/
 77    r[0].c=1;
 78    r[0].x1=r[0].y1=0;
 79    r[0].x2=a;
 80    r[0].y2=b;
 81
 82    rect t[4];
 83
 84    int i,j,rr=1;
 85    for(i=0;i<n;i++) 
 86      {
 87        int tmp;
 88        fscanf(fp,"%d %d %d %d %d",&r[rr].x1,&r[rr].y1,&r[rr].x2,&r[rr].y2,&r[rr].c);
 89
 90        if(r[rr].x1>r[rr].x2) 
 91          {
 92            tmp=r[rr].x1;
 93            r[rr].x1=r[rr].x2;
 94            r[rr].x2=tmp;
 95          }
 96        if(r[rr].y1>r[rr].y2) 
 97          {
 98            tmp=r[rr].y1;
 99            r[rr].y1=r[rr].y2;
100            r[rr].y2=tmp;
101          }
102
103        int nr=rr;
104        rect curr=r[rr++];
105        for(j=0;j<nr;j++) 
106          {
107            int n=intersect(r[j],curr,t);
108            if(!n)/**//*和r[j]不相交*/
109                continue;
110            if(n==-1) 
111              {/**//*全部覆蓋r[j]*/
112                memmove(r+j,r+j+1,sizeof(rect)*(rr-j-1));
113                /**//*把r數(shù)組從r[j+1]全部往前移一位*/
114                j--;/**//*進(jìn)行相應(yīng)的調(diào)整*/
115                rr--;
116                nr--;
117                continue;
118              }
119            r[j]=t[--n];/**//*分成幾塊*/
120            for(;n-->0;)/**//*把分成的幾塊加進(jìn)去*/
121                r[rr++]=t[n];
122          }
123      }
124
125    for(i=0;i<rr;i++)/**//*現(xiàn)在每一塊都是單一顏色的 直接統(tǒng)計(jì)*/
126        c[r[i].c]+=(r[i].x2-r[i].x1)*(r[i].y2-r[i].y1);
127
128    for(i=1;i<=2500;i++)
129        if(c[i])/**//*輸出*/
130            fprintf(fo,"%d %d\n",i,c[i]);
131
132    return 0;
133}
134