勤快的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)
blank

相关推荐

  • centos 7如何将 网卡ens33 修改成 eth0「建议收藏」

    centos 7如何将 网卡ens33 修改成 eth0「建议收藏」文章目录linux网卡名称命名命名规则修改eth0方法linux网卡名称命名命名规则CENTOS6的网卡命名方式它会根据情况有所改变而非唯一且固定,在CENTOS6之前,网络接口使用连续号码命名:eth0、eth1等,当增加或删除网卡时,名称可能会发生变化CENTOS7命名方式采用dmidecode采集命名方案,以此来得到主板信息;它可以实现网卡名字永久唯一化(dmidecode这个命令可以采集有关硬件方面的信息)对网络设备的命名方式:1)如果Firmware(固件)或B

  • Java基础语法(四)基本语法和数据类型

    Java基础语法(四)基本语法和数据类型

  • leetcode 接雨水2_leetcode会议室

    leetcode 接雨水2_leetcode会议室题目链接给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。示例 1:输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。示例 2:输入:height = [4,2,0,3,2,5]输出:9 提示:n == height.length0 <= n &lt

  • svn配置忽略文件

    svn配置忽略文件1、添加忽略项项目根目录,找到SVN->右键->属性新建,其它->选择svn:ignore输入要忽略的内容确定即可。2、全局忽略配置svn->右键->设置即可

  • map转map_java获取map的值

    map转map_java获取map的值String转map:Mapmap_new=newGson().fromJson(s,map.getClass());//需要引入jar包引用的jar<!–配置gson–><dependency><groupId>com.google.code.gson</groupId><artifactId>gson</artifactId><version>2.2.4</v.

  • c语言生成随机数数组

    c语言实现获得从0~num-1的随机数组(数组元素不重复,内容是0~num-1),实现的原理是数组乱序,效率高!

发表回复

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

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