找人做网站要多少钱,mysql网站数据库,网站更换域名备案,seo织梦网站建设步骤题目描述 Q的妈妈是一个出纳#xff0c;经常需要做一些统计报表的工作。今天是妈妈的生日#xff0c;小Q希望可以帮妈妈分担一些工作#xff0c;作为她的生日礼物之一。 经过仔细观察#xff0c;小Q发现统计一张报表实际上是维护一个非负整数数列#xff0c;并且进行一些查…题目描述 Q的妈妈是一个出纳经常需要做一些统计报表的工作。今天是妈妈的生日小Q希望可以帮妈妈分担一些工作作为她的生日礼物之一。 经过仔细观察小Q发现统计一张报表实际上是维护一个非负整数数列并且进行一些查询操作。 在最开始的时候有一个长度为N的整数序列并且有以下三种操作 INSERT i k在原数列的第i个元素后面添加一个新元素k如果原数列的第i个元素已经添加了若干元素则添加在这些元素的最后见下面的例子MIN_GAP查询相邻两个元素的之间差值绝对值的最小值MIN_SORT_GAP查询所有元素中最接近的两个元素的差值绝对值例如一开始的序列为5, 3, 1。 执行操作INSERT 2 9将得到5, 3, 9, 1此时MIN_GAP为22MIN_SORT_GAP为22。 再执行操作INSERT 2 6将得到5, 3, 9, 6, 1 注意这个时候原序列的第2个元素后面已经添加了一个9此时添加的6应加在9的后面。这个时候MIN_GAP为2MIN_SORT_GAP为1。 于是小Q写了一个程序使得程序可以自动完成这些操作但是他发现对于一些大的报表他的程序运行得很慢你能帮助他改进程序么 输入输出格式 输入格式 第一行包含两个整数NM分别表示原数列的长度以及操作的次数。 第二行为N个整数为初始序列。 接下来的M行每行一个操作即INSERT i kMIN_GAPMIN_SORT_GAP 中的一种无多余空格或者空行。 输出格式 对于每一个MIN_GAP和MIN_SORT_GAP命令输出一行答案即可。 输入输出样例 输入样例#1 3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP输出样例#1 2
2
1说明 对于30%的数据N ≤ 1000 ,M ≤ 5000对于100%的数据N ,M ≤500000对于所有的数据序列内的整数不超过5×108。 时限2s Solution 本题splay堆好水啊乱打的代码都能AC~。 分析题目 操作1加入一个数只会改变相邻的关系所以数组模拟随便乱搞维护下相邻关系。 操作2加入一个数改变的是两对相邻的差值所以可以直接用带修改的堆去维护pbds大法好。 操作3由于是维护全局最小值那么只需要在加入数时在其插入二叉搜索树的遍历过程中与访问过的节点更新下答案当然为了保证树的平衡选用平衡树写写就行了。 代码 /*Code by 520 -- 9.17*/
#includebits/stdc.h
#includeext/pb_ds/assoc_container.hpp
#includeext/pb_ds/priority_queue.hpp
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)(a);(i)(b);(i))
#define Bor(i,a,b) for(RE int (i)(b);(i)(a);(i)--)
#define son(x) (xch[fa[x]][1])
using namespace std;
using namespace __gnu_pbds;
const int N1000005;
int n,m,a[N1][2],tot,val[N1];
int root,ch[N][2],fa[N],cnt,date[N];
int minn0x7fffffff;
struct node{int ls,rs,val;bool operator (const node a) const {return vala.val;}
};
typedef __gnu_pbds::priority_queuenode,lessnode,pairing_heap_tag heap;
heap q;
heap::point_iterator id[N];int gi(){int a0;char xgetchar();bool f0;while((x0||x9)x!-) xgetchar();if(x-) xgetchar(),f1;while(x0x9) a(a3)(a1)(x^48),xgetchar();return f?-a:a;
}il void rotate(int x){int yfa[x],zfa[y],bson(x),cson(y),ach[x][!b];z?ch[z][c]x:rootx; fa[x]z;if(a) fa[a]y; ch[y][b]a;ch[x][!b]y,fa[y]x;
}il void splay(int x,int i){while(fa[x]!i){RE int yfa[x],zfa[y];if(zi) rotate(x);else {if(son(x)son(y)) rotate(y),rotate(x);else rotate(x),rotate(x);}}
}void insert(int rt,int x){if(!rt) {rtcnt,date[cnt]x;return;}if(date[rt]x) {minn0;return;}if(xdate[rt])insert(ch[rt][0],x),fa[ch[rt][0]]rt,minnmin(minn,abs(date[rt]-x));else insert(ch[rt][1],x),fa[ch[rt][1]]rt,minnmin(minn,abs(date[rt]-x));
}int main(){int pos,x; char s[10];ngi(),mgi(),totn;For(i,1,n) {val[i]gi(),insert(root,val[i]),splay(cnt,0);if(i!1) a[i][0]i;if(i!n) a[i][1]i;}For(i,2,n) id[i]q.push(node{i,i1,abs(val[i]-val[i-1])});while(m--){scanf(%s,s);if(s[0]I) {posgi(),val[tot]gi(),insert(root,val[tot]),splay(cnt,0);int tpa[pos][1];id[tot]q.push(node{tot,tp,abs(val[tp]-val[tot])});if(pos!n) q.modify(id[pos1],node{pos1,tot,abs(val[pos1]-val[tot])});a[pos1][0]tot,a[pos][1]tot;}else if(strlen(s)7) printf(%d\n,q.top().val);else printf(%d\n,minn);}return 0;
} 转载于:https://www.cnblogs.com/five20/p/9665522.html
