noip2019集训测试赛（六）C.恐怖分子

本文主要是介绍noip2019集训测试赛（六）C.恐怖分子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

有一个 n×m 的网格和 q 名旅行者。初始时第 i 名旅行者在网格 (xi,yi) 上。

不幸的是，这 n×m 个网格中，有 K 个网格里是有恐怖分子的，所以这 K 个网格是不安全的。为了安全起见，旅行者可以从初始坐标 (x1,y1) 走到网格 (x2,y2) 当且仅当对于所有满足 min(x1,x2)≤x≤max(x1,x2),min(y1,y2)≤y≤max(y1,y2) 的网格 (x,y) 都是安全的。

现在，对于每个旅行者，你都想知道他们可以走到多少个网格（含初始位置）。

Input

第一行包含4个整数 n,m,K,q(1≤n,m,K,q≤105)

接下来 K 行，每行包含两个整数 (ai,bi)(1≤ai≤n,1≤bi≤m) ，表示该网格是不安全的。数据保证这些坐标互不相同。

接下来 Q 行，每行包含两个整数 (xi,yi)(1≤xi≤n,1≤yi≤m) ，表示每个旅行者的初始位置。数据保证初始位置一定是安全的。

Output

对于每个旅行者，输出一行表示答案。

Solution

线段树神仙题。

本题直接算可行部分较难做，所以我们采用计算总体减去不可行部分的方法。
对于每一个恐怖分子，将其设为原点，把总体分成第一二三四象限计算。
利用类似李超线段树的方法，可以维护每个x最大的y值。

思考一个简单的问题，若要得到第一象限x的的矩阵，右边的x的最大y值应大于左边的y值。
所以我们在统计面积sum时还要统计左儿子的面积suml，统计时分类讨论：

若当前左边的mx大于整个区间，直接加上 $m x * (r - l + 1)$ 。
若当前左边的mx大于等于右边，直接加上mx*右儿子区间x长度，再统计左儿子区间y更高的矩阵。
若当前左边的mx小于右边，加上suml，再统计右儿子区间可延伸的面积。

至于一二三四区间，将坐标旋转九十度即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
long long ans[N],sum[N<<2],maxn[N<<2],suml[N<<2];
int n,m,k,q,t;
struct data{int x,y,id;
}a[N],b[N],c[N<<1];
bool cmp(data u,data v){if(u.x!=v.x) return u.x<v.x;if(u.y!=v.y) return u.y<v.y;return u.id<v.id;
}
long long query(int id,int l,int r,int ql,int qr,long long &mx){//cout<<id<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;if(id==0) exit(0); if(ql<=l&&r<=qr){if(mx>maxn[id])return mx*(r-l+1);if(l==r) return mx=maxn[id];int mid=(l+r)/2;long long tmp=maxn[id*2+1],res=0;if(mx>=tmp){res+=mx*(r-mid);res+=query(id*2,l,mid,ql,qr,mx);}else{res+=suml[id];res+=query(id*2+1,mid+1,r,ql,qr,mx);}mx=maxn[id];return res;}long long res=0;int mid=(l+r)/2;if(qr>mid) res+=query(id*2+1,mid+1,r,ql,qr,mx);if(ql<=mid) res+=query(id*2,l,mid,ql,qr,mx);return res;
}
void update(int id,int l,int r,int k,long long v){//cout<<id<<" "<<l<<" "<<r<<" "<<k<<endl;if(l==r){if(v>maxn[id])maxn[id]=sum[id]=v;return;}int mid=(l+r)/2;if(k<=mid) update(id*2,l,mid,k,v);else update(id*2+1,mid+1,r,k,v);long long tmp=maxn[id*2+1];suml[id]=query(id*2,l,mid,l,mid,tmp);sum[id]=suml[id]+sum[id*2];maxn[id]=max(maxn[id*2],maxn[id*2+1]);
}
void work(){for(int i=1;i<=k;i++)c[++t]=a[i];//,cout<<c[t].x<<" "<<c[t].y<<endl;for(int i=1;i<=q;i++)c[++t]=b[i];//,cout<<c[t].x<<" "<<c[t].y<<endl;sort(c+1,c+t+1,cmp);for(int i=1;i<=t;i++){//cout<<i<<" "<<c[i].id<<" "<<c[i].x<<" "<<c[i].y<<endl;if(!c[i].id) update(1,1,m,c[i].y,c[i].x);else{long long mx=0;ans[c[i].id]+=query(1,1,m,1,c[i].y,mx);mx=0;ans[c[i].id]-=query(1,1,m,c[i].y,c[i].y,mx);}//cout<<i<<":ok"<<endl;}
}
int main(){scanf("%d%d%d%d",&n,&m,&k,&q);for(int i=1;i<=k;i++)scanf("%d%d",&a[i].x,&a[i].y);for(int i=1;i<=q;i++){scanf("%d%d",&b[i].x,&b[i].y);b[i].id=i;}for(int i=0;i<4;i++){t=0;for(int j=1;j<=(m<<2);j++)sum[j]=maxn[j]=suml[j]=0;work();for(int j=1;j<=k;j++){//旋转90度a[j].x=n-a[j].x+1;swap(a[j].x,a[j].y);}for(int j=1;j<=q;j++){b[j].x=n-b[j].x+1;swap(b[j].x,b[j].y);}swap(n,m);}     for(int i=1;i<=q;i++)printf("%lld\n",1ll*n*m-ans[i]);
}