SGU177 解题手记
　　这题跟USACO的Shaping Regions有相似之处，我曾写过一篇解题报告：http://www.studentblog.net/m/bslgh/archives/2006/usaco211.html。
　　采用倒序染色+封闭然过色的格子的办法。对每一行开一个链表，染色时将白色部分记入总和，染色过后将这个格子删去。由于每个格子只被染色一次，所以总复杂度能控制在O(n^2)级别。
　　Submit 1: TLE on 13。废弃STL的list不用，改设置一个next数组来表示。
　　调试过程中出现了一个很奇怪的状况，程序在给出输出，return 0之后又出现了“段错误”。大概是读数据的时候有问题。
　　Submit 2: WA on 2。next数组只需要开一行就可以了。在封闭格子的时候出错了，假设之前染色[2,10]，当下一次染色[1,6]的时候，我把[1,7]封闭起来了。
　　Submit 3: TLE on 13。实际上根据前面的做法，复杂度无法控制在O(n^2)级别。极端数据是5000个给最后一列染色。问题出在每次都从链表头开始寻找染色的格子，现在需要更直接的定位方法。
　　Submit 4: AC。143ms，第一名（2008-01-29 19:29:20），拍照留念。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int main()
{
    int next[1002];
    bool painted[1001];
    int ops[5000][5];
    int n,m,tot;
    scanf("%d %d",&n,&m);
    tot=n*n;
    for (int i=0;i<m;++i)
    {
        int x1,x2,y1,y2;
        char c;
        scanf("%d %d %d %d %c",&x1,&y1,&x2,&y2,&c);
        ops[i][0]=min(x1,x2); ops[i][2]=max(x1,x2);
        ops[i][1]=min(y1,y2); ops[i][3]=max(y1,y2);
        ops[i][4]=c=='b';
    }
    for (int i=1;i<=n;++i)
    {
        for (int j=0;j<=n;++j) next[j]=j+1; next[n+1]=n+1;
        memset(painted,false,sizeof(painted));
        for (int p=m-1;p>=0;--p) if (i>=ops[p][0] && i<=ops[p][2])
        {
            int s,j;
            for (j=ops[p][1];j<=ops[p][3];s=j,j=next[j],next[s]=next[ops[p][3]]) if (!painted[j])
            {
                tot-=ops[p][4];
                painted[j]=true;
            }
        }
    }
    printf("%d\n",tot);
    return 0;
}