題目描述

n*m的平面內(nèi)有K個不安全點，Q個詢問位置在(x,y)的人能走到多少個點？從(x,y)走到(x',y')是合法的，當(dāng)且僅當(dāng)(x,y)和(x',y')之間的矩形中不包含不安全點。

題解

問題相當(dāng)于平面中有若干障礙點，詢問以某一個點為四個角之一的不包含障礙點的矩形有多少個。

我們只需要考慮一個方向，接下來把整個圖旋轉(zhuǎn)90度再算即可?

那一個方向怎么求呢？

正難則反，我們可以考慮逆向思考

如圖，線與線交點表示一個坐標(biāo)，黑點表示不安全點，白點表示詢問點

白點右下方可以走到的點數(shù)=藍(lán)線內(nèi)的點數(shù)-陰影內(nèi)的點數(shù)

那陰影到底是什么呢？

它其實就是 每一高度的最右邊的黑點向下作垂線，與坐標(biāo)軸圍成的最大區(qū)域

換句話說，它滿足?如果上方的右邊界在下方的原右邊界右邊, 則下方的右邊界按上方的算

那我們可以以高度劃定區(qū)間建一顆線段樹，做一些特殊處理就可以求出陰影了 原諒我表達(dá)能力有限，具體看代碼吧 //正難則反 #include<bits/stdc++.h> #define mid ((l+r)>>1) using namespace std; const int N=100005; typedef long long ll; int n,m,K,Q,T_Max[N<<2],tot,Max; //T_Max表y在某一區(qū)間內(nèi)的x的最大值 ll ans[N],T_sum[N<<2],T_suml[N<<2]; struct node {int x,y,id,pd;node() {} node(int a,int b,int c,int d) {x=a;y=b;id=c;pd=d;} }a[N*2],tr[N],q[N]; bool cmp(const node &A,const node &B){return A.x<B.x||(A.x==B.x&&A.y<B.y)||(A.x==B.x&&A.y==B.y&&A.pd<B.pd); } int read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f; } ll query_sum(int u,int l,int r,int a,int b,int &mx){if (a<=l&&r<=b){if(mx>=T_Max[u]) return (ll)mx*(r-l+1);if(l==r) return mx=T_Max[u];int tt=T_Max[u<<1|1];ll res=0;if(mx>=tt){//即T_Max[u<<1|1]<=mx<T_Max[u<<1] res+=(ll)mx*(r-mid);res+=query_sum(u<<1,l,mid,a,b,mx);}else{//即mx<T_Max[u<<1|1](T_Max[u<<1]的范圍不限) res+=T_suml[u];res+=query_sum(u<<1|1,mid+1,r,a,b,mx);}mx=T_Max[u];return res;}ll s=0;if(b>mid) s+=query_sum(u<<1|1,mid+1,r,a,b,mx);//先更新上邊以更新右邊界 if(a<=mid) s+=query_sum(u<<1,l,mid,a,b,mx);return s; } void ins(int u,int l,int r,int y,int x){if(l==r){if(x>T_Max[u]) T_Max[u]=T_sum[u]=x;return;}if(y<=mid) ins(u<<1,l,mid,y,x);else ins(u<<1|1,mid+1,r,y,x);int tt=T_Max[u<<1|1];T_suml[u]=query_sum(u<<1,l,mid,l,mid,tt);//注意直接寫T_max[u<<1|1]的話可能會被修改T_Max[u]=max(T_Max[u<<1],T_Max[u<<1|1]);T_sum[u]=T_suml[u]+T_sum[u<<1|1];//如果T_max[u<<1|1]>[l,mid]區(qū)間的原右邊界,則[l,mid]區(qū)間的右邊界按T_max[u<<1|1]算 //否則，按原右邊界算 } void calc(){tot=0;for (int i=1;i<=K;i++) a[++tot]=node(tr[i].x,tr[i].y,i,0);for (int i=1;i<=Q;i++) a[++tot]=node(q[i].x,q[i].y,i,1);sort(a+1,a+tot+1,cmp);for (int i=1;i<=tot;i++){if(!a[i].pd) ins(1,1,m,a[i].y,a[i].x);else{Max=0;ans[a[i].id]+=query_sum(1,1,m,1,a[i].y,Max);//二維數(shù)點 Max=0;ans[a[i].id]-=query_sum(1,1,m,a[i].y,a[i].y,Max);//減去重復(fù)的同行/同列軸 }} } int main(){n=read();m=read();K=read();Q=read();for (int i=1;i<=K;i++) tr[i].x=read(),tr[i].y=read();for (int i=1;i<=Q;i++) q[i].x=read(),q[i].y=read(),ans[i]=0;for (int i=0;i<4;i++){calc();for (int i=1;i<=(m<<2); i++) T_sum[i]=T_suml[i]=T_Max[i]=0;//清零for (int j=1;j<=K;j++) tr[j].x=n-tr[j].x+1,swap(tr[j].x,tr[j].y);//旋轉(zhuǎn)90度 for (int j=1;j<=Q;j++) q[j].x=n-q[j].x+1,swap(q[j].x,q[j].y);swap(n,m);}for (int i=1;i<=Q;i++) printf("%lld\n",(ll)n*m-ans[i]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/HarryPotter-fan/p/11317080.html

總結(jié)

以上是生活随笔為你收集整理的HDU6089 恐怖分子（变形线段树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。