POJ 2528 Mayor's posters

这一题多数用的是线段树+离散化，但是今天正好看到矩阵切割，所以就用矩阵切割试了一下。

参考了 http://www.2cto.com/kf/201209/156711.html 的代码，进行了一些修改，个人感觉更简洁且比较容易理解。

#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
const int M = 100000;
const int N = 10000;

struct line
{
    int l, r;
    int color;
    line(int ll = 0, int rr = 0, int c = 0) : l(ll), r(rr), color(c) {}
}post[M], cur;
int tot;

bool used[N];

inline bool cross(const line& l1, const line& l2)
{
    return !(
             (l1.l > l2.r)
             || (l1.r < l2.l));
}

inline void add(const line& t)
{
    post[tot++] = t;
}

void cut(const line& t)
{
    if(t.l < cur.l)
    {
        add(line(t.l, cur.l-1, t.color));
    }
    if(t.r > cur.r)
    {
        add(line(cur.r+1, t.r, t.color));
    }
}


int main(int argc, char *argv[])
{
#ifdef ACM_LOCAL // Local
    freopen("in", "r", stdin);
#else
    #ifndef  ONLINE_JUDGE // not HDOJ / POJ
    freopen("humble.in", "r", stdin);
    freopen("humble.out", "w", stdout);
    #endif
#endif

    int ncase;
    scanf("%d", &ncase);
    while(ncase--)
    {
        tot = 0;
        int color = 0;
        int n;

        scanf("%d", &n);
        while(n--)
        {
            scanf("%d %d", &cur.l, &cur.r);
            cur.color = color++;

            // 倒序，否则在cut操作中增加的线段也会再被检查一遍
            for(int i = tot-1; i>= 0; i--)
            {
                if(cross(post[i], cur))
                {
                    cut(post[i]);
                    post[i] = post[--tot];
                }
            }
            add(cur);
        }

        memset(used, false, sizeof(used));
        int cnt = 0;
        for(int i = 0; i!= tot; i++)
        {
            if(!used[post[i].color])
            {
                used[post[i].color] = true;
                cnt++;
            }
        }

        printf("%d\n", cnt);
    }

    return 0;
}

BTW，按说注释中提到的那个循环改成顺序的应该也可以的，只是会慢一些，但实际提交了却是RE。目前还不清楚原因。