BZOJ 1935 园丁的烦恼

时间:2021-03-15 05:38:14

离线,BIT。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 500500
using namespace std;
int n,m,a,b,c,d,t[maxn*],ans[maxn*],hash[maxn*],cnt=,mov=;
struct query
{
int x,y,pos,val,opt;
}q[maxn*];
bool cmp(query a,query b)
{
if ((a.x==b.x) && (a.y==b.y)) return a.opt<b.opt;
if (a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int lowbit(int x)
{
return (x&(-x));
}
void add(int x,int val)
{
for (int i=x;i<=cnt;i+=lowbit(i))
t[i]+=val;
}
int ask(int x)
{
int ret=;
for (int i=x;i>=;i-=lowbit(i))
ret+=t[i];
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
{
scanf("%d%d",&a,&b);a++;b++;
q[++mov].x=a;q[i].y=b;q[i].pos=i;q[i].val=;q[i].opt=;
hash[++cnt]=b;
}
for (int i=;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);a++;b++;c++;d++;
hash[++cnt]=b;hash[++cnt]=d;hash[++cnt]=b-;hash[++cnt]=d-;
q[++mov].x=c;q[mov].y=d;q[mov].pos=i;q[mov].val=;q[mov].opt=;
q[++mov].x=a-;q[mov].y=d;q[mov].pos=i;q[mov].val=-;q[mov].opt=;
q[++mov].x=c;q[mov].y=b-;q[mov].pos=i;q[mov].val=-;q[mov].opt=;
q[++mov].x=a-;q[mov].y=b-;q[mov].pos=i;q[mov].val=;q[mov].opt=;
}
sort(hash+,hash+cnt+);cnt=unique(hash+,hash+cnt+)-hash-;
for (int i=;i<=mov;i++) q[i].y=lower_bound(hash+,hash+cnt+,q[i].y)-hash;
sort(q+,q+mov+,cmp);
for (int i=;i<=mov;i++)
{
if (!q[i].opt) add(q[i].y,q[i].val);
else ans[q[i].pos]+=q[i].val*ask(q[i].y);
}
for (int i=;i<=m;i++)
printf("%d\n",ans[i]);
return ;
}