# CodeForces 575I Robots protection

Author: Fanyi Pu

Published: 2020-02-11

Canonical: <https://pufanyi.com/blog/oi-icpc/codeforces/cf575i>

CodeForces 575I Robots protection 题解。

你需要在平面直角坐标系上进行 $q$ 次操作。每次操作有两种，要么放置一个两条直角边平行于坐标轴的等腰直角三角形，要么查询某一个点被多少个三角形覆盖。保证所有点的坐标都是整数且 $\in [1,n]$。$n \le 5 \times 10^3, q \le 10^5$。

考虑到四种方向是对称的，我们只考虑其中一种情况，比如说直角顶点在左下角的情况，令三个顶点为 $(x,y), (x+l,y), (x,y+l)$。

首先我们发现需要加的所有点 $(x',y')$，都满足 $x+y\le x'+y'\le x+y+l$，这个东西用一棵树状数组就可以维护：

![两条平行斜线之间的带状区域，包含待覆盖的三角形](https://pufanyi.com/posts/oi-icpc/codeforces/cf575i/images/diagonal-strip.avif)

然后我们就是要减去这两块：

![带状区域中需要减去的左侧和下侧区域](https://pufanyi.com/posts/oi-icpc/codeforces/cf575i/images/excluded-regions.avif)

我们考虑如何减去，观察这些点的性质，首先均满足 $x'+y'\in [x+y,x+y+l]$，然后其还满足 $x'<x$ 或 $y'<y$。于是我们可以考虑开两棵二维树状数组，一棵维护下标 $(x+y,x)$，另一棵维护下标 $(x+y,y)$，然后在这两棵树状数组上矩阵加即可。

时间复杂度 $\mathcal{O}(q\log^2n)$，空间 $\mathcal{O}(n^2)$。

[代码在这儿](https://codeforces.com/contest/575/submission/70715634)。

```cpp
#define _CRT_SECURE_NO_WARNINGS

#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

inline char gc() {
    static const int L = 233333;
    static char sxd[L], *sss = sxd, *ttt = sxd;
    if (sss == ttt) {
        ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
        if (sss == ttt) {
            return EOF;
        }
    }
    return *sss++;
}

#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
    char dd;
    for (; !isalpha(c); dd);
    return c;
}

inline char readchar() {
    char dd;
    for (; c == ' '; dd);
    return c;
}

template <class T>
inline bool read(T& x) {
    bool flg = false;
    char dd;
    x = 0;
    for (; !isdigit(c); dd) {
        if (c == '-') {
            flg = true;
        } else if(c == EOF) {
            return false;
        }
    }
    for (; isdigit(c); dd) {
        x = (x * 10) + (c ^ 48);
    }
    if (flg) {
        x = -x;
    }
    return true;
}
#undef dd

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x < 10) {
        putchar(x | 48);
        return;
    }
    write(x / 10);
    putchar((x % 10) | 48);
}

template <class T>
inline void writesp(T x) {
    write(x);
    putchar(' ');
}

template <class T>
inline void writeln(T x) {
    write(x);
    puts("");
}

#define lowbit(x) (x & -x)

namespace dfcmd {

    const int maxn = 5005;
    const int maxq = 100005;

    int n, q;

    struct Tree_Line {
        int no[maxn << 1];

        inline void init() {
            memset(no, 0, sizeof(no));
        }

        inline void _update(int x, int y) {
            for (; x <= n << 1; x += lowbit(x)) {
                no[x] += y;
            }
        }

        inline void update(int l, int r) {
            _update(l, 1);
            _update(r + 1, -1);
        }

        inline int query(int x) {
            int ans = 0;
            for (; x; x -= lowbit(x)) {
                ans += no[x];
            }
            return ans;
        }
    } s;

    struct Tree_2D {
        int no[maxn << 1][maxn];

        inline void init() {
            memset(no, 0, sizeof(no));
        }

        inline void _update(int x, int y, int xx) {
            for (; x <= n << 1; x += lowbit(x)) {
                for (int ty = y; ty <= n; ty += lowbit(ty)) {
                    no[x][ty] += xx;
                }
            }
        }

        inline void update(int lx, int ly, int rx, int ry) {
            if (lx <= rx && ly <= ry) {
                _update(lx, ly, 1);
                _update(rx + 1, ly, -1);
                _update(lx, ry + 1, -1);
                _update(rx + 1, ry + 1, 1);
            }
        }

        inline int query(int x, int y) {
            int ans = 0;
            for (; x; x -= lowbit(x)) {
                for (int ty = y; ty; ty -= lowbit(ty)) {
                    ans += no[x][ty];
                }
            }
            return ans;
        }
    } xx, yy;

    struct query {
        int typ, dir, x, y, len;
    } qq[maxq];

    int ans[maxq];

    inline void solve(int tp) {
        xx.init(), yy.init(), s.init();
        for (int i = 1; i <= q; ++i) {
            if (qq[i].typ == 2) {
                ans[i] += s.query(qq[i].x + qq[i].y) - xx.query(qq[i].x + qq[i].y, qq[i].x) - yy.query(qq[i].x + qq[i].y, qq[i].y);
            } else if ((qq[i].dir & 1) == tp) {
                if (qq[i].dir < 3) {
                    s.update(qq[i].x + qq[i].y, qq[i].x + qq[i].y + qq[i].len);
                    xx.update(qq[i].x + qq[i].y, 1, qq[i].x + qq[i].y + qq[i].len, qq[i].x - 1);
                    yy.update(qq[i].x + qq[i].y, 1, qq[i].x + qq[i].y + qq[i].len, qq[i].y - 1);
                } else {
                    s.update(qq[i].x + qq[i].y - qq[i].len, qq[i].x + qq[i].y);
                    xx.update(qq[i].x + qq[i].y - qq[i].len, qq[i].x + 1, qq[i].x + qq[i].y, n);
                    yy.update(qq[i].x + qq[i].y - qq[i].len, qq[i].y + 1, qq[i].x + qq[i].y, n);
                }
            }
        }
    }

    int Main() {
        read(n), read(q);
        for (int i = 1; i <= q; ++i) {
            read(qq[i].typ);
            if (qq[i].typ == 1) {
                read(qq[i].dir), read(qq[i].x), read(qq[i].y), read(qq[i].len);
                if (qq[i].dir == 3) {
                    qq[i].dir = 4;
                } else if (qq[i].dir == 4) {
                    qq[i].dir = 3;
                }
            } else {
                read(qq[i].x), read(qq[i].y);
            }
        }
        solve(1);
        for (int i = 1; i <= q; ++i) {
            qq[i].y = n - qq[i].y + 1;
        }
        solve(0);
        for (int i = 1; i <= q; ++i) {
            if (qq[i].typ == 2) {
                writeln(ans[i]);
            }
        }
        return 0;
    }

}

int main() {
    return dfcmd::Main();
}
```