JZOJ 6484 不安的前方

完成了我人生第二道 CDQ 分治题（上一道是我自己出的）……
告诉我，你和 JZOJ 4419 啥关系（

考虑如何判定一个点是否在一个等腰直角三角形内部。
这里以 (x,y),(x+z,y),(x,y+z) 组成的三角形为例（即 type=1 的情况）。
显然点 (x′,y′) 在这个三角形内部，当且仅当 x+y≤x′+y′≤x+y+z,x≤x′,y≤y′。

首先假设所有询问都在修改后。
看起来是个三维偏序。然而，实际上，容易发现，若 x+y≤x′+y′≤x+y+z，则在剩下的两个条件中，必定至少满足一个。
这意味着什么？
这意味着，仅需用总数分别减去不满足其中一个条件的数量即可。
这样就变成二维偏序了。

当然，再套路地做两次二维偏序很麻烦……
所以实际上可以对 x+y 做扫描线，然后用两个树状数组分别维护 x 和 y 的贡献。
这样就可以一遍扫描线解决一个一维偏序（雾，但是没说错啊）和两个二维偏序了。

然后丢上 CDQ 分治即可。
复杂度 O(nlog2n)。

代码：

#include <cstdio>
#include <algorithm>
#define lowbit(x) ((x) & -(x))
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x,1);
}

const int N = 3e5;
const int M = 3e5;
int num,n,m,all;
int tot[4],qry_tot,ans[M + 5];
struct note
{
    int op,x,y,z;
    inline bool operator<(const note &o) const
    {
        return x + y + z < o.x + o.y + o.z || (x + y + z == o.x + o.y + o.z && op < o.op);
    }
} a[4][M + 5],e[(M << 1) + 5];
int c[2][N + 5];
inline void update(int op,int x,int k)
{
    for(;x;x -= lowbit(x))
        c[op][x] += k;
}
inline int query(int op,int x)
{
    int ret = 0;
    for(;x <= n;x += lowbit(x))
        ret += c[op][x];
    return ret;
}
void cdq(note *a,int l,int r)
{
    if(l == r)
        return ;
    int mid = l + r >> 1,n = 0;
    cdq(a,l,mid),cdq(a,mid + 1,r);
    for(register int i = l;i <= mid;++i)
        if(!a[i].op)
            e[++n] = (note){0,a[i].x,a[i].y,0},e[++n] = (note){-1,a[i].x,a[i].y,a[i].z + 1};
    for(register int i = mid + 1;i <= r;++i)
        if(a[i].op)
            e[++n] = (note){a[i].op,a[i].x,a[i].y,0};
    sort(e + 1,e + n + 1);
    for(register int i = 1;i <= n;++i)
    {
        if(!e[i].op)
            update(0,all,1),update(0,e[i].x - 1,-1),update(1,e[i].y - 1,-1);
        else if(~e[i].op)
            ans[e[i].op] += query(0,e[i].x) + query(1,e[i].y);
        else
            update(0,all,-1),update(0,e[i].x - 1,1),update(1,e[i].y - 1,1);
    }
}
int main()
{
    freopen("frontier.in","r",stdin),freopen("frontier.out","w",stdout);
    read(num),read(n),read(m),all = n;
    int op,type,x,y,z;
    for(register int i = 1;i <= m;++i)
    {
        read(op);
        if(op == 1)
        {
            read(type),read(x),read(y),read(z);
            if(type == 1)
                a[0][++tot[0]] = (note){0,x,y,z};
            else if(type == 2)
                a[1][++tot[1]] = (note){0,x,n - y + 1,z};
            else if(type == 3)
                a[2][++tot[2]] = (note){0,n - x + 1,y,z};
            else
                a[3][++tot[3]] = (note){0,n - x + 1,n - y + 1,z};
        }
        else
            read(x),read(y),++qry_tot,
            a[0][++tot[0]] = (note){qry_tot,x,y,0},
            a[1][++tot[1]] = (note){qry_tot,x,n - y + 1,0},
            a[2][++tot[2]] = (note){qry_tot,n - x + 1,y,0},
            a[3][++tot[3]] = (note){qry_tot,n - x + 1,n - y + 1,0};
    }
    for(register int i = 0;i < 4;++i)
        if(tot[i])
            cdq(a[i],1,tot[i]);
    for(register int i = 1;i <= qry_tot;++i)
        printf("%d\n",ans[i]);
}