数列所有公式大全_finish验证失败是什么意思

数列所有公式大全_finish验证失败是什么意思请写一个程序,要求维护一个数列,支持以下 6 种操作:(请注意,格式栏 中的下划线 _ 表示实际输入文件中的空格)输入格式第 1 行包含两个数 N 和 M,N 表示初始时数列中数的个数,M 表示要进行的操作数目。第 2 行包含 N 个数字,描述初始时的数列。以下 M 行,每行一条命令,格式参见问题描述中的表格。输出格式对于输入数据中的 GET-SUM 和 MAX-SUM 操作,向输出文件依次打印结果,每个答案(数字)占一行。数据范围与约定你可以认为在任何时刻,数列中至少有 1 个数。输入

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

请写一个程序,要求维护一个数列,支持以下 6 种操作:(请注意,格式栏 中的下划线 _ 表示实际输入文件中的空格)

在这里插入图片描述

输入格式
第 1 行包含两个数 N 和 M,N 表示初始时数列中数的个数,M 表示要进行的操作数目。

第 2 行包含 N 个数字,描述初始时的数列。

以下 M 行,每行一条命令,格式参见问题描述中的表格。

输出格式
对于输入数据中的 GET-SUM 和 MAX-SUM 操作,向输出文件依次打印结果,每个答案(数字)占一行。

数据范围与约定
你可以认为在任何时刻,数列中至少有 1 个数。

输入数据一定是正确的,即指定位置的数在数列中一定存在。

50% 的数据中,任何时刻数列中最多含有 30000 个数;100% 的数据中,任何时刻数列中最多含有 500000 个数。

100% 的数据中,任何时刻数列中任何一个数字均在 [−1000,1000] 内。

100% 的数据中,M≤20000,插入的数字总数不超过 4000000 个,输入文件大小不超过 20 MBytes。

输入样例:
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
输出样例:
-1
10
1
10


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 3000010, INF = 1e9;
int nodes[N], tt;
struct Node{ 
   
    int s[2], v, p;
    int same, rev;
    int siz, ms, ls, rs, sum;
    void init(int _p, int _v)
    { 
   
        v = _v, p = _p; s[0] = s[1] = 0;
        same = rev = 0;
        siz = 1; sum = ms = v; ls = rs = max(v, 0);
    }
}t[N];
int root, idx;
int w[N];
void pushup(int u)
{ 
   
    auto &fa = t[u], &l = t[t[u].s[0]], &r = t[t[u].s[1]];
    fa.siz = l.siz + r.siz + 1;
    fa.ms = max(max(l.ms, r.ms), l.rs + r.ls + fa.v);
    fa.ls = max(l.ls, l.sum + r.ls + fa.v);
    fa.rs = max(r.rs, r.sum + l.rs + fa.v);
    fa.sum = l.sum + r.sum + fa.v;
}
void pushdown(int x)
{ 
   
    auto &u = t[x], &l = t[t[x].s[0]], &r = t[t[x].s[1]];
    if(u.same)
    { 
   
        u.same = u.rev = 0;
        if(u.s[0]) l.same = 1, l.v = u.v, l.sum = l.siz * l.v;
        if(u.s[1]) r.same = 1, r.v = u.v, r.sum = r.siz * r.v;
        if(u.v > 0)
        { 
   
            if(u.s[0]) l.ls = l.rs = l.ms = l.sum;
            if(u.s[1]) r.ls = r.rs = r.ms = r.sum;
        }
        else 
        { 
   
            if(u.s[0]) l.ls = l.rs = 0, l.ms = l.v;
            if(u.s[1]) r.ls = r.rs = 0, r.ms = r.v;
        }
    }
    else if(u.rev)
    { 
   
        u.rev = 0; l.rev ^= 1, r.rev ^= 1;
        swap(l.s[0], l.s[1]); swap(l.ls, l.rs);
        swap(r.s[0], r.s[1]); swap(r.ls, r.rs);
    }
}
void rotate(int x)
{ 
   
    int y = t[x].p, z = t[y].p;
    int k = t[y].s[1] == x;
    t[z].s[t[z].s[1] == y] = x; t[x].p = z;
    t[y].s[k] = t[x].s[k ^ 1], t[t[x].s[k ^ 1]].p = y;
    t[x].s[k ^ 1] = y; t[y].p = x;
    pushup(y); pushup(x);
}
void splay(int x, int p)
{ 
   
    while(t[x].p != p)
    { 
   
        int y = t[x].p, z = t[y].p;
        if(z != p)
            if(t[y].s[1] == x ^ t[z].s[1] == y) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(!p) root = x;
}
int build(int l, int r,int p)
{ 
   
    int mid = l + r >> 1;
    int u = nodes[tt --];
    t[u].init(p, w[mid]);
    if(mid > l) t[u].s[0] = build(l, mid - 1, u); 
    if(mid < r) t[u].s[1] = build(mid + 1, r, u);
    pushup(u);
    return u;
}
int get_k(int siz)
{ 
   
    int u = root;
    while(u)
    { 
   
        pushdown(u);
        if(t[t[u].s[0]].siz >= siz) u = t[u].s[0];
        else if(t[t[u].s[0]].siz + 1 == siz) return u;
        else siz -= t[t[u].s[0]].siz + 1, u = t[u].s[1];
    }
    return -1;
}
void dfs(int u)
{ 
   
    if(t[u].s[0]) dfs(t[u].s[0]);
    if(t[u].s[1]) dfs(t[u].s[1]);
    nodes[++ tt] = u;
}
int main()
{ 
   
    for(int i = 1; i < N; ++ i) nodes[++ tt] = i;
    int n, m; scanf("%d%d", &n, &m);

    w[0] = -INF, w[n + 1] = -INF;
    t[0].ms = -INF;
    for(int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
    root = build(0, n + 1, 0);
    char op[10];
    while(m --)
    { 
   
        scanf("%s", op);
        if(!strcmp(op, "INSERT"))
        { 
   
            int pos, len;
            scanf("%d%d", &pos, &len);
            for(int i = 0; i < len; ++ i) scanf("%d", &w[i]);
            int l = pos + 1, r = pos + 2;
            l = get_k(l); r = get_k(r);
            splay(l, 0); splay(r, l);
            t[r].s[0] = build(0, len - 1, r);
            pushup(r); pushup(l);
        }
        else if(!strcmp(op, "DELETE"))
        { 
   
            int pos, len;scanf("%d%d", &pos, &len);
            int l = get_k(pos), r = get_k(pos + len + 1);
            splay(l, 0); splay(r, l);
            dfs(t[r].s[0]);
            t[r].s[0] = 0;
            pushup(r); pushup(l);
            
        }
        else if(!strcmp(op, "MAKE-SAME"))
        { 
   
            int pos, len, c; scanf("%d%d%d", &pos, &len, &c);
            int l =get_k(pos), r = get_k(pos + len + 1);
            splay(l, 0); splay(r, l);
            auto &ch = t[t[r].s[0]];
            ch.same = 1; ch.v = c; ch.sum = c * ch.siz;
            if(c > 0) ch.ms = ch.ls = ch.rs = ch.sum;
            else ch.ms = ch.v, ch.ls = ch.rs = 0;
            pushup(r); pushup(l);
        }
        else if(!strcmp(op, "REVERSE"))
        { 
   
            int pos, len; scanf("%d%d", &pos, &len);
            int l =get_k(pos), r = get_k(pos + len + 1);
            splay(l, 0); splay(r, l);
            auto &ch = t[t[r].s[0]];
            ch.rev ^= 1;
            swap(ch.s[0], ch.s[1]);
            swap(ch.ls, ch.rs);
            pushup(r); pushup(l);
        }
        else if(!strcmp(op, "GET-SUM"))
        { 
   
            int pos, len; scanf("%d%d", &pos, &len);
            int l =get_k(pos), r = get_k(pos + len + 1);
            splay(l, 0); splay(r, l);
            printf("%d\n", t[t[r].s[0]].sum);
        }
        else printf("%d\n", t[root].ms);
        
    }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168589.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • SCI 投稿Cover letter模板大全「建议收藏」

    SCI 投稿Cover letter模板大全「建议收藏」“`一、第一次投稿Coverletter:主要任务是介绍文章主要创新以及声明没有一稿多投DearEditors,Wewouldliketosubmittheenclosedmanuscriptentitled“PaperTi…

  • apache 80端口被占用_tomcat8005端口被占用

    apache 80端口被占用_tomcat8005端口被占用参考:https://jingyan.baidu.com/article/1876c8527b1fc3890b13763b.html1.win+R,输入cmd,打开命令行窗口2.命令行输入netstat-ano3.找到80端口及对应进程 4.在任务管理器中的进程处查看与上述80端口对应的PID相同的进程,并关闭。如果没有PID,选择“查看”–&gt;"选择列"–…

    2022年10月30日
  • linux下安装tomcat的默认目录[通俗易懂]

    linux下安装tomcat的默认目录[通俗易懂]以Linux分支UbuntuServer为例。一、相关目录及作用说明  /etc/tomcat6-全局配置  /usr/share/tomcat6/-程序主目录  /usr/share/tomcat6/conf/Catalina/localhost/-本机部署的Catalina配置  /var/lib/tomcat6/-工作主目录  /var/l

  • linux fork函数浅析

    linux fork函数浅析

  • ps怎么导出图片形式_ps导出图片变色

    ps怎么导出图片形式_ps导出图片变色在PS中做好图之后,我们会有下面几种导出图片的需求,下面分别介绍一下将每个图层分别存储为一个文件文件——脚本——将图层导出到文件其中可以仅仅导出可见图层,这样,我们就能够通过控制图层窗口中个图层

  • mimikatz行为免杀_易语言远程源码

    mimikatz行为免杀_易语言远程源码目录介绍环境准备处理报错生成32位生成64位下载360、360杀毒直接查杀关键字替换-失败去除注释,修改版本信息删除注释信息替换图标修改版本信息重新编译文件过杀软360家族腾讯电脑管家火绒在线查杀参考学习一下月师傅的文章介绍Mimikatz是一款能够从Windows认证(LSASS)的进程中获取内存,并且获取明文密码和NTLM哈希值的工具,攻击者可以借此漫游内网。也可以通过明文密码或者传递hash值来提权。因为这款工具特别出名所以被查杀的机率很大,我们可以通过github上的开源代码对其进行源码免

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号