HDU6315 Naive Operations(线段树 复杂度分析)

题意

题目链接

Sol

这题关键是注意到题目中的\(b\)是个排列

那么最终的答案最多是\(nlogn\)(调和级数)

设\(d_i\)表示\(i\)号节点还需要加\(d_i\)次才能产生\(1\)的贡献

用线段树维护每个节点里\(d_i\)的最小值,每次当\(d_i - 1= 0\)的时候往下递归即可

时间复杂度:\(O(nlog^2 n)\)

多组数据记得清空lazy标记啊qwq。。。。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, b[MAXN];
#define ls k << 1
#define rs k << 1 | 1
struct Node {
    int l, r, mn, sum, f;
}T[MAXN];
void update(int k) {
    T[k].mn = min(T[ls].mn, T[rs].mn);
    T[k].sum = T[ls].sum + T[rs].sum;
}
void add(int k, int val) {
    T[k].mn -= val; T[k].f += val;
}
void pushdown(int k) {
    if(!T[k].f) return ;
    add(ls, T[k].f); add(rs, T[k].f);
    T[k].f = 0;
}
void Build(int k, int ll, int rr) {
    T[k].l = ll; T[k].r = rr; T[k].sum = 0; T[k].f = 0;
    if(ll == rr) {T[k].mn = b[ll]; return ;}
    int mid = ll + rr >> 1;
    Build(ls, ll, mid); Build(rs, mid + 1, rr);
    update(k); 
}
void dec(int k) {
    if(T[k].mn == 0) {
        if(T[k].l == T[k].r) T[k].sum++, T[k].mn = b[T[k].l];
        else pushdown(k), dec(ls), dec(rs), update(k);
    }
}
void IntervalAdd(int k, int ll, int rr) {
    if(ll <= T[k].l && T[k].r <= rr) {
        add(k, 1);
        if(T[k].mn == 0) dec(k);
        return ;
    }
    pushdown(k);
    int mid = T[k].l + T[k].r >> 1;
    if(ll <= mid) IntervalAdd(ls, ll, rr);
    if(rr  > mid) IntervalAdd(rs, ll, rr);
    update(k);
}
int Query(int k, int ll, int rr) {
    if(ll <= T[k].l && T[k].r <= rr) return T[k].sum;
    pushdown(k);
    int mid = T[k].l + T[k].r >> 1;
    if(rr <= mid) return Query(ls, ll, rr);
    else if(ll > mid) return Query(rs, ll, rr);
    else return Query(ls, ll, rr) + Query(rs, ll, rr);
}
main() {
    while(scanf("%d %d", &N, &M) == 2) {
        for(int i = 1; i <= N; i++) b[i] = read();
        Build(1, 1, N);
        while(M--) {
            char s[6]; int l, r;
            scanf("%s", s + 1); l = read(), r = read(); 
            if(s[1] == 'a') IntervalAdd(1, l, r);
            else printf("%d\n", Query(1, l, r));            
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

Java每日一练(2017/8/2)

本期题目: (单选题)1、在 java 中,一个类可同时定义为许多同名的方法,这些方法的形式参数个数,类型或顺序各不相同,传回的值可能个不相同,这种面向对象的...

2927
来自专栏YG小书屋

MapReduce:N keys,N files

MapReduce中,不管是map阶段还是reduce阶段,二者的输入和输出都是key,value类型的值。现在有个需求是根据map阶段返回值key的个数,生成...

854
来自专栏java思维导图

Java 单例以及单例所引发的思考

1 前言 前几天无意中看到一篇文章,讲到了老生常谈的单例,抱着复习一下的心态点了进去,还是那些熟悉的内容,可是却发现自己思考的角度变了,以前更多的是去记忆,只停...

2947
来自专栏用户2442861的专栏

[疯狂Java]JDBC:PreparedStatement预编译执行SQL语句

    1) SQL语句和编程语言一样,仅仅就会普通的文本字符串,首先数据库引擎无法识别这种文本字符串,而底层的CPU更不理解这些文本字符串(只懂二进制机器指...

3342
来自专栏数据结构与算法

SPOJ1043 GSS1(线段树)

注意查询的时候不能按照以前的方式写,因为不知道变量的下界,最稳妥的办法就是判三种情况

1051
来自专栏Golang语言社区

go语言的sql包原理与用法分析

本文实例讲述了go语言的sql包原理与用法。分享给大家供大家参考,具体如下: go的sql包是在pkg/database中,里面的两个包sql和sql/driv...

4566
来自专栏耕耘实录

Linux三大剑客之awk

版权声明:本文为耕耘实录原创文章,各大自媒体平台同步更新。欢迎转载,转载请注明出处,谢谢

1684
来自专栏PHP在线

mysql学习笔记

InnoDB引擎与MyISAM引擎 mysql是关系型数据库。其中的存储引擎可以show engines来查看。我的版本是5.6.26的,查看版本用selec...

2905
来自专栏偏前端工程师的驿站

MyBatis魔法堂:即学即用篇

一、前言                                          本篇内容以理解MyBatis的基本用法和快速在项目中实践为目的,...

2256
来自专栏数据结构与算法

BZOJ3261: 最大异或和(可持久化trie树)

2223

扫码关注云+社区

领取腾讯云代金券