codeforces 1191 F 离散化+树状数组

98 阅读 0 评论 65 点赞

我是靠谱客的博主阔达火龙果，这篇文章主要介绍codeforces 1191 F 离散化+树状数组，现在分享给大家，希望可以做个参考。

题意：定义无序集合s（l,r,a）为x∈[l,r]，y∈(a,+∞)的所有点，给你n个点，问你最多有多少个这样的集合

题解：将坐标离散化为a[i].x和a[i].x-1，从上到下从左到右，加上每个点的贡献值即可。注意，树状数组只记录一次，即最大是1即可，因为只需要看当前y坐标的所有点就行，与上一层和下一层的无关。

复制代码

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10, INF = 0x3f3f3f3f;
int bit[maxn],b[maxn],coun=0,vis[maxn];
struct node {
    int x,y;
}a[maxn];
bool cmp(node a,node b){
    if(a.y==b.y)return a.x<b.x;
    else return a.y>b.y;
}
int mp(int x){
    return  lower_bound(b+1,b+1+coun,x)-b-1;
}
int lowbit(int x)
{
    return x&(-x);
}
void update(int i)
{ 
    i=mp(i);
    if(!vis[i]){
        vis[i]=1;
       
        while(i<=coun)
        {
            bit[i]++;
            i+=lowbit(i);
        }
    }
}
int query(int i)
{
    int s=0;
    while(i>0)
    {
        s+=bit[i];
        i-=lowbit(i);
    }
    return s;
}
int query(int l,int r){
    return query(mp(r))-query(mp(l-1));
}

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        b[++coun]=a[i].x;b[++coun]=a[i].x-1;
    }
    b[++coun]=0;b[++coun]=INF;
    sort(a+1,a+n+1,cmp);sort(b+1,b+coun+1);
    ll ans=0;
    for(int i=1;i<=n;i++){
        int j=i;
        while(j<n&&a[j+1].y==a[i].y)j++;
        for(int k=i;k<=j;k++){
            int l=query(1,a[k].x-1);
            int r=query(a[k].x+1,k==j?INF:a[k+1].x-1);
            ans+=1ll*(l+1)*(r+1);
            //cout<<l+1<<" "<<r+1<<endl;
            update(a[k].x);
        }
        i=j;
    }
    printf("%lldn", ans);
   //while(1)getchar();
}

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10, INF = 0x3f3f3f3f;
int bit[maxn],b[maxn],coun=0,vis[maxn];
struct node {
    int x,y;
}a[maxn];
bool cmp(node a,node b){
    if(a.y==b.y)return a.x<b.x;
    else return a.y>b.y;
}
int mp(int x){
    return  lower_bound(b+1,b+1+coun,x)-b-1;
}
int lowbit(int x)
{
    return x&(-x);
}
void update(int i)
{ 
    i=mp(i);
    if(!vis[i]){
        vis[i]=1;
       
        while(i<=coun)
        {
            bit[i]++;
            i+=lowbit(i);
        }
    }
}
int query(int i)
{
    int s=0;
    while(i>0)
    {
        s+=bit[i];
        i-=lowbit(i);
    }
    return s;
}
int query(int l,int r){
    return query(mp(r))-query(mp(l-1));
}

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        b[++coun]=a[i].x;b[++coun]=a[i].x-1;
    }
    b[++coun]=0;b[++coun]=INF;
    sort(a+1,a+n+1,cmp);sort(b+1,b+coun+1);
    ll ans=0;
    for(int i=1;i<=n;i++){
        int j=i;
        while(j<n&&a[j+1].y==a[i].y)j++;
        for(int k=i;k<=j;k++){
            int l=query(1,a[k].x-1);
            int r=query(a[k].x+1,k==j?INF:a[k+1].x-1);
            ans+=1ll*(l+1)*(r+1);
            //cout<<l+1<<" "<<r+1<<endl;
            update(a[k].x);
        }
        i=j;
    }
    printf("%lldn", ans);
   //while(1)getchar();
}