侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【树状数组, 线段树】数星星

GabrielxD
2023-03-07 / 0 评论 / 0 点赞 / 130 阅读 / 1,316 字
温馨提示:
本文最后更新于 2023-03-07,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1265. 数星星 - AcWing题库


天空中有一些星星,这些星星都在不同的位置,每个星星有个坐标。

如果一个星星的左下方(包含正左和正下)有 kk 颗星星,就说这颗星星是 kk 级的。

1.png

例如,上图中星星 5533 级的( 1,2,41,2,4 在它左下),星星 2,42,411 级的。

例图中有 1100 级, 2211 级, 1122 级, 1133 级的星星。

给定星星的位置,输出各级星星的数目。

换句话说,给定 NN 个点,定义每个点的等级是在该点左下方(含正左、正下)的点的数目,试统计每个等级有多少个点。

输入格式

第一行一个整数 NN ,表示星星的数目;

接下来 NN 行给出每颗星星的坐标,坐标用两个整数 x,yx,y 表示;

不会有星星重叠。星星按 yy 坐标增序给出, yy 坐标相同的按 xx 坐标增序给出。

输出格式

NN 行,每行一个整数,分别是 00 级, 11 级, 22 级,……, N1N-1 级的星星的数目。

数据范围

1N150001 \le N \le 15000 ,
0x,y320000 \le x,y \le 32000

输入样例:

5
1 1
5 1
7 1
3 3
5 5

输出样例:

1
2
1
1
0

解题

方法一:树状数组

思路

题目说星星按 yy 坐标增序给出, yy 坐标相同的按 xx 坐标增序给出,那么按顺序输入每个点时:

  • 在其左下角的点一定会在其之前被给出
  • 但是在其之前被给出的点不一定全是在其左下角的点

image-20230307143113054

如图所示,对于当前输入到的绿点,所有在其左下角的点(绿色区域)在之前就被输入了,而在其之前被输入但又不在其左下角的点都是那些 xx 坐标大于当前点 xx 坐标的点。

那么其实我们只需要维护横坐标为 0N0 \dots N 的点的数量,在每次输入一个点 (x,y)(x, y) 时先查询 0x0 \dots x 横坐标上点的数量的总和就是当前星星的等级,然后再把横坐标为 xx 的点自增 11

本题数据是时间限制是 0.2s0.2s ,所以普通的前缀和时间复杂度 O(NM)O(NM) 肯定是过不了的,但是选择树状数组或是线段树,时间复杂度可以降到 O(NlogM)O(N\log{M}) ,这题就能过了。

注意:

  • 本题中横坐标有可能为 00 ,而一般我们维护的线段树或树状数组都是从 11 开始的,所以输入坐标后最好把横坐标加 11 再进行操作。
  • 本题要求的是每一级星星的数量,而不是每一个星星是几级,这点要注意。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 32010;
    static int[] tr = new int[N];
    
    static void add(int i, int x) {
        for (; i <= N; i += i & -i) tr[i] += x;
    }
    
    static int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i) sum += tr[i];
        return sum;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] cnts = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            int x = (int) in.nval;
            in.nextToken();
            int y = (int) in.nval;
            ++cnts[query(x + 1)];
            add(x + 1, 1);
        }
        for (int i = 0; i < n; ++i) System.out.println(cnts[i]);
    }
}

方法二:线段树

思路

思路与前面一样,只不过单点修改和区间查询的操作改为线段树实现。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int N = 32010;
    static class Node {
        int l, r, sum;
        
        public Node(int l, int r, int sum) {
            this.l = l;
            this.r = r;
            this.sum = sum;
        }
    }
    static Node[] tr = new Node[N * 4];
    
    static void pushup(int u) {
        tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    }
    
    static void build(int u, int l, int r) {
        if (l == r) tr[u] = new Node(l, r, 0);
        else {
            tr[u] = new Node(l, r, 0);
            int m = l + r >> 1;
            build(u << 1, l, m);
            build(u << 1 | 1, m + 1, r);
            pushup(u);
        }
    }
    
    static int query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
        int m = tr[u].l + tr[u].r >> 1;
        int sum = 0;
        if (l <= m) sum += query(u << 1, l, r);
        if (r >= m + 1) sum += query(u << 1 | 1, l, r);
        return sum;
    }
    
    static void add(int u, int i) {
        if (tr[u].l == tr[u].r) ++tr[u].sum;
        else {
            int m = tr[u].l + tr[u].r >> 1;
            if (i <= m) add(u << 1, i);
            else add(u << 1 | 1, i);
            pushup(u);
        }
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] cnts = new int[n];
        build(1, 1, N);
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            int x = (int) in.nval + 1;
            in.nextToken();
            int y = (int) in.nval;
            ++cnts[query(1, 1, x)];
            add(1, x);
        }
        for (int x : cnts) System.out.println(x);
    }
}
0
博主关闭了所有页面的评论