Tree 園丁的煩惱 HYSBZ - 1935

https://www.lydsy.com/JudgeOnline/problem.php?id=1935

基礎三維偏序問題 但是資料範圍大 需要離散化

還有 hysbz上數組開小了會WA 一直T 加了個輸入挂才過。。

#include <bits/stdc++.h>
using namespace std;

struct node1
{
    int tp;
    int x;
    int y;
    int val;
};

struct node2
{
    int l;
    int r;
    int val;
};

node1 order[2500010],tmp[2500010];
node2 tree[10000010];
int posx[2500010],posy[2500010],ans[500010];
int n,q,tot,nx,ny;

template <class T>
inline void _cin1(T &ret)
{
    char c;
    ret = 0;
    while((c = getchar()) < '0' || c > '9');
    while(c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0');
        c = getchar();
    }
}


void build(int l,int r,int cur)
{
    int m;
    tree[cur].l=l;
    tree[cur].r=r;
    tree[cur].val=0;
    if(l==r) return;
    m=(l+r)/2;
    build(l,m,2*cur);
    build(m+1,r,2*cur+1);
}

void update(int tar,int val,int cur)
{
    tree[cur].val+=val;
    if(tree[cur].l==tree[cur].r) return;
    if(tar<=tree[2*cur].r) update(tar,val,2*cur);
    else update(tar,val,2*cur+1);
}

int query(int pl,int pr,int cur)
{
    int res;
    if(pl<=tree[cur].l&&tree[cur].r<=pr)
    {
        return tree[cur].val;
    }
    res=0;
    if(pl<=tree[2*cur].r) res+=query(pl,pr,2*cur);
    if(pr>=tree[2*cur+1].l) res+=query(pl,pr,2*cur+1);
    return res;
}

void cdq(int l,int r)
{
    int m,p,q,cnt,i;
    if(l==r) return;
    m=(l+r)/2;
    cdq(l,m);
    cdq(m+1,r);
    p=l,q=m+1,cnt=l;
    while(p<=m&&q<=r)
    {
        if(order[p].x<=order[q].x)
        {
            if(order[p].tp==1) update(order[p].y,order[p].val,1);
            tmp[cnt++]=order[p++];
        }
        else
        {
            if(order[q].tp==2) ans[order[q].val]-=query(1,order[q].y,1);
            else if(order[q].tp==3) ans[order[q].val]+=query(1,order[q].y,1);
            tmp[cnt++]=order[q++];
        }
    }
    while(q<=r)
    {
        if(order[q].tp==2) ans[order[q].val]-=query(1,order[q].y,1);
        else if(order[q].tp==3) ans[order[q].val]+=query(1,order[q].y,1);
        tmp[cnt++]=order[q++];
    }
    for(i=l;i<p;i++)
    {
        if(order[i].tp==1) update(order[i].y,-order[i].val,1);
    }
    while(p<=m) tmp[cnt++]=order[p++];
    for(i=l;i<=r;i++) order[i]=tmp[i];
}

int main()
{
    int i,x1,y1,x2,y2;
    //scanf("%d%d",&n,&q);
    _cin1(n);
    _cin1(q);
    tot=0,nx=0,ny=0;
    for(i=1;i<=n;i++)
    {
        //scanf("%d%d",&x1,&y1);
        _cin1(x1);
        _cin1(y1);
        tot++;
        order[tot].tp=1,order[tot].x=x1,order[tot].y=y1,order[tot].val=1;
        posx[++nx]=x1,posy[++ny]=y1;
    }
    for(i=1;i<=q;i++)
    {
        //scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        _cin1(x1);
        _cin1(y1);
        _cin1(x2);
        _cin1(y2);
        if(x1-1>=0)
        {
            tot++;
            order[tot].tp=2,order[tot].x=x1-1,order[tot].y=y2,order[tot].val=i;
            posx[++nx]=x1-1,posy[++ny]=y2;
        }
        if(y1-1>=0)
        {
            tot++;
            order[tot].tp=2,order[tot].x=x2,order[tot].y=y1-1,order[tot].val=i;
            posx[++nx]=x2,posy[++ny]=y1-1;
        }
        if(x1-1>=0&&y1-1>=0)
        {
            tot++;
            order[tot].tp=3,order[tot].x=x1-1,order[tot].y=y1-1,order[tot].val=i;
            posx[++nx]=x1-1,posy[++ny]=y1-1;
        }
        tot++;
        order[tot].tp=3,order[tot].x=x2,order[tot].y=y2,order[tot].val=i;
        posx[++nx]=x2,posy[++ny]=y2;
    }
    sort(posx+1,posx+nx+1);
    nx=unique(posx+1,posx+nx+1)-posx-1;
    sort(posy+1,posy+ny+1);
    ny=unique(posy+1,posy+ny+1)-posy-1;
    for(i=1;i<=tot;i++)
    {
        order[i].x=lower_bound(posx+1,posx+nx+1,order[i].x)-posx;
        order[i].y=lower_bound(posy+1,posy+ny+1,order[i].y)-posy;
    }
    build(1,ny,1);
    cdq(1,tot);
    for(i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}