- Code:
- #include<bits/stdc++.h>
- #define setIO(s) freopen(s".in","r",stdin), freopen(s".out","w",stdout)
- #define maxn 1000000
- #define mid ((l+r)>>1)
- using namespace std;
- int d,root,tot, W;
- struct Node
- {
- int ch[2],p[2],minv[2],maxv[2],w,sumv;
- }t[maxn];
- bool cmp(Node a,Node b)
- {
- return a.p[d]==b.p[d]?a.p[d^1]<b.p[d^1]:a.p[d]<b.p[d];
- }
- int isin(int x,int x1,int y1,int x2,int y2)
- {
- if(x1 <= t[x].minv[0] && x2>= t[x].maxv[0] && y1 <= t[x].minv[1] && y2>= t[x].maxv[1])
- return 1;
- else
- return 0;
- }
- int isout(int x,int x1,int y1,int x2,int y2)
- {
- if(x1> t[x].maxv[0] || x2 <t[x].minv[0] || y1> t[x].maxv[1] || y2 <t[x].minv[1])
- return 1;
- else
- return 0;
- }
- void pushup(int x,int y)
- {
- for(int i=0;i<2;++i)
- {
- t[x].minv[i]=min(t[x].minv[i], t[y].minv[i]);
- t[x].maxv[i]=max(t[x].maxv[i], t[y].maxv[i]);
- }
- t[x].sumv+=t[y].sumv;
- }
- void insert(int &x,int o)
- {
- if(!x)
- {
- x = tot;
- t[tot].minv[0]=t[tot].maxv[0]=t[tot].p[0];
- t[tot].minv[1]=t[tot].maxv[1]=t[tot].p[1];
- t[tot].sumv=t[tot].w;
- t[tot].ch[0]=t[tot].ch[1]=0;
- return;
- }
- d=o;
- if(cmp(t[tot], t[x]) == 1)
- {
- insert(t[x].ch[0], o^1);
- pushup(x, tot);
- }
- else
- {
- insert(t[x].ch[1],o^1);
- pushup(x, tot);
- }
- }
- int query(int x,int x1,int y1,int x2,int y2)
- {
- if(isout(x, x1, y1, x2, y2) || !x) return 0;
- if(isin(x, x1, y1, x2, y2)) return t[x].sumv;
- int tmp=0;
- if(t[x].p[0]>= x1 && t[x].p[0] <= x2 && t[x].p[1]>= y1 && t[x].p[1] <= y2) tmp += t[x].w;
- if(t[x].ch[0]) tmp += query(t[x].ch[0], x1, y1, x2, y2);
- if(t[x].ch[1]) tmp += query(t[x].ch[1], x1, y1, x2, y2);
- return tmp;
- }
- int build(int l,int r,int o)
- {
- d=o;
- nth_element(t+l,t+mid,t+1+r,cmp);
- t[mid].minv[0]=t[mid].maxv[1]=t[mid].p[0];
- t[mid].minv[1]=t[mid].maxv[1]=t[mid].p[1];
- t[mid].sumv = t[mid].w;
- t[mid].ch[0]=t[mid].ch[1]=0;
- if(mid> l)
- {
- t[mid].ch[0] = build(l, mid - 1, o ^ 1);
- pushup(mid, t[mid].ch[0]);
- }
- if(r> mid)
- {
- t[mid].ch[1] = build(mid + 1, r, o ^ 1);
- pushup(mid, t[mid].ch[1]);
- }
- return mid;
- }
- int main()
- {
- // setIO("input");
- int S,opt,i,j,x,y,k,root = 0 ,a,b,c,d,ii=0;
- scanf("%d%d",&W,&S);
- for(ii=1;;++ii)
- {
- scanf("%d",&opt);
- if(opt==1)
- {
- scanf("%d%d%d",&x,&y,&k);
- ++tot;
- t[tot].p[0]=x, t[tot].p[1]=y, t[tot].w = k;
- insert(root, 0);
- }
- if(opt==2)
- {
- scanf("%d%d%d%d",&a,&b,&c,&d);
- printf("%d\n",query(root, a, b, c, d));
- }
- if(opt==3) break;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3100273.html