Description

GFS打算去郊外建所别墅，享受生活，于是他耗费巨资买下了一块风水宝地，但令他震惊的是，一群DSJ对GFS的富贵生活深恶痛绝，决定打洞以搞破坏。

现在我们简化一下这个问题，在这片土地上会按顺序发生一系列事件。

①一只DSJ在(x,y) 这个点打了一个洞。

②有着高雅品味GFS想建一个

等腰直角三角形的别墅，即由

(x,y) ,(x+d,y) ,(x,y+d) 三点围成的三角形，但为了地基的牢固，他想知道

当前这块三角形土地内的洞的个数。

GFS现在对DSJ已经忍无可忍了，请你帮他回答这些询问。

初始土地上没有洞。GFS毕竟是GFS，你可以认为土地无限大。

 

Input

第一行一个整数 n，表示事件数。接下来n行，每行3个

非负整数x ，y ，d 。

若

d=0 表示DSJ打洞的事件。否则表示GFS建房的询问。

Output

对每个询问输出一个整数，表示当时询问的三角形内的洞的个数。

 

Sample Input

输入1： 8 1 3 0 1 5 0 3 6 0 4 4 0 2 6 0 1 5 3 1 5 4 1 1 1 输入2： 4 1 5 0 3 7 0 2 5 6 2 3 4

Sample Output

输出1： 3 3 0 输出2： 1 0

 

Data Constraint

30%的数据n<=3333 。

另30% 的数据 GFS只会在DSJ打完洞后才开始询问,xi,yi<=333333 。

100%的数据 1<=n<=88888，xi,yi<=3333333 。

分析

我们可以发现，在直角等腰三角形内的点必然满足：x≤x1≤x+d,y≤y1≤y+d,x+y≤x1+y1≤x+y+d

那么把x+y看作第三维，这就是一个四维偏序问题

之前也做过类似的Thersa与数据结构，为了节省(tou)时间(lan)就直接调用了以前写的程序，改了改读入就行

时间O(nlog³n)

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define rep(i,a,b) for (i=a;i<=b;i++)#define lowbit(x) x&-xconst int N=88889;using namespace std;struct Node {    int l,r,key,mak,dat,sum;}t[50*N];int tcnt;struct Point {    int x,y,z;};struct Query {    Point p;    int r,t,id;}q[N],a[2*N];int qcnt;int rt[N];int sy,sq,sh,n,m,top;int ans[N],y[N];void Update(int x) {    t[x].sum=t[x].dat+t[t[x].l].sum+t[t[x].r].sum;}void Left_Rotate(int &x) {    int s=t[x].r;    t[x].r=t[s].l;t[s].l=x;    Update(x);Update(s);    x=s;}void Right_Rotate(int &x) {    int s=t[x].l;    t[x].l=t[s].r;t[s].r=x;    Update(x);Update(s);    x=s;}void Insert(int &x,int mak,int dat) {    if (!x) {        x=++tcnt;t[x].l=t[x].r=0;t[x].mak=mak;t[x].sum=t[x].dat=dat;t[x].key=rand();        return;    }    if (mak
           
            t[x].key) Right_Rotate(x); } else { Insert(t[x].r,mak,dat); if (t[t[x].r].key>t[x].key) Left_Rotate(x); } Update(x);}int Get_Suk(int x,int mak) { if (!x) return 0; if (mak
            
             >1; if (y[mid]>x) r=mid-1; else l=mid; } return l+1;}void Fix() { int i; sort(a+1,a+sh+1,Cmp); sy=0; rep(i,1,sh) if (a[i].t<2) y[++sy]=a[i].p.y; sort(y+1,y+sy+1); sy=unique(y+1,y+sy+1)-(y+1); rep(i,1,sy+1) rt[i]=0;tcnt=0; rep(i,1,sh) { if (a[i].t<2) Add(Lower_Bound(1,sy,a[i].p.y),a[i].p.z,a[i].t); else { int l=Lower_Bound(1,sy,a[i].p.y-1),r=Lower_Bound(1,sy,a[i].p.y+a[i].r); if (l==r) continue; ans[a[i].id]+=(Get_Sum(r,a[i].p.z,a[i].r)-Get_Sum(l,a[i].p.z,a[i].r))*(a[i].t-3); } }}bool In(Point a,Point b,int r) { return a.x>=b.x&&a.y>=b.y&&a.z>=b.z&&a.x<=b.x+r&&a.y<=b.y+r&&a.z<=b.z+r;}void Work(int l,int r) { int so=0,sa=0,i,j; rep(i,l,r) if (!q[i].t) sa++; else so++; if (!sa||!so) return; if (r-l+1<=400) { rep(i,l,r-1) rep(j,i+1,r) if (!q[j].t&&In(q[i].p,q[j].p,q[j].r)) ans[q[j].id]+=q[i].t; return; } int mid=l+r>>1; Work(l,mid); Work(mid+1,r); sh=0; rep(i,l,mid) if (q[i].t!=0) a[++sh]=q[i]; int hs=sh; rep(i,mid+1,r) if (!q[i].t) { a[++sh]=q[i];a[sh].p.x--;a[sh].t=2; a[++sh]=q[i];a[sh].p.x+=q[i].r;a[sh].t=4; } if (hs&&sh>hs) Fix();}void Print() { int i; rep(i,1,sq) if (!q[i].t) printf("%d\n",ans[q[i].id]);}int main() { Init(); Work(1,sq); Print();}