hdu4288 Coder(段树+分离)

hdu4288 Coder(段树+分离)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

主题链接:

题意:

题目中给了三个操作
1:add x 就是把x插进去 
2:delete x 就是把x删除
3:sum 就是求下标%5=3的元素的和。
另一个条件是插入和删除最后都要保证数列有序。

。。

首先告诉一种暴力的写法。

。由于时间很充足,须要对stl里面的函数有所了解。

就是直接申明一个vector的容器。然后直接用vector里面的操作比方 insert,erase等等操作。

。只是这个效率非常低。。

最后跑出来6000多ms。

。(强哥的代码)

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

char s[5];
int n;

vector<int>a;

int main()
{
    int len,val;
    vector<int>::iterator iter;
    while(cin>>n)
    {
        len=0;
        a.clear();
        while(n--)
        {
            scanf("%s",s);
            if(s[0]=='s')
            {
                long long ans = 0;
                for(int i=2; i < len ; i+=5)
                    ans += a[i];
                cout<<ans<<endl;
            }
            else if(s[0]=='a')
            {
                len++;
                scanf("%d",&val);
                iter=lower_bound(a.begin(),a.end(),val);
                a.insert(iter,val);
            }
            else
            {
                 len--;
                 scanf("%d",&val);
                 iter= lower_bound(a.begin(),a.end(),val);
                 a.erase(iter); // basic coding
            }
        }
    }
    return 0;
}

另外一种方法是线段树做法,这个要维护5颗线段树。结构体里面保存每一个节点的个数。首先由于线段树不支持插入,删除,要维护一个个数cnt,当插入一个数的时候,你看原来%3的数,如今取余肯定等于2,那么怎么办呢??那么这个cnt就起到了奇妙的作用。每当插入删除的时候就把对应的节点数变化,来维护那5棵线段树。

最后由于没有告诉数据范围,所以要採取离散化,然后离线处理,最后得出全部要操作的总个数,然后依此建树。第一次用离散化,认为好高大上。。。

代码:(參考自cxlove)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=100000+10;
int n,a[maxn],b[maxn];
char op[maxn][5];

struct Tree
{
    int cnt;
    ll sum[5];
}tree[maxn<<2];

void buildtree(int l,int r,int dex)
{
    tree[dex].cnt=0;
    memset(tree[dex].sum,0,sizeof(tree[dex].sum));
    if(l==r)  return;
    int mid=(l+r)>>1;
    buildtree(l,mid,dex<<1);
    buildtree(mid+1,r,dex<<1|1);
}

void push_up(int dex)
{
    for(int i=0;i<5;i++)
        tree[dex].sum[i]=tree[dex<<1].sum[i]+tree[dex<<1|1].sum[((i-tree[dex<<1].cnt)%5+5)%5];
}

void update(int l,int r,int dex,int pos,int flag,int val)
{
    tree[dex].cnt+=flag;
    if(l==r)
    {
        if(flag==1)
           tree[dex].sum[1]=val;
        else
           tree[dex].sum[1]=0;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)  update(l,mid,dex<<1,pos,flag,val);
    else update(mid+1,r,dex<<1|1,pos,flag,val);
    push_up(dex);
}

int main()
{
    int tot,pos,flag;
    while(~scanf("%d",&n))
    {
        tot=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",op[i]);
            if(op[i][0]!='s')
            {
                scanf("%d",&b[i]);
                a[tot++]=b[i];
            }
        }
        sort(a,a+tot);
        tot=unique(a,a+tot)-a;
        if(tot==0)  memset(tree[1].sum,0,sizeof(tree[1].sum));
        else buildtree(1,tot,1);
        for(int i=1;i<=n;i++)
        {
            pos=lower_bound(a,a+tot,b[i])-a;
            pos++;
            if(op[i][0]=='a')
            {
                flag=1;
                update(1,tot,1,pos,flag,b[i]);
            }
            else if(op[i][0]=='d')
            {
                flag=-1;
                update(1,tot,1,pos,flag,b[i]);
            }
            else
                printf("%I64d\n",tree[1].sum[3]);
        }
    }
    return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • Python语言实现C-S架构–基于TCP通信[通俗易懂]

    Python语言实现C-S架构–基于TCP通信[通俗易懂]加粗样式@[TOC](http://blog.chinaunix.net/uid-26833883-id-3500874.html欢迎使用Markdown编辑器你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。新的改变我们对Markdown编辑器进行了一些功能拓展与语…

  • MVC三层架构理解

    MVC三层架构理解MVC三层架构什么是MVC:ModelviewController模型、视图、控制器以前的架构用户直接访问控制层,控制层就可以直接操作数据库;servlet–CRUD–>数据库弊端:程序十分臃肿,不利于维护servlet的代码中:处理请求、响应、视图跳转、处理JDBC、处理业务代码、处理逻辑代码架构:没有什么是加一层解决不了的!程序猿调用↑JDBC(实现该接口)↑MysqlOracleSqlServer….(不同厂商)MVC三层架构M

  • vmm安装hassos_安装freenas无法启动

    vmm安装hassos_安装freenas无法启动提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档使用群辉VMM安装freenas前言用vm玩一段时间黑群NAS,就像尝试一下用VMM,觉得想折腾一下freenas。感觉有啥区别。下面是我安装的教程以及遇到的一些问题。保姆级教程。一、需要准备文件1,freenasFreeNAS-11.2-U7.iso2、打开群辉VMM3.添加镜像文件。其他系统的也可以添加进来,选择ISO下载的镜像文件。![在这里插入图片描述](https://img-blog.csdnimg.cn/28.

  • Navicat连接MySQL数据库报错1045

    Navicat连接MySQL数据库报错1045

  • 复杂json转MAP对象

    复杂json转MAP对象普通json对象或者字符串转换map或者实体就不说了,这里主要提供复杂json转map的方法,直接上java代码了:publicclassJsonUtils{ /** *类描述:复杂json字符串转换为Map,包含数组时value为List。 */ publicstaticMapjson2Map(Stringjson){ LinkedMap

  • Spring Cloud入门-Eureka服务注册与发现(Hoxton版本)

    Spring Cloud入门-Eureka服务注册与发现(Hoxton版本)文章目录什么是SpringCloud摘要Eureka简介搭建Eureka注册中心创建父工程springcloud-learning创建Eureka服务端模块使用IDEA的RunDashboard来运行SpringCloud应用搭建Eureka客户端搭建Eureka注册中心集群搭建两个注册中心运行Eureka注册中心集群给Eureka注册中心添加认证创建一个eureka-security-ser…

发表回复

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

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