汽车便宜网站建设,医疗器械研发,西安活动公司,安徽省途顺建设工程有限公司网站【题目分析】 直接x,y二维轮番划分#xff0c;暴力即可。 套上替罪羊#xff0c;打碎重构#xff0c;对于时间复杂度有了保证。 写起来好麻烦#xff0c;重构的技巧很棒#xff01; 【代码】 #include cstdio
#include cstring
#include iostream…【题目分析】 直接x,y二维轮番划分暴力即可。 套上替罪羊打碎重构对于时间复杂度有了保证。 写起来好麻烦重构的技巧很棒 【代码】 #include cstdio
#include cstring
#include iostream
#include algorithmusing 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 (lr1)
#define F(i,j,k) for (int ij;ik;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 opt0,D,rt0,ans0,tot0,cnt;
inline bool cmp(int x,int y){return t[x][D]t[y][D];}
void pushup(int k)
{for (int i0;i2;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].sumt[t[k].c[0]].sumt[t[k].c[1]].sumt[k].v;t[k].sizt[t[k].c[0]].sizt[t[k].c[1]].siz1;
}
inline int build(int l,int r,int dir){Ddir;nth_element(pl,pmid,pr1,cmp);int op[mid];t[o].Ddir;F(i,0,1) t[o].mn[i]t[o].mx[i]t[o][i];t[o].sumt[o].v;Llmid ? build(l,mid-1,dir^1) : 0;Rmidr ? build(mid1,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){cnt0;dfs(o);obuild(1,cnt,t[o].D);
}void ins(int o,int dir)
{if (!o){otot;t[o]now;for (int i0;i2;i) t[o].mn[i]t[o].mx[i]t[o].d[i];t[o].siz1;t[o].Ddir;t[o].sumt[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 ret0;if (t[o].d[0]x1t[o].d[0]x2t[o].d[1]y1t[o].d[1]y2)rett[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 retquery(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 retquery(t[o].c[1],x1,y1,x2,y2);return ret;}
}int main()
{for (int i0;i2;i) t[rt].mx[i]-inf,t[rt].mn[i]inf;t[rt].sizt[rt].sumt[rt].v0; scanf(%*d);while (scanf(%d,opt)!EOFopt!3){if (opt1){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,ansquery(rt,x1,y1,x2,y2));}}
}转载于:https://www.cnblogs.com/SfailSth/p/6231276.html
