勤快的love枫[ZJOI2007]

勤快的love枫[ZJOI2007]

大家好,又见面了,我是全栈君。

题目描述

小绝恋love 枫是一个出纳,经常需要做一些统计报表的工作。今天是绝恋love 枫的生日,小绝恋love 枫希望可以帮爸爸分担一些工作,作为他的生日礼物之一。经过仔细观察,小绝恋love 枫发现统计一张报表实际上是维护一个非负整数数列,并且进行一些查询操作。在最开始的时候,有一个长度为的整数序列,并且有以下三种操作:INSERT i k 在原数列的第个元素后面添加一个新元素k;如果原数列的第个元素已经添加了若干元素,则添加在这些元素的最后(见下面的例子)

MIN_GAP 查询相邻两个元素的之间差值(绝对值)的最小值

MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值(绝对值)

例如一开始的序列为

5 3 1

执行操作INSERT 2 9 将得到:

5 3 9 1

此时MIN_GAP 为2,MIN_SORT_GAP 为2。

再执行操作INSERT 2 6 将得到:

5 3 9 6 1

注意这个时候原序列的第2 个元素后面已经添加了一个9,此时添加的6 应加在9 的后面。这个时候MIN_GAP 为2,MIN_SORT_GAP 为1。于是小绝恋love 枫写了一个程序,使得程序可以自动完成这些操作,但是他发现对于一些大的报表他的程序运行得很慢,你能帮助他改进程序么?

 

输入

第一行包含两个整数N,M,分别表示原数列的长度以及操作的次数。

第二行为个整数,为初始序列。

接下来的行每行一个操作,即“INSERT i k”,“MIN_GAP”,“MIN_SORT_GAP”中的一种(无多余空格或者空行)。

 

输出

对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令,输出一行答案即可。

 

样例输入

3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

样例输出

2
2
1

提示

对于30% 的数据,N≤1000,M≤5000

对于100% 的数据,N,M≤50000

对于所有的数据,序列内的整数不超过5*10^8。

 

题解

       一道显而易见的数据结构题,在数据结构题里几乎算不用动脑子的那种。前后最小的一下子想到钢哥讲过的垃圾堆,维护两个堆就可以实现有效答案的添加和删除。原数列也可以用一个副本数组,只维护目前最靠前和最靠后的值(考试时忘了下一个位置的开头元素还需要记录,炸了不少分)。但是整个序列中最相近的两个元素,就有些犯难。明明知道就应该建个平衡树找前驱后继,尴尬的情况是平衡树只打过Treap,Treap只打过两道题,还是一两周之前的事了,考场上打挂可能性极大。权衡了一下,还是拿了个数组暴力排序,唯一的优化是如果最小值已经为0就不再改动。算上这道题平衡树也只打过三道,简直不能算做过题。书到用时方恨少,事非经过不知难,从第一次见到这句话到现在已经有些年了,理解倒是越来越深了= =。

 

勤快的love枫[ZJOI2007]
勤快的love枫[ZJOI2007]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<cmath>
using namespace std;
const int sj=50010;
int n,m,a[sj],a1,a2,mi,g,q,h,jq,hj,size,d[sj];
priority_queue<int,vector<int>,greater<int> > qi;
priority_queue<int,vector<int>,greater<int> > du;
char c[20];
struct tree
{
     int l,r,v,rnd;
}t[sj];
int bj(int x,int y)
{
     return x<y?x:y;
}
void lturn(int &x)
{
     int tt=t[x].r;
     t[x].r=t[tt].l;
     t[tt].l=x;
     x=tt;
}
void rturn(int &x)
{
     int tt=t[x].l;
     t[x].l=t[tt].r;
     t[tt].r=x;
     x=tt;
}
void query_pre(int k,int x)
{
     if(k==0) return;
     if(t[k].v<x)
     {
         q=k;
         query_pre(t[k].r,x);
     }
     else query_pre(t[k].l,x);
}
void query_beh(int k,int x)
{
     if(k==0) return;
     if(t[k].v>x)
     {
        h=k;
        query_beh(t[k].l,x);
     }
     else query_beh(t[k].r,x);
}
void cr(int &x,int y)
{
     if(x==0)
     {
        size++;
        x=size;
        t[x].rnd=rand();
        t[x].v=y;
        return;
     }
     if(t[x].v==y)
     {
        jq=hj=y;
        q=h=1;
        return;
     }
     if(y>t[x].v)
     {
        cr(t[x].r,y);
        if(t[x].rnd>t[t[x].r].rnd) lturn(x);
     }
     if(y<t[x].v)
     {
        cr(t[x].l,y);
        if(t[x].rnd>t[t[x].l].rnd) rturn(x);
     }
}
void init()
{
    scanf("%d%d",&n,&m);
    mi=0x7fffffff;
    for(int i=1;i<=n;i++) 
    {
      scanf("%d",&a[i]);
      if(i!=1) qi.push(abs(a[i]-a[i-1]));
      if(mi) 
      {
        q=h=-1;
        jq=hj=0;
        cr(g,a[i]);
        if(q==-1)
        {
           query_beh(g,a[i]);
           query_pre(g,a[i]);
           if(q!=-1||h!=-1)
           {
             jq=(q==-1)?0x7fffffff:t[q].v;
             hj=(h==-1)?0x7fffffff:t[h].v;
             mi=bj(mi,abs(a[i]-jq));
             mi=bj(mi,abs(a[i]-hj));
           }
        }
        else mi=0;
      }
      memcpy(d,a,sizeof(a));
    }
}
void cl()
{
     for(int i=1;i<=m;i++)
     {
        scanf("%s",c);
        if(c[4]=='R')
        {
           scanf("%d%d",&a1,&a2);
           if(a1!=n)
           {
             qi.push(abs(a2-a[a1+1]));
             du.push(abs(a[a1+1]-d[a1]));
           }
           qi.push(abs(a2-d[a1]));
           d[a1]=a2;
           if(mi) 
           {
              q=h=-1;
              jq=hj=0;
              cr(g,a2);
              if(q==-1)
              {
                query_beh(g,a2);
                query_pre(g,a2);
                if(q!=-1||h!=-1)
                {
                  jq=(q==-1)?0x7fffffff:t[q].v;
                  hj=(h==-1)?0x7fffffff:t[h].v;
                  mi=bj(mi,abs(a2-jq));
                  mi=bj(mi,abs(a2-hj));
                }
              }
              else mi=0;
           }
        }
        if(c[4]=='G')
        {
           while(!qi.empty()&&!du.empty()&&qi.top()==du.top())
           {
              qi.pop();
              du.pop();
           }
           printf("%d\n",qi.top());
        }
        if(c[4]=='S') printf("%d\n",mi);
     }
}
int main()
{
    init();
    cl();
    return 0;
}

love

 

     在cogs上看到了这题,交了一下RE,发现数据范围是十倍……调了数组大小再交一遍,居然TLE了!据说堆可能会炸掉,不得已又改成了线段树。跑得确实快了,可是比堆难写得多啊。差点上两百行【抵制恶意缩行不良风气,从我做起!

勤快的love枫[ZJOI2007]
勤快的love枫[ZJOI2007]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int sj=500010;
int n,m,a[sj],a1,a2,mi,g,q,h,jq,hj,size,d[sj],last;
struct xs
{
     int v,l,r;
}xds[sj*8];
char c[20];
struct tree
{
     int l,r,v,rnd;
}t[sj];
int bj(int x,int y)
{
     return x<y?x:y;
}
void lturn(int &x)
{
     int tt=t[x].r;
     t[x].r=t[tt].l;
     t[tt].l=x;
     x=tt;
}
void rturn(int &x)
{
     int tt=t[x].l;
     t[x].l=t[tt].r;
     t[tt].r=x;
     x=tt;
}
void query_pre(int k,int x)
{
     if(k==0) return;
     if(t[k].v<x)
     {
         q=k;
         query_pre(t[k].r,x);
     }
     else query_pre(t[k].l,x);
}
void query_beh(int k,int x)
{
     if(k==0) return;
     if(t[k].v>x)
     {
        h=k;
        query_beh(t[k].l,x);
     }
     else query_beh(t[k].r,x);
}
void cr(int &x,int y)
{
     if(x==0)
     {
        size++;
        x=size;
        t[x].rnd=rand();
        t[x].v=y;
        return;
     }
     if(t[x].v==y)
     {
        jq=hj=y;
        q=h=1;
        return;
     }
     if(y>t[x].v)
     {
        cr(t[x].r,y);
        if(t[x].rnd>t[t[x].r].rnd) lturn(x);
     }
     if(y<t[x].v)
     {
        cr(t[x].l,y);
        if(t[x].rnd>t[t[x].l].rnd) rturn(x);
     }
}
void build(int x,int z,int y)
{
     xds[x].l=z;
     xds[x].r=y;
     xds[x].v=0x7fffffff;
     if(z==y)  return;
     int mid=(z+y)>>1;
     build(x<<1,z,mid);
     build((x<<1)|1,mid+1,y);
}
void update(int x,int z,int y)
{
     if(xds[x].l==xds[x].r&&xds[x].l==z)
     {
        xds[x].v=y;
        return;
     }
     int mid=(xds[x].l+xds[x].r)>>1;
     if(z<=mid) 
     {
        update(x<<1,z,y);
        xds[x].v=bj(xds[(x<<1)|1].v,xds[x<<1].v);
     }
     else
     {
        update((x<<1)|1,z,y);
        xds[x].v=bj(xds[(x<<1)|1].v,xds[x<<1].v);
     }
}
void init()
{
    scanf("%d%d",&n,&m);
    mi=0x7fffffff;
    build(1,1,sj*2-5);
    for(int i=1;i<=n;i++) 
    {
      scanf("%d",&a[i]);
      if(i!=1) update(1,i-1,abs(a[i]-a[i-1]));
      if(mi) 
      {
        q=h=-1;
        jq=hj=0;
        cr(g,a[i]);
        if(q==-1)
        {
           query_beh(g,a[i]);
           query_pre(g,a[i]);
           if(q!=-1||h!=-1)
           {
             jq=(q==-1)?0x7fffffff:t[q].v;
             hj=(h==-1)?0x7fffffff:t[h].v;
             mi=bj(mi,abs(a[i]-jq));
             mi=bj(mi,abs(a[i]-hj));
           }
        }
        else mi=0;
      }
    }
    memcpy(d,a,sizeof(a));
    last=n-1;
}
void cl()
{
     for(int i=1;i<=m;i++)
     {
        scanf("%s",c);
        if(c[4]=='R')
        {
           scanf("%d%d",&a1,&a2);
           last++;
           update(1,last,abs(a2-d[a1]));
           update(1,a1,abs(a2-a[a1+1]));
           d[a1]=a2;
           if(mi) 
           {
              q=h=-1;
              jq=hj=0;
              cr(g,a2);
              if(q==-1)
              {
                query_beh(g,a2);
                query_pre(g,a2);
                if(q!=-1||h!=-1)
                {
                  jq=(q==-1)?0x7fffffff:t[q].v;
                  hj=(h==-1)?0x7fffffff:t[h].v;
                  mi=bj(mi,abs(a2-jq));
                  mi=bj(mi,abs(a2-hj));
                }
              }
              else mi=0;
           }
        }
        if(c[4]=='G') printf("%d\n",xds[1].v);
        if(c[4]=='S') printf("%d\n",mi);
     }
}
int main()
{
    init();
    cl();
    return 0;
}

form

 

 

转载于:https://www.cnblogs.com/moyiii-/p/7270753.html

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

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

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

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

(0)


相关推荐

  • 【Netty】mmap 和 sendFile 零拷贝原理

    【Netty】mmap 和 sendFile 零拷贝原理一、零拷贝简介、二、传统BIO数据拷贝分析(4拷贝4切换)、三、mmap内存映射(3拷贝4切换)、四、sendFile函数(Linux2.1优化)(3拷贝2切换)、五、sendFile函数(Linux2.4优化)(2拷贝2切换)、

  • Sqoop问题解决:运行报错java.lang.RuntimeException: Could not load db driver class: com.mysql.jdbc.Driver

    Sqoop问题解决:运行报错java.lang.RuntimeException: Could not load db driver class: com.mysql.jdbc.DriverSqoop问题解决:运行报错报错信息:java.lang.RuntimeException:Couldnotloaddbdriverclass:com.mysql.jdbc.Driver原因分析:未将mysql关系型数据库驱动包放到sqoop/lib目录下解决方法:将mysql关系型数据库驱动包放到sqoop/lib目录下这里需要下载mysql关系型数据库驱动包放到本地/opt/software/下mysql依赖包下载链接:https://pan.baidu.com/s

  • 腾讯会议——录制的视频如何正常观看(转为MP4格式)

    腾讯会议——录制的视频如何正常观看(转为MP4格式)操作步骤1.打开腾讯会议2.点击**历史会议**3.点击你录制的会议4.点击**录制详情**5.点击**转码**1.打开腾讯会议2.点击历史会议3.点击你录制的会议4.点击录制详情5.点击转码完成这5步,即可将所保存的视频转为MP4格式,便于观看。…

  • pytest指定用例_文件夹排列顺序自定义

    pytest指定用例_文件夹排列顺序自定义前言测试用例在设计的时候,我们一般要求不要有先后顺序,用例是可以打乱了执行的,这样才能达到测试的效果.有些同学在写用例的时候,用例写了先后顺序,有先后顺序后,后面还会有新的问题(如:上个用例返回

  • 计算机实现原理专题–二进制减法器(三)「建议收藏」

    计算机实现原理专题–二进制减法器(三)「建议收藏」在计算机实现原理专题–二进制减法器(二)中指出当时的减法器需要人工判断被减数和减数的大小,如果能让计算机来自动判断就更好了。实际上计算机采用了补码来表达有符号数,在之前的java整形数值表示–基础中就说明了,采用补码可将减法变成加法。对于正数而言它的补码就是原码如21=0001_010…

  • 业务安全(逻辑漏洞)

    业务安全(逻辑漏洞)文章目录业务安全概述黑客攻击的目标业务安全测试流程测试准备业务调研业务建模业务流程梳理业务风险点的识别开展测试撰写报告业务数据安全商品支付金额篡改前端JS限制绕过验证请求重放测试业务上限测试商品订购数量篡改damiCMSV5.1为例密码找回安全验证码客户端回显测试验证码暴力破解Response状态值修改测试Session覆盖弱token设计缺陷测试密码找回流程绕过测试接口参数账号修改metinfoV4.0为例业务安全概述近年来,随着信息化技术的迅速发展和全球一体化进程的不断加快,计算机和网

发表回复

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

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