文档章节

【codevs 2492】上帝造题的七分钟2

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 257
阅读 11
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

QAQ这题不是线段树?
参见切水果

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN = 100000 + 5;
ll num[MAXN];
int zero[MAXN];
int fa[MAXN];
int n;
void init()
{
    for(int i = 0;i < MAXN;i ++)
        fa[i] = i;
    return;
}
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool same(int x,int y)
{
    return find(x) == find(y);
}
void merge(int x,int y)
{
    x = find(x);
    y = find(y);
    fa[x] = y;
    return;
}
void change(int l,int r)
{
    for(int i = l;i <= r;i ++)
    {
        i = find(i);
        if(i > r)
            break;
        num[i] = sqrt(num[i]);
        if(num[i] == 1)
            merge(i,i + 1);
    }
    return;
}
ll ask(int l,int r)
{
    ll ans = 0;
    for(int i = l;i <= r;i ++)
    {
        int x = find(i);
        ans += min(x,r + 1) - i;
        i = x;
        if(i <= r)
            ans += num[i];
    }
    ans -= zero[r] - zero[l - 1];
    return ans;
}
int Q;
int q,l,r;
int main()
{
    scanf("%d",&n);
    init();
    for(int i = 1;i <= n;i ++)
    {
        scanf("%lld",&num[i]);
        if(!num[i])
            zero[i] ++;
        zero[i] += zero[i - 1];
    }
    scanf("%d",&Q);
    while(Q --)
    {
        scanf("%d %d %d",&q,&l,&r);
        if(l > r)
            swap(l,r);
        switch(q)
        {
            case 0:
                change(l,r);
                break;
            case 1:
                printf("%lld\n",ask(l,r));
                break;
        }
    }
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
这不是电影!BBC记者挑战中国天网工网系统,“潜逃”7分钟就被抓获!

     潜逃7分钟,就通过互联监控摄像头被抓获!这不是电影《速度与激情7》中的“天眼 ” 系统,而是我国的“天网工程 ”。   据英国广播公司(BBC)当地时间12月10日报道,BBC记者约翰...

人工智能机器人联盟
2017/12/14
0
0
codevs 5971 打击犯罪

题目描述 Description 某个地区有n(n<=1000)个犯罪团伙,当地警方按照他们的危险程度由高到低给他们编号为1-n,他们有些团伙之间有直接联系,但是任意两个团伙都可以通过直接或间接的方式联系...

zoom1109
06/19
0
0
疾病的小常识

这文章不发布,就只能草稿箱看,我有强迫症。发布一下,写给自己的。 咽喉炎 咽喉炎.没有特效的办法. 关键是保养.不大声讲话和歌唱!积极预防感冒.应该禁烟 ,酒,不吃辛辣食物.急性疼痛期间口服...

东风冷雪
2018/01/01
0
0
【活动发布】华为云点大咖神秘空降,解读企业IT转型新动力

创新业务or传统业务,企业上云是否摇摆不定?公有云、专属云and混合云,哪个才是企业最终归属?三分技术,七分管理,如何实现点到点、端到端的安全防护? 五大行业,四种场景,全方位多维度的...

云点学堂
2016/01/04
89
0
程序员的十层楼2

3、海森堡 (1901~1976) 海森堡这个名字相信没有几个人不知道的,大部分人在学习物理时都学过他的“测不准 关系”,也就是因为这个“测不准关系”,海森堡爬到了第十层楼。 如果你看过《时间简...

传奇再现
2013/02/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx反向代理+负载均衡+服务器宕机解决办法

反向代理 作用:保证系统安全,不暴露服务器IP,利用nginx服务器,利用内网ip进行访问,避免出现攻击服务器的情况 启动本地tomact,127.0.0.1:8080可以访问到tomcat管理页面 效果:通过 bbs....

Jack088
4分钟前
1
0
返回IEnumerable 与IQueryable相比 [关闭]

返回IQueryable<T>与IEnumerable<T>之间有什么区别? IQueryable<Customer> custs = from c in db.Customerswhere c.City == "<City>"select c;IEnumerable<Customer> custs = from c i......

技术盛宴
11分钟前
2
0
开放下载 | 《Knative 云原生应用开发指南》开启云原生时代 Serverless 之门

点击下载《Knative 云原生应用开发指南》 自 2018 年 Knative 项目开源后,就得到了广大开发者的密切关注。Knative 在 Kubernetes 之上提供了一套完整的应用 Serverless 编排服务,让应用开发...

阿里巴巴云原生
16分钟前
2
0
解密淘宝推荐实战,打造 “比你还懂你” 的个性化APP

手淘推荐简介 手淘推荐的快速发展源于2014年阿里“All in 无线”战略的提出。在无线时代,手机屏幕变小,用户无法同时浏览多个视窗,交互变得困难,在这样的情况下,手淘借助个性化推荐来提升...

阿里云官方博客
18分钟前
2
0
内核程序中进程的pid,handle,eprocess之间相互转换的方法

在内核程序开发中,我们常常需要取得某进程的pid或句柄,或者需要检索进程的eprocess结构,很多API函数需要的参数也不同,所以掌握pid<->handle<->eprocess相互转换的方法会大大提高我们的开...

simpower
20分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部