常用知名购物网站,网页设计与网站建设考试名词解释2019,网站灰色跟,怎么让百度收录网址problem
洛谷链接
solution
纯纯不理解要搬用平衡树的那些做法#xff0c;使我们可可爱爱的链表不香不好写吗#xff1f;#xff1f;
众所周知#xff0c;链表法是可以进行删除和增加的#xff0c;只需要维护每个点的前驱和后继。
相邻两个的差绝对值的最小值#x…problem
洛谷链接
solution
纯纯不理解要搬用平衡树的那些做法使我们可可爱爱的链表不香不好写吗
众所周知链表法是可以进行删除和增加的只需要维护每个点的前驱和后继。
相邻两个的差绝对值的最小值用 set\text{set}set 维护这个绝对值差即可每次增点时把原来的先删掉再加上新的。
任选两个数的差的绝对值更简单直接扔进一个 set\text{set}set 然后每次新加点的时候就 lower_bound() 求前后继全局取 min\text{min}min 即可。
由于值可能相同所以我们用 multiset\text{multiset}multiset 就行了。
非常小清新啊
code
#include bits/stdc.h
using namespace std;
#define maxn 1000005
multiset int s1, s2;
int n, m, ans 0x3f3f3f3f;
int a[maxn], g[maxn], lst[maxn], nxt[maxn];int main() {scanf( %d %d, n, m );for( int i 1;i n;i ) {scanf( %d, a[i] );g[i] i;if( i 1 ) lst[i] i - 1;if( i n ) nxt[i] i 1;if( i 1 ) s1.insert( fabs( a[i] - a[i - 1] ) );s2.insert( a[i] );auto it s2.lower_bound( a[i] );auto l it, r it;if( it ! s2.begin() ) ans min( ans, a[i] - *(--l) );if( (r) ! s2.end() ) ans min( ans, *r - a[i] );}int cnt n;for( int i 1;i m;i ) {char op[10]; int x, k;scanf( %s, op );if( op[0] I ) {scanf( %d %d, x, k );a[ cnt] k;s1.erase( s1.find( fabs( a[g[x]] - a[nxt[g[x]]] ) ) );lst[nxt[g[x]]] cnt;lst[cnt] g[x];nxt[cnt] nxt[g[x]];nxt[g[x]] cnt;g[x] cnt;s1.insert( fabs( k - a[lst[cnt]] ) );s1.insert( fabs( k - a[nxt[cnt]] ) );s2.insert( k );auto it s2.lower_bound( k );auto l it, r it;if( it ! s2.begin() ) ans min( ans, k - *(--l) );if( (r) ! s2.end() ) ans min( ans, *r - k );}else if( op[4] G ) printf( %d\n, *s1.begin() );else printf( %d\n, ans );}return 0;
}
