lg2163

发表于 | 分类于 | 阅读数 次

链接:lg2163

Description

题解

f(a,b,c,d)=sum(c,d)-sum(a-1,d)-sum(c,b-1)+sum(a-1,b-1)
转化后即是一个二维偏序问题,树状数组、cdq分治都可以解决

cdq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define lowbit(x) x&(-x)
#define ll long long
using namespace std;
const int N=3e6+7;
struct node{
    int x,y,opt,idx;
    bool operator <(const node &b) const {
        return x==b.x?(y==b.y?opt:y<b.y):x<b.x;
    }
}a[N],tmp[N];
int n,m,ans_cnt,act;
int ans[N];
void cdq(int l,int r){
    if(l==r)return ;
    int mid=l+r>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int posa=l,posb=mid+1,pos=l,tot=0;
    while(posa<=mid&&posb<=r){
    	if(a[posa].y<=a[posb].y)tot+=a[posa].opt,tmp[pos++]=a[posa++];
    	else ans[a[posb].idx]+=tot,tmp[pos++]=a[posb++];
    }
    while(posa<=mid)tmp[pos++]=a[posa++];
    while(posb<=r)ans[a[posb].idx]+=tot,tmp[pos++]=a[posb++];
    rep(i,l,r)a[i]=tmp[i];
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n){
        int x,y;
        scanf("%d%d",&x,&y);
        a[++act]=node{x,y,1,0};
    }
    rep(i,1,m){
        int x,y,c,d;
        scanf("%d%d%d%d",&x,&y,&c,&d);
        a[++act]=node{c,d,0,++ans_cnt};
        a[++act]=node{c,y-1,0,++ans_cnt};
        a[++act]=node{x-1,d,0,++ans_cnt};
        a[++act]=node{x-1,y-1,0,++ans_cnt};
    }
    sort(a+1,a+act+1);
    cdq(1,act);
    for(int i=1;i+3<=ans_cnt;i+=4)printf("%d\n",ans[i]-ans[i+1]-ans[i+2]+ans[i+3]);
    return 0;
}

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define lowbit(x) x&(-x)
#define ll long long
using namespace std;
const int N=3e6+7;
struct node{
    int x,y,opt,id;
    bool operator <(const node &b)const {
        return x==b.x?(y==b.y?opt:y<b.y):x<b.x;
    }
}ques[N];
int y[N];
unordered_map<int,int>mp;
int n,m,ques_tot,ans_tot,nn,cnt,tr[N],ans[N];
inline void update(int x,int y){for(int i=x;i<=cnt;i+=lowbit(i))tr[i]+=y;}
inline int query(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=tr[i];return res;}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n){
        scanf("%d%d",&ques[i].x,&ques[i].y);
        ques[++ques_tot].opt=1;
        y[++nn]=ques[i].y;
    }
    rep(i,1,m){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        ques[++ques_tot]=node{c,d,0,++ans_tot};
        ques[++ques_tot]=node{c,b-1,0,++ans_tot};
        ques[++ques_tot]=node{a-1,d,0,++ans_tot};
        ques[++ques_tot]=node{a-1,b-1,0,++ans_tot};
        y[++nn]=d;y[++nn]=b-1;
    }
    sort(y+1,y+nn+1);
    rep(i,1,nn)if(y[i]!=y[i+1])mp[y[i]]=++cnt;
    sort(ques+1,ques+ques_tot+1);
    rep(i,1,ques_tot){
        int id=mp[ques[i].y];
        if(ques[i].opt==0)ans[ques[i].id]+=query(id);
        else update(id,1);
    }
    for(int i=1;i+3<=ans_tot;i+=4)printf("%d\n",ans[i]-ans[i+1]-ans[i+2]+ans[i+3]);
    return 0;
}