文档章节

CF #546 D.E

o
 osc_y8yehimr
发布于 2019/03/20 09:46
字数 301
阅读 6
收藏 0

精选30+云产品,助力企业轻松上云!>>>

D

coun[i]表示[i]这个数右边有多少个数j能和他组成题中所给的二元组(i,j)

如果一个数的coun[i]=n-i-ans 那么说明他可以与最后一个交换 同时不计算贡献 因为它是向右走的 对左边没有贡献

#include<bits/stdc++.h>
using namespace std;
int num[300005];
vector<int> f[300005];
int coun[300005];
int main() {
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
                scanf("%d", &num[i]);
        }
        int a, b;
        for (int i = 1; i <= m; i++) {
                scanf("%d  %d", &a, &b);
                f[b].push_back(a);
        }
        int ans = 0;
        for (int i = 0; i < f[num[n]].size(); i++) {
                int now = f[num[n]][i];
                coun[now]++;
        }
        for (int i = n - 1; i >= 1; i--) {
                int now = num[i];
                if (coun[now] == n - i - ans) {
                        ans++;
                } else {
                        for (int v : f[now]) {
                                coun[v]++;
                        }
                }
        }
        printf("%d\n", ans);
        return 0;
}

E

令k[i]的前缀和为c[i] 则题目中的要求Ai+1>=Ai+ki两边同时减去c[i]可以变成Ai+1-c[i]>=Ai-c[i-1] 再令b[i]=Ai-c[i-1] 变成b[i+1]>=b[i]

询问中的求和就直接求b[i]的和再补上减去的c[i]即可 单点修改操作则是二分求第一个大于等于b[i]+x的位置再区间修改即可

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
《转》ceilometer的数据采集机制入门

问题导读 1.ceilometer负责什么事情? 2.ceilometer 有哪些概念? 3.ceilometer 如何采集hardware? 附上openstack 官网API http://docs.openstack.org/developer/python-ceilometerclient/ ......

傻呆
2016/06/22
78
0
Linux_DHCP服务配置部署

一、什么是DHCP: (DynamicHost Configuration Protocol) 动态主机配置协议, 是一个局域网的网络协议,使用UDP协议工作,DHCP有3个端口, DHCPServer : 67 DHCP Client : 68 DHCPv6 Client:5...

osc_da4rblss
2019/09/17
2
0
D.E.Shaw——高频统计套利交易获利41亿美元

黑科技,还是要提 D.E.Shaw Research 这个奇异的存在。 要讲这个黑科技,我们可能要扯远一点,先讲讲 D.E. Shaw 这个人是怎么学术赚钱通吃,成为彻底的人生大赢家的。 D.E.Shaw 是个学霸,是...

osc_zsm40sb6
2018/09/12
2
0
36kr这个是没有注意,还是要让我们看到的?

#0 [8 : Undefined index: HTTP_USER_AGENT] tracking call at /var/www/krplus/corelib/common.func.php (546) #1 isAndroidOrIOsMobile call at /var/www/krplus/mars/vchost/index.php (4......

欣儿
2013/06/24
397
2
golang的 Web 开发,提示找不到模板文件

编译后的可执行文件,与模板文件在同一目录,报错:no files 代码: 错误信息:

反AI首席倡议官
2016/07/18
414
0

没有更多内容

加载失败,请刷新页面

加载更多

浅谈对python pandas中 inplace 参数的理解

这篇文章主要介绍了对python pandas中 inplace 参数的理解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 pandas 中 inplace 参数在很多函数中都会有,它的作用是:是否...

Linux就该这么学
34分钟前
20
0
C++ 从基本数据类型说起

前言 int 在32位和64位操作系统,都是四个字节长度。为了能编写一个在32位和64位操作系统都能稳定运行的程序,建议采用std::int32_t 或者std::int64_t指定数据类型。*与long随操作系统子长变...

osc_sxdofc9c
34分钟前
9
0
游戏音乐的作用以及起源

游戏音乐是由特殊的音乐、语言符号、美学符号组成,在电子游戏的发展下,游戏音乐越来越成熟,游戏音乐与美术相融合,能够带给玩家视觉与声音的感官冲击,形成游戏音乐所具有的独特的审美效果...

奇亿音乐
35分钟前
10
0
2020,最新Model的设计-APP重构之路

很多的app使用MVC设计模式来将“用户交互”与“数据和逻辑”分开,而model其中一个重要作用就是持久化。下文中设计的Model可能不是一个完美的,扩展性强的model范例,但在我需要重构的app中,...

osc_mfzkzkxi
35分钟前
4
0
面对职业瓶颈,iOS 开发人员应该如何突破?

我们经常看到 iOS 开发人员(各种能力水平都有)的一些问题,咨询有关专业和财务发展方面的建议。 这些问题有一个共同点:前面都会说“我现在遇到了职业困境”,然后会问一些诸如“我是否应该...

osc_gfpedeca
36分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部