企业网站设计与管理系统,网站详细设计,网站建设研究课题,吉林省建筑工程网文章目录RobotProduct SumBuilding BridgesJump missionRobot
BZOJ3938
机器人每次一旦改变速度#xff0c;直到下一次改变速度为止
这一时间段内机器人的位置下标可以用一次函数表示
如果知道时刻t1t_1t1即将改变速度的机器人位置#xff0c;以及最近的下一次机器人速…
文章目录RobotProduct SumBuilding BridgesJump missionRobot
BZOJ3938
机器人每次一旦改变速度直到下一次改变速度为止
这一时间段内机器人的位置下标可以用一次函数表示
如果知道时刻t1t_1t1即将改变速度的机器人位置以及最近的下一次机器人速度再次变化的时刻t2t_2t2
利用数学工具可以算出这条线段的解析式两点式计算
(t1,d)−(t2,dv(t2−t1))\big(t_1,d\big)-\big(t_2,dv(t_2-t_1)\big)(t1,d)−(t2,dv(t2−t1))
机器人的多次更换速度那么一个机器人的位置其实就是若干条折线
将操作按照时间排序记录上一次同一个机器人的操作时间速度等然后计算出线段
李超数就可以查询ttt时刻的最远值了位置有正负所以计算后要取绝对值哦
还有时间ttt的离散化线段树内存不允许开[0,1e9][0,1e9][0,1e9]这么大
#include cstdio
#include iostream
#include algorithm
using namespace std;
#define int long long
#define inf 1e9
#define maxn 600005
#define lson num 1
#define rson num 1 | 1
struct node{int k, b;node(){}node( int K, int B ) { k K, b B; }
}t[maxn 2];struct query { int ti, k, x, opt; }q[maxn];int d[maxn], Time[maxn], V[maxn], lst_t[maxn], lst_v[maxn], T[maxn], val[maxn];
bool vis[maxn];
int m;void build( int num, int l, int r ) {t[num] node( 0, 0 );if( l r ) return;int mid l r 1;build( lson, l, mid );build( rson, mid 1, r );
}int Fabs( int x ) { return x 0 ? -x : x; }int calc( node l, int x ) { return Fabs( l.k * T[x] l.b ); }bool cover( node lst, node now, int x ) { return calc( lst, x ) calc( now, x ); }void insert( int num, int l, int r, node now ) {if( cover( t[num], now, l ) and cover( t[num], now, r ) ) {t[num] now;return;}if( l r ) return;int mid l r 1;if( cover( t[num], now, mid ) ) swap( t[num], now );if( cover( t[num], now, l ) ) insert( lson, l, mid, now );if( cover( t[num], now, r ) ) insert( rson, mid 1, r, now );
}void modify( int num, int l, int r, int L, int R, node now ) {if( R l or r L ) return;if( L l and r R ) { insert( num, l, r, now ); return; }int mid l r 1;modify( lson, l, mid, L, R, now );modify( rson, mid 1, r, L, R, now );
}int query( int num, int l, int r, int x ) {if( l r ) return calc( t[num], x );int mid l r 1, ans;if( x mid ) ans query( lson, l, mid, x );else ans query( rson, mid 1, r, x );return max( ans, calc( t[num], x ) );
}int find( int x ) { return lower_bound( T 1, T m 1, x ) - T; }signed main() {int n, Q; char opt[10];scanf( %lld %lld, n, Q ); build( 1, 0, maxn );for( int i 1;i n;i ) {scanf( %lld, d[i] );modify( 1, 0, maxn, 0, 0, node( 0, d[i] ) );}T[ m] 0;for( int i 1;i Q;i ) {scanf( %lld %s, q[i].ti, opt );T[ m] q[i].ti;if( opt[0] c ) {q[i].opt 0;scanf( %lld %lld, q[i].k, q[i].x );lst_t[i] Time[q[i].k], Time[q[i].k] q[i].ti;lst_v[i] V[q[i].k], V[q[i].k] q[i].x;}else q[i].opt 1;}sort( T 1, T m 1 );m unique( T 1, T m 1 ) - T - 1;for( int i 1;i Q;i )if( q[i].opt ) continue;else {int dt q[i].ti - lst_t[i];int y dt * lst_v[i] d[q[i].k];int k lst_v[i];int b y - q[i].ti * k;modify( 1, 0, m, find( lst_t[i] ), find( q[i].ti ), node( k, b ) );d[q[i].k] y;}for( int i Q;i;i -- )if( vis[q[i].k] ) continue;else {vis[q[i].k] 1;int dt inf - q[i].ti;int y dt * q[i].x d[q[i].k];int k q[i].x;int b y - inf * k;modify( 1, 0, m, find( q[i].ti ), m, node( k, b ) );}for( int i 1;i n;i )if( ! vis[i] ) modify( 1, 0, m, 0, m, node( 0, d[i] ) );for( int i 1;i Q;i )if( q[i].opt ) printf( %lld\n, query( 1, 0, m, find( q[i].ti ) ) );return 0;
}Product Sum
CF631E
令S∑i1ni∗aiS\sum_{i1}^ni*a_iS∑i1ni∗ai
考虑当位置iii的数插到位置jjj的时权值的变化 jijiji位置iii的数往前插 ∀k∈[1,j)⋃(i,n]k∗ak\forall k\in[1,j)\bigcup (i,n]\quad k*a_k∀k∈[1,j)⋃(i,n]k∗ak没有变化 ∀k∈[j,i)\forall k\in[j,i)∀k∈[j,i) 每个数都会往后移一位k∗ak←(k1)∗akk*a_k\leftarrow (k1)*a_kk∗ak←(k1)∗akSSS增加∑kji−1ak\sum_{kj}^{i-1}a_k∑kji−1ak iii前移i−ji-ji−j位到jjji∗ai←j∗aii*a_i\leftarrow j*a_ii∗ai←j∗aiSSS减少(i−j)ai(i-j)a_i(i−j)ai 设fif_ifi 考虑第iii个位置往前移动到某个位置时的最大权值sumi∑j1iajsum_i\sum_{j1}^ia_jsumi∑j1iaj 从小到大枚举i fimin{Ssumi−1−sumj−1(i−j)ai}Ssumi−1i⋅aimin{−j∗ai−sumj−1}f_i\min\Big\{Ssum_{i-1}-sum_{j-1}(i-j)a_i\Big\}Ssum_{i-1}i·a_i\min\Big\{-j*a_i-sum_{j-1}\Big\} fimin{Ssumi−1−sumj−1(i−j)ai}Ssumi−1i⋅aimin{−j∗ai−sumj−1} −j-j−j看做直线斜率kkk−sumj−1-sum_{j-1}−sumj−1看做直线截距bbbaia_iai就是因变量xxx jijiji位置iii的数往后插 ∀k∈[1,i)⋃(j,n]k∗ak\forall k\in[1,i)\bigcup (j,n]\quad k*a_k∀k∈[1,i)⋃(j,n]k∗ak没有变化 ∀k∈(i,j]\forall k\in(i,j]∀k∈(i,j] 每个数都会往前移一位k∗ak←(k−1)∗akk*a_k\leftarrow (k-1)*a_kk∗ak←(k−1)∗akSSS减少∑ki1jak\sum_{ki1}^ja_k∑ki1jak iii后移j−ij-ij−i位到jjji∗ai←j∗aii*a_i\leftarrow j*a_ii∗ai←j∗aiSSS增加(j−i)ai(j-i)a_i(j−i)ai 设fif_ifi 考虑第iii个位置往移动后到某个位置时的最大权值sumi∑j1iajsum_i\sum_{j1}^ia_jsumi∑j1iaj 从大到小枚举i fimin{S−(sumj−sumi)(j−i)ai}Ssumi−i⋅aimin{j∗ai−sumj}f_i\min\Big\{S-(sum_j-sum_i)(j-i)a_i\Big\}Ssum_i-i·a_i\min\Big\{j*a_i-sum_j\Big\} fimin{S−(sumj−sumi)(j−i)ai}Ssumi−i⋅aimin{j∗ai−sumj} jjj看做直线斜率kkk−sumj-sum_{j}−sumj看做直线截距bbbaia_iai就是因变量xxx
#include cstdio
#include iostream
using namespace std;
#define int long long
#define inf 1e18
#define maxn 1000000
#define lson num 1
#define rson num 1 | 1
struct node {int k, b;node(){}node( int K, int B ) { k K, b B; }
}t[( maxn 5 ) 3];void build( int num, int l, int r ) {t[num] node( 0, -inf );if( l r ) return;int mid l r 1;build( lson, l, mid );build( rson, mid 1, r );
}int calc( node l, int x ) { return l.k * x l.b; }int cover( node lst, node now, int x ) { return calc( lst, x ) calc( now, x ); }void insert( int num, int l, int r, node now ) {if( cover( t[num], now, l ) and cover( t[num], now, r ) ) {t[num] now;return;}if( l r ) return;int mid l r 1;if( cover( t[num], now, mid ) ) swap( t[num], now );if( cover( t[num], now, l ) ) insert( lson, l, mid, now );if( cover( t[num], now, r ) ) insert( rson, mid 1, r, now );
}int query( int num, int l, int r, int x ) {if( l r ) return calc( t[num], x );int mid l r 1, ans 0;if( x mid ) ans query( lson, l, mid, x );else ans query( rson, mid 1, r, x );return max( ans, calc( t[num], x ) );
}int A[maxn], sum[maxn], ans, ret;
int n;
signed main() {scanf( %lld, n );for( int i 1;i n;i ) scanf( %lld, A[i] );for( int i 1;i n;i ) sum[i] sum[i - 1] A[i];for( int i 1;i n;i ) ans i * A[i];ret ans;build( 1, -maxn, maxn );insert( 1, 1, n, node( 1, 0 ) );for( int i 2;i n;i ) {ret max( ret, ans sum[i - 1] - A[i] * i query( 1, -maxn, maxn, A[i] ) );insert( 1, -maxn, maxn, node( i, - sum[i - 1] ) );}build( 1, -maxn, maxn );insert( 1, -maxn, maxn, node( n, -sum[n] ) );for( int i n - 1;i;i -- ) {ret max( ret, ans sum[i] - A[i] * i query( 1, -maxn, maxn, A[i] ) );insert( 1, -maxn, maxn, node( i, - sum[i] ) );}printf( %lld\n, ret );return 0;
}Building Bridges
LOJ2483
设dpi:dp_i:dpi: 使1−i1-i1−i联通的最小花费
考虑暴力dpdpdp转移枚举桥建筑在jjj和iii根柱子之间
dpimin{dpj∑kj1i−1wk(hi−hj)2}dp_i\min\Big\{dp_j\sum_{kj1}^{i-1}w_k(h_i-h_j)^2\Big\}dpimin{dpj∑kj1i−1wk(hi−hj)2}
前缀和优化sumi∑j1iwjsum_i\sum_{j1}^iw_jsumi∑j1iwj dpimin{dpjsumi−1−sumjhi2−2hihjhj2}sumi−1hi2min{−2hj∗hidpj−sumjhj2}dp_i\min\Big\{dp_jsum_{i-1}-sum_{j}h_i^2-2h_ih_jh_j^2\Big\}\\ sum_{i-1}h_i^2\min\Big\{-2h_j*h_idp_j-sum_jh_j^2\Big\} dpimin{dpjsumi−1−sumjhi2−2hihjhj2}sumi−1hi2min{−2hj∗hidpj−sumjhj2}
#include cstdio
#include iostream
using namespace std;
#define int long long
#define maxn 1000000
#define lson num 1
#define rson num 1 | 1
#define inf 1e18
struct node {int k, b;node(){}node( int K, int B ) { k K, b B; }
}t[( maxn 5 ) 2];int calc( node l, int x ) { return l.k * x l.b; }bool cover( node lst, node now, int x ) { return calc( lst, x ) calc( now, x ); }void build( int num, int l, int r ) {t[num] node( 0, inf );if( l r ) return;int mid l r 1;build( lson, l, mid );build( rson, mid 1, r );
}void insert( int num, int l, int r, node now ) {if( cover( t[num], now, l ) and cover( t[num], now, r ) ) {t[num] now;return;}if( l r ) return;int mid l r 1;if( cover( t[num], now, mid ) ) swap( t[num], now );if( cover( t[num], now, l ) ) insert( lson, l, mid, now );if( cover( t[num], now, r ) ) insert( rson, mid 1, r, now );
}int query( int num, int l, int r, int x ) {if( l r ) return calc( t[num], x );int mid l r 1, ans;if( x mid ) ans query( lson, l, mid, x );else ans query( rson, mid 1, r, x );return min( ans, calc( t[num], x ) );
}int h[maxn], w[maxn], dp[maxn], sum[maxn];signed main() {int n;scanf( %lld, n );for( int i 1;i n;i ) scanf( %lld, h[i] );for( int i 1;i n;i ) scanf( %lld, w[i] );for( int i 1;i n;i ) sum[i] sum[i - 1] w[i];build( 1, 0, maxn );insert( 1, 0, maxn, node( -2 * h[1], -sum[1] h[1] * h[1] ) );for( int i 2;i n;i ) {dp[i] sum[i - 1] h[i] * h[i] query( 1, 0, maxn, h[i] );insert( 1, 0, maxn, node( -2 * h[i], dp[i] - sum[i] h[i] * h[i] ) );}printf( %lld\n, dp[n] );return 0;
}Jump mission
CodeChef
设dpi:dp_i:dpi: 在iii座山停留的最小花费
考虑暴力dpdpdp转移枚举上一次停留在jjj山 dpimin{dpjAihi2−2hihjhj2}Aihi2min{−2hj∗hidpjhj2}dp_i\min\Big\{dp_jA_ih_i^2-2h_ih_jh_j^2\Big\}A_ih_i^2\min\Big\{-2h_j*h_idp_jh_j^2\Big\} dpimin{dpjAihi2−2hihjhj2}Aihi2min{−2hj∗hidpjhj2} 从小到大枚举iii利用前面枚举过的山当jjj这只能保证jijiji的条件
然而本题多了一个PjPiP_jP_iPjPi的限制
这个时候只有献出神祭——树套树将PPP利用树状数组嵌套在李超线段树外面
自然内存就会多一些看着开就行了
#include cstdio
#include iostream
using namespace std;
#define int long long
#define inf 5e18
#define maxn 600000
struct node {int k, b;node(){ k 0, b inf; }node( int K, int B ) { k K, b B; }
}t[maxn * 80];
int lson[maxn * 80], rson[maxn * 80];
int cnt;int calc( node l, int x ) { return l.k * x l.b; }bool cover( node lst, node now, int x ) { return calc( lst, x ) calc( now, x ); }void insert( int num, int l, int r, node now ) {if( ! num ) num cnt, t[num] node( 0, inf );if( cover( t[num], now, l ) and cover( t[num], now, r ) ) {t[num] now;return;}if( l r ) return;int mid ( l r ) 1;if( cover( t[num], now, mid ) ) swap( t[num], now );if( cover( t[num], now, l ) ) insert( lson[num], l, mid, now );if( cover( t[num], now, r ) ) insert( rson[num], mid 1, r, now );
}int query( int num, int l, int r, int x ) {if( ! num ) return inf;if( l r ) return calc( t[num], x );int mid ( l r ) 1, ans;if( x mid ) ans query( lson[num], l, mid, x );else ans query( rson[num], mid 1, r, x );return min( ans, calc( t[num], x ) );
}int p[maxn], a[maxn], h[maxn], dp[maxn], root[maxn];
int n;int lowbit( int i ) { return i -i; }void add( int i, node l ) {for( ;i n;i lowbit( i ) ) insert( root[i], 1, maxn, l );
}int query( int i, int x ) {int ans inf;for( ;i;i - lowbit( i ) ) ans min( ans, query( root[i], 1, maxn, x ) );return ans;
}signed main() {scanf( %lld, n );for( int i 1;i n;i ) scanf( %lld, p[i] );for( int i 1;i n;i ) scanf( %lld, a[i] );for( int i 1;i n;i ) scanf( %lld, h[i] );dp[1] a[1], add( p[1], node( -2 * h[1], h[1] * h[1] dp[1] ) );for( int i 2;i n;i ) {dp[i] a[i] h[i] * h[i] query( p[i], h[i] );add( p[i], node( - 2 * h[i], h[i] * h[i] dp[i] ) );}printf( %lld\n, dp[n] );return 0;
}李超数注意两点即可
推出能够转化成直线解析式的转移方程式确定线段树点的区间范围究竟是哪个值做线段树区间是否需要离散化
