●BZOJ 4822 [Cqoi2017]老C的任务

时间:2023-03-08 21:33:59

题链:

https://www.luogu.org/problemnew/show/P3755 (洛谷上数据范围给全了的)

题解:

树状数组,离线询问
(本来想弄一个二维树状数组/二维RMQ,然后直接查询,但是空间不够用。)
做法如下,可以考虑把每个询问拆为四个, 即:四个二维前缀和。
然后把"拆过的询问操作"和"基站插入操作"排序,
排序规则:若 x 不同时,x 小的排在前面,
                否则 y 不同时,y 小的排在前面,
                否则把"基站插入操作"排在"拆过的询问操作"前面。
离散化 y 后
然后依次枚举排好序的操作,对一维树状数组进行修改和查询操作就好了。
这样可以保证对于每个前缀询问,其覆盖的区域里的基站信息都已经被统计。

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100500
#define ll long long
#define filein(x) freopen(#x".in","r",stdin)
#define fileout(x) freopen(#x".out","w",stdout)
using namespace std;
struct Question{
int cnt; ll sum[5];
ll Ans(){
return sum[4]-sum[3]-sum[2]+sum[1];
}
}Q[MAXN];
struct Command{
int x,y,t,b;
bool operator <(const Command & rtm) const{
if(x!=rtm.x) return x<rtm.x;
if(y!=rtm.y) return y<rtm.y;
if(t!=rtm.t) return t<rtm.t;
return 1;
}
}C[MAXN*5];
struct BIT{
ll A[MAXN*3],ret;int N;
void Reset(int n){
N=n;
memset(A,0,sizeof(A));
}
int lowbit(int x){
return x&-x;
}
void Modify(int p,int x){
while(p<=N) A[p]+=x,p+=lowbit(p);
}
ll Query(int p){
ret=0; while(p) ret+=A[p],p-=lowbit(p);
return ret;
}
}T;
int N,M,Cnt;
int main(){
static int tmp[MAXN*3],tnt;
scanf("%d%d",&N,&M);
for(int i=1,x,y,b;i<=N;i++){
scanf("%d%d%d",&x,&y,&b);
C[++Cnt]=(Command){x,y,0,b};
tmp[++tnt]=y;
}
for(int i=1,x1,y1,x2,y2;i<=M;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1--; y1--; Q[i].cnt=0;
C[++Cnt]=(Command){x1,y1,1,i};
C[++Cnt]=(Command){x1,y2,1,i};
C[++Cnt]=(Command){x2,y1,1,i};
C[++Cnt]=(Command){x2,y2,1,i};
tmp[++tnt]=y1; tmp[++tnt]=y2;
}
sort(C+1,C+Cnt+1);
sort(tmp+1,tmp+tnt+1);
tnt=unique(tmp+1,tmp+tnt+1)-tmp-1;
T.Reset(tnt);
for(int i=1,y;i<=Cnt;i++){
y=lower_bound(tmp+1,tmp+tnt+1,C[i].y)-tmp;
if(C[i].t) Q[C[i].b].sum[++Q[C[i].b].cnt]=T.Query(y);
else T.Modify(y,C[i].b);
}
for(int i=1;i<=M;i++)
printf("%lld\n",Q[i].Ans());
return 0;
}