poj2481 树状数组

简介:

排序后类似stars, 用树状数组。

注意两个数组都要memset和去重



#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct data{
    int s, e, i;
    friend bool operator <(data a, data b){
        if (a.e != b.e) return a.e > b.e;
        else return a.s<b.s;
    }
} a[100010];
int t[100010];
int lowbit(int x){
    return x & -x;
}
void build(int x){
    while (x <= 100001){
        t[x] ++;
        x += lowbit(x);
    }
}
int sum(int x){
    int res = 0;
    while (x){
        res += t[x];
        x -= lowbit(x);
    }
    return res;
}
int ans[100010];
int main(){
    int n;
    while (scanf("%d", &n) && n){
        memset(ans, 0, sizeof(ans));
        memset(t, 0, sizeof(t));
        for (int i = 0; i < n; i++) {scanf("%d%d", &a[i].s, &a[i].e);
        a[i].s++; a[i].e++; a[i].i = i;}
        sort(a, a + n);
        build(a[0].s);
        for (int i = 1; i < n; i++){
            if (a[i].s == a[i-1].s && a[i].e == a[i-1].e) {
                ans[a[i].i] = ans[a[i-1].i];
                build(a[i].s);
                continue;
            }
            ans[a[i].i] = sum(a[i].s);
            //cout<<a[i].i<<"    "<<a[i].s<<' '<<a[i].e<<' '<<ans[a[i].i]<<endl;
            build (a[i].s);
        }
        for (int i = 0; i < n-1; i++) printf("%d ", ans[i]); printf("%d", ans[n-1]);
        printf("\n");
    }
    return 0;
}
AI 代码解读


目录
打赏
0
0
0
0
1
分享
相关文章
Harry技术添加存储(minio、aliyun oss)、短信sms(aliyun、模拟)、邮件发送等功能
### SpringBoot3 + Vue3 前后端分离的Java快速开发框架更新 本次更新主要包含以下内容: 1. **端口修改**:为避免与Minio存储服务冲突,后端启动端口从9000改为9999。 2. **添加存储支持**:集成Minio和阿里云OSS对象存储服务,详细配置请参考相关文档。 3. **短信服务**:接入阿里云短信服务,并增加模拟发送功能,方便本地测试。 4. **邮件发送**:引入邮件发送功能,支持简单文本邮件和带附件邮件。 5. **完善个人中心**:优化个人中心页面,提升用户体验。
267 85
Harry技术添加存储(minio、aliyun oss)、短信sms(aliyun、模拟)、邮件发送等功能
安卓应用开发中的常见挑战及解决策略
【10月更文挑战第7天】在安卓应用开发的旅程中,开发者常面临各种挑战,从设备兼容性到性能优化,再到用户界面设计。本文将深入探讨这些常见问题,并提供实用的解决策略,帮助开发者提升应用质量和用户体验。我们将通过代码示例和实践建议,展示如何克服这些挑战,打造更流畅、更吸引人的安卓应用。
229 0
|
6月前
|
获取1688商品SKU信息API接口及实战应用
在电商蓬勃发展的今天,数据成为宝贵的财富。1688作为国内知名批发采购平台,提供商品SKU信息API接口,可获取库存、价格、规格等关键数据,助力电商运营、市场分析和价格监控。本文介绍如何注册1688开放平台账号、创建应用并获取AppKey/AppSecret,申请API权限,使用Python实现接口调用,处理响应数据,并注意请求频率限制和错误处理。通过该接口,可为电商运营和数据分析提供有力支持。
283 2
Java“NoClassDefFoundError”解决
“Java NoClassDefFoundError”是运行时错误,表示JVM找不到某个类的定义。通常由类路径设置不当、依赖缺失或版本冲突引起。解决方法包括检查类路径、确保所有依赖正确添加及版本兼容。
1316 3
WPF与Socket编程的完美邂逅:打造流畅网络通信体验——从客户端到服务器端,手把手教你实现基于Socket的实时数据交换
【8月更文挑战第31天】网络通信在现代应用中至关重要,Socket编程作为其实现基础,即便在主要用于桌面应用的Windows Presentation Foundation(WPF)中也发挥着重要作用。本文通过最佳实践,详细介绍如何在WPF应用中利用Socket实现网络通信,包括创建WPF项目、设计用户界面、实现Socket通信逻辑及搭建简单服务器端的全过程。具体步骤涵盖从UI设计到前后端交互的各个环节,并附有详尽示例代码,助力WPF开发者掌握这一关键技术,拓展应用程序的功能与实用性。
433 0
Obsidian 与 Typora 图片兼容保存路径一致设置
Obsidian 与 Typora 图片兼容保存路径一致设置
820 0
阿里云服务器备案服务码申请流程及限制说明
阿里云服务器备案需要备案服务码,阿小云以阿里云轻量应用服务器获取服务码教程为例
1971 0
阿里云服务器备案服务码申请流程及限制说明
Soloπ:支付宝开源的Android专项测试工具
无线化、非侵入、免 Root 的 Android 专项测试方案 Soloπ。
8617 0
云效(原RDC)如何耦合进我们的业务
最近在将公司的持续集成架构做一个系统的调整,调整过程中受到了RDC团队大量的帮助,所以利用国庆时间写了几篇RDC的分享,希望能让更多的人了解和用好RDC这个产品。 我会把我最近3个月的使用体会分成5个部分:使用RDC的动机、PHP项目集成、JS项目集成、JAVA项目集成、Docker类项目集成这5.
3282 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问