[NOIP2017 A팀 시뮬레이션 7.14 향상] 긴급 철수.

제목 대의:
n*m의 0,1 행렬(1<=n, m<=500)을 제시하고 한 점에서 출발하여 매번 아래로 또는 오른쪽으로만 갈 수 있고 1로 갈 수 없는 규칙을 규정한다. 여러 그룹은 (1<=Q<=600000)을 묻고 한 점에서 다른 점으로 갈 수 있는지 묻는다.
문제 풀이:
이 문제는 질이 매우 높다.이것은 오프라인으로 만든 것이라고 생각하기 쉽다.우리는 대열을 나누어 치료할 수 있다.현재 물어볼 열이 [x.y] 구간에 있다고 가정하고 m=(x+y)/2를 설정하고 m열을 연결열로 합니다.fi, j, S를 설정하면 (i, j) 이 점이 중간열에 들어갈 수 있는 S를 나타낸다. S는 하나의 점집이다. 이 물건은 직접 dp로 할 수 있고 S는bitset으로 신속하게 해결할 수 있다.그리고 매거 질문을 해서 중간열을 통과했는지 확인한다. 통과했다면 두 점의 S가 교차했는지 직접 볼 수 있고 만약에 한 점이 m열에서 특판해야 한다.이어서 [x.m-1], [m+1.y]를 치료한다.물론 문의는 미리 순서를 정해야 한다. 그렇지 않으면 매번 폭발할 때마다 반드시 시간을 초과한다.시간 복잡도: O(n ∗ m∗ log m∗ n32)
Code:

#include 
#include 
#include 
#include 
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
using namespace std;

const int N = 505, Q = 600005;

int n, m, q, p[N][N], ans[Q];
int cur[N][N], final[N][N], tot;
struct edge {
    int c, d, next, e;
}e[Q];
struct node {
    int a, b, c, d, e;
}d[Q];
bitset<505> f[501][501], emp; 

bool rank(node a, node b) {
    return a.d < b.d;
}

void link(int a, int b, int c, int d, int ee) {
    e[++ tot].next = final[a][b], e[tot].c = c, e[tot].d = d, e[tot].e = ee, final[a][b] = tot;
}

void Init() {
    scanf("%d %d", &n, &m);
    fo(i, 1, n) {
        fo(j, 1, m) {
            char ch = ' '; for(;ch != '0' && ch != '1'; ch = getchar());
            p[i][j] = ch - '0';
        }
    }
    scanf("%d", &q);
    fo(i, 1, q) scanf("%d %d %d %d", &d[i].a, &d[i].b, &d[i].c, &d[i].d), d[i].e = i;
    sort(d + 1, d + q + 1, rank);
    fo(i, 1, q) link(d[i].a, d[i].b, d[i].c, d[i].d, d[i].e);
}

void dg(int x, int y) {
    if(x > y) return;
    int m = (x + y) / 2;
    fd(j, m, x) fd(i, n, 1) {
        f[i][j] = emp;
        if(p[i][j]) continue;
        if(j == m) f[i][j][i] = 1;
        if(j != m) f[i][j] |= f[i][j + 1];
        if(i != n) f[i][j] |= f[i + 1][j];
    }
    fo(j, m, y) fo(i, 1, n) {
        f[i][j] = emp;
        if(p[i][j]) continue;
        if(j == m) f[i][j][i] = 1;
        if(j != m) f[i][j] |= f[i][j - 1];
        if(i != 1) f[i][j] |= f[i - 1][j];
    }
    fo(j, x, m) fo(i, 1, n) {
        for(int k = cur[i][j]; k; k = e[k].next, cur[i][j] = k) {
            int c = e[k].c, d = e[k].d, cc = e[k].e;
            if(d < m) break;
            if(j == m && d != m) {
                ans[cc] = f[c][d][i];
                continue;   
            }
            if(d == m && j != m) {
                ans[cc] = f[i][j][c];
                continue;
            }
            ans[cc] = (f[i][j] & f[c][d]).any();
        }
    }
    dg(x, m - 1); dg(m + 1, y);
}

void Mid() {
    fo(i, 1, n) fo(j, 1, m) cur[i][j] = final[i][j];
    dg(1, m);
}

void End() {
    fo(i, 1, q) if(ans[i]) printf("Safe
"); else printf("Dangerous
");
}

int main() {
    Init();
    Mid();
    End();
}