门户网站的建设费用,seo外包公司兴田德润,济南城之运维网络科技,策划公司属于什么行业题目描述 n*m的平面内有K个不安全点#xff0c;Q个询问位置在(x,y)的人能走到多少个点#xff1f;从(x,y)走到(x,y)是合法的#xff0c;当且仅当(x,y)和(x,y)之间的矩形中不包含不安全点。 题解 问题相当于平面中有若干障碍点#xff0c;询问以某一个点为四个角之一的不包含… 题目描述 n*m的平面内有K个不安全点Q个询问位置在(x,y)的人能走到多少个点从(x,y)走到(x,y)是合法的当且仅当(x,y)和(x,y)之间的矩形中不包含不安全点。 题解 问题相当于平面中有若干障碍点询问以某一个点为四个角之一的不包含障碍点的矩形有多少个。 我们只需要考虑一个方向接下来把整个图旋转90度再算即可 那一个方向怎么求呢 正难则反我们可以考虑逆向思考 如图线与线交点表示一个坐标黑点表示不安全点白点表示询问点 白点右下方可以走到的点数蓝线内的点数-阴影内的点数 那阴影到底是什么呢 它其实就是 每一高度的最右边的黑点向下作垂线与坐标轴围成的最大区域 换句话说它满足 如果上方的右边界在下方的原右边界右边, 则下方的右边界按上方的算 那我们可以以高度划定区间建一颗线段树做一些特殊处理就可以求出阴影了 原谅我表达能力有限具体看代码吧 //正难则反
#includebits/stdc.h
#define mid ((lr)1)
using namespace std;
const int N100005;
typedef long long ll;
int n,m,K,Q,T_Max[N2],tot,Max;
//T_Max表y在某一区间内的x的最大值
ll ans[N],T_sum[N2],T_suml[N2];
struct node {int x,y,id,pd;node() {} node(int a,int b,int c,int d) {xa;yb;idc;pdd;}
}a[N*2],tr[N],q[N];
bool cmp(const node A,const node B){return A.xB.x||(A.xB.xA.yB.y)||(A.xB.xA.yB.yA.pdB.pd);
}
int read(){int x0,f1;char chgetchar();while (ch0||ch9){if(ch-) f-1;chgetchar();}while (ch0ch9)x(x1)(x3)ch-0,chgetchar();return x*f;
}
ll query_sum(int u,int l,int r,int a,int b,int mx){if (alrb){if(mxT_Max[u]) return (ll)mx*(r-l1);if(lr) return mxT_Max[u];int ttT_Max[u1|1];ll res0;if(mxtt){//即T_Max[u1|1]mxT_Max[u1] res(ll)mx*(r-mid);resquery_sum(u1,l,mid,a,b,mx);}else{//即mxT_Max[u1|1](T_Max[u1]的范围不限) resT_suml[u];resquery_sum(u1|1,mid1,r,a,b,mx);}mxT_Max[u];return res;}ll s0;if(bmid) squery_sum(u1|1,mid1,r,a,b,mx);//先更新上边以更新右边界 if(amid) squery_sum(u1,l,mid,a,b,mx);return s;
}
void ins(int u,int l,int r,int y,int x){if(lr){if(xT_Max[u]) T_Max[u]T_sum[u]x;return;}if(ymid) ins(u1,l,mid,y,x);else ins(u1|1,mid1,r,y,x);int ttT_Max[u1|1];T_suml[u]query_sum(u1,l,mid,l,mid,tt);//注意直接写T_max[u1|1]的话可能会被修改T_Max[u]max(T_Max[u1],T_Max[u1|1]);T_sum[u]T_suml[u]T_sum[u1|1];//如果T_max[u1|1][l,mid]区间的原右边界,则[l,mid]区间的右边界按T_max[u1|1]算 //否则按原右边界算
}
void calc(){tot0;for (int i1;iK;i) a[tot]node(tr[i].x,tr[i].y,i,0);for (int i1;iQ;i) a[tot]node(q[i].x,q[i].y,i,1);sort(a1,atot1,cmp);for (int i1;itot;i){if(!a[i].pd) ins(1,1,m,a[i].y,a[i].x);else{Max0;ans[a[i].id]query_sum(1,1,m,1,a[i].y,Max);//二维数点 Max0;ans[a[i].id]-query_sum(1,1,m,a[i].y,a[i].y,Max);//减去重复的同行/同列轴 }}
}
int main(){nread();mread();Kread();Qread();for (int i1;iK;i) tr[i].xread(),tr[i].yread();for (int i1;iQ;i) q[i].xread(),q[i].yread(),ans[i]0;for (int i0;i4;i){calc();for (int i1;i(m2); i) T_sum[i]T_suml[i]T_Max[i]0;//清零for (int j1;jK;j) tr[j].xn-tr[j].x1,swap(tr[j].x,tr[j].y);//旋转90度 for (int j1;jQ;j) q[j].xn-q[j].x1,swap(q[j].x,q[j].y);swap(n,m);}for (int i1;iQ;i) printf(%lld\n,(ll)n*m-ans[i]);return 0;
} 转载于:https://www.cnblogs.com/HarryPotter-fan/p/11317080.html
