【題目分析】

? ? 直接x,y二維輪番劃分，暴力即可。

? ? 套上替罪羊，打碎重構，對于時間復雜度有了保證。

? ? 寫起來好麻煩，重構的技巧很棒！

【代碼】

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;#define maxn 200005 #define inf 0x3f3f3f3f #define lim 0.7 #define L t[o].c[0] #define R t[o].c[1] #define mid (l+r>>1) #define F(i,j,k) for (int i=j;i<=k;++i)struct node{int d[2],c[2];int mx[2],mn[2],sum,v,siz,D;int& operator [] (int x){return d[x];} }t[maxn],now; int p[maxn]; int opt=0,D,rt=0,ans=0,tot=0,cnt; inline bool cmp(int x,int y){return t[x][D]<t[y][D];} void pushup(int k) {for (int i=0;i<2;++i){t[k].mn[i]=min(t[t[k].c[0]].mn[i],min(t[t[k].c[1]].mn[i],t[k].mn[i]));t[k].mx[i]=max(t[t[k].c[0]].mx[i],max(t[t[k].c[1]].mx[i],t[k].mx[i]));}t[k].sum=t[t[k].c[0]].sum+t[t[k].c[1]].sum+t[k].v;t[k].siz=t[t[k].c[0]].siz+t[t[k].c[1]].siz+1; } inline int build(int l,int r,int dir){D=dir;nth_element(p+l,p+mid,p+r+1,cmp);int o=p[mid];t[o].D=dir;F(i,0,1) t[o].mn[i]=t[o].mx[i]=t[o][i];t[o].sum=t[o].v;L=l<mid ? build(l,mid-1,dir^1) : 0;R=mid<r ? build(mid+1,r,dir^1) : 0;pushup(o);return o; } inline void dfs(int o){if (!o) return;dfs(L);p[++cnt]=o;dfs(R); } inline void rebuild(int &o){cnt=0;dfs(o);o=build(1,cnt,t[o].D); }void ins(int &o,int dir) {if (!o){o=++tot;t[o]=now;for (int i=0;i<2;++i) t[o].mn[i]=t[o].mx[i]=t[o].d[i];t[o].siz=1;t[o].D=dir;t[o].sum=t[o].v;return ;}if (now.d[dir]<t[o].d[dir]){ins(t[o].c[0],dir^1);pushup(o);if ((double)t[t[o].c[0]].siz>(double)t[o].siz*lim) rebuild(o);}else{ins(t[o].c[1],dir^1);pushup(o);if ((double)t[t[o].c[1]].siz>(double)t[o].siz*lim) rebuild(o);} }void print(int o){if (!o) return;printf("%d t[o].mn[0]=%d t[o].mn[1]=%d t[o].mx[0]=%d t[o].mx[1]=%d\n",o,t[o].mn[0],t[o].mn[1],t[o].mx[0],t[o].mx[1]);print(L);print(R); }int query(int o,int x1,int y1,int x2,int y2) {if (!o) return 0;if (t[o].mn[0]>=x1 && t[o].mn[1]>=y1 && t[o].mx[0]<=x2 && t[o].mx[1]<=y2)return t[o].sum;else{int ret=0;if (t[o].d[0]>=x1&&t[o].d[0]<=x2&&t[o].d[1]>=y1&&t[o].d[1]<=y2)ret+=t[o].v;if (t[t[o].c[0]].mn[0]>x2||t[t[o].c[0]].mx[0]<x1||t[t[o].c[0]].mn[1]>y2||t[t[o].c[0]].mx[1]<y1);else ret+=query(t[o].c[0],x1,y1,x2,y2);if (t[t[o].c[1]].mn[0]>x2||t[t[o].c[1]].mx[0]<x1||t[t[o].c[1]].mn[1]>y2||t[t[o].c[1]].mx[1]<y1);else ret+=query(t[o].c[1],x1,y1,x2,y2);return ret;} }int main() {for (int i=0;i<2;++i) t[rt].mx[i]=-inf,t[rt].mn[i]=inf;t[rt].siz=t[rt].sum=t[rt].v=0; scanf("%*d");while (scanf("%d",&opt)!=EOF&&opt!=3){if (opt==1){scanf("%d%d%d",&now.d[0],&now.d[1],&now.v);now.d[0]^=ans; now.d[1]^=ans; now.v^=ans;ins(rt,1);}else{int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1^=ans;y1^=ans;x2^=ans;y2^=ans;printf("%d\n",ans=query(rt,x1,y1,x2,y2));}} }

　　

轉載于:https://www.cnblogs.com/SfailSth/p/6231276.html

總結

以上是生活随笔為你收集整理的BZOJ 4066 简单题 ——KD-Tree套替罪羊树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。