jsp网站开发需要哪些技术,网站建设仟首先金手指13,陕西省城乡住房建设厅网站,企业网站模板下载尽在题解#xff1a; 前一题不是强制在线#xff0c;后一题是强制在线 树套树空间会炸 说一下cdq分治树状数组 首先我们利用cdq分治使得查询和操作保证先后关系 然后矩阵查询变成4个矩阵的差 那么我们就可以运用扫描线的方法来维护了 时间nlogn^2,空间O(n) 后一题是kd-tree 查询的…题解 前一题不是强制在线后一题是强制在线 树套树空间会炸 说一下cdq分治树状数组 首先我们利用cdq分治使得查询和操作保证先后关系 然后矩阵查询变成4个矩阵的差 那么我们就可以运用扫描线的方法来维护了 时间nlogn^2,空间O(n) 后一题是kd-tree 查询的方法和线段树基本一样 如果矩阵被包含就返回答案如果不被包含就直接退出 否则递归下去 然后修改的话和替罪羊树一样 达到一定时候就重构 注意一下x相同insert和build要保证y的顺序区分左右 另外学习了一下map中用struct作为key的方法 虽然这题完全不用用 代码 #include bits/stdc.h
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (rint ih;it;i)
#define dep(i,t,h) for (rint it;ih;i--)
#define mid ((ht)/2)
#define me(x) memset(x,0,sizeof(x))
const int INF2e9;
const int N6e61e4;
char ss[124],*Ass,*Bss;
IL char gc()
{return AB(B(Ass)fread(ss,1,124,stdin),AB)?EOF:*A;
}
templateclass Tvoid read(T x)
{rint f1,c; while (cgc(),c48||c57) if (c-) f-1; x(c^48);while (cgc(),c47c58) x(x3)(x1)(c^48); x*f;
}
IL void umax(int x,int y)
{if (xy) xy;
}
IL void umin(int x,int y)
{if (xy) xy;
}
struct re{int d[2],v;
}p[N];
int cmp_d,ans,rt,num;
bool cmp(re x,re y)
{return x.d[cmp_d]y.d[cmp_d]||(x.d[cmp_d]y.d[cmp_d]x.d[cmp_d^1]y.d[cmp_d^1]);
}
struct kd
{int Mx[N],My[N],Nx[N],Ny[N],count2[N],ls[N],rs[N];IL void clear(){me(count2);me(ls); me(rs);}IL void updata(int x){count2[x]count2[ls[x]]count2[rs[x]]p[x].v;if (ls[x]){umax(Mx[x],Mx[ls[x]]);umax(My[x],My[ls[x]]);umin(Nx[x],Nx[ls[x]]);umin(Ny[x],Ny[ls[x]]);}if (rs[x]){umax(Mx[x],Mx[rs[x]]);umax(My[x],My[rs[x]]);umin(Nx[x],Nx[rs[x]]);umin(Ny[x],Ny[rs[x]]);}}int build(int h,int t,int o){cmp_do; nth_element(ph,pmid,pt1,cmp);int xmid;Mx[x]Nx[x]p[x].d[0];My[x]Ny[x]p[x].d[1];count2[x]p[x].v;if (h!x) ls[x]build(h,mid-1,o^1); else ls[x]0;if (x!t) rs[x]build(mid1,t,o^1); else rs[x]0;updata(x);return x; }void insert(int k,int x,int y,int z,int o){if (!k){knum;Mx[num]Nx[num]p[num].d[0];My[num]Ny[num]p[num].d[1];count2[num]p[num].vz;return;}if (p[k].d[0]xp[k].d[1]y){count2[k]z; p[k].vz; return;}if (!o)if (xp[k].d[0]||(xp[k].d[0]yp[k].d[1])) insert(ls[k],x,y,z,o^1);else insert(rs[k],x,y,z,o^1);else if (yp[k].d[1]||(yp[k].d[1]xp[k].d[0])) insert(ls[k],x,y,z,o^1);else insert(rs[k],x,y,z,o^1); updata(k);}void query(int k,int x1,int x2,int y1,int y2){if (!k||Mx[k]x1||Nx[k]x2||My[k]y1||Ny[k]y2) return;if (x2Mx[k]Nx[k]x1y2My[k]Ny[k]y1){anscount2[k]; return;}if (x1p[k].d[0]p[k].d[0]x2y1p[k].d[1]p[k].d[1]y2)ansp[k].v;query(ls[k],x1,x2,y1,y2); query(rs[k],x1,x2,y1,y2);}
}kd;
struct re1{int a,b;
};
struct cmp2
{bool operator() (const re1 x,const re1 y){if (x.ay.a||(x.ay.ax.by.b)) return(1); else return(0);}
};
mapre1,int,cmp2 M;
int main()
{int m;freopen(1.in,r,stdin);freopen(1.out,w,stdout);read(m);int cnt0,rt0,i0;while (1){i;ans0;int k;read(k);if (k3) break;if (k1){int x,y,z;read(x); read(y); read(z);x^ans; y^ans; z^ans;re1 k3(re1){x,y};int kkM[k3];if (!kk) p[num1].d[0]x,p[num1].d[1]y,kknum1;M[k3]kk;kd.insert(rt,x,y,z,0);cnt;if (cnt%100000){ kd.clear();rtkd.build(1,num,0);} } else{int x1,x2,y1,y2;read(x1),read(y1),read(x2),read(y2);x1^ans,x2^ans,y1^ans,y2^ans;ans0;kd.query(rt,x1,x2,y1,y2);coutansendl;}}return 0;
} 转载于:https://www.cnblogs.com/yinwuxiao/p/9288414.html
