如何给网站做关键字,昆明网站建设网站,建筑网方成龙,做网站需要哪几个板块problem
洛谷链接
solution
结论#xff1a;最优方案中一定有一种是全程不停的。
断环成链#xff0c;接一个 [1,n][1,n][1,n] 在后面形成 2n2n2n 的序列#xff0c;同时将时间戳逆过来。
转化成#xff1a;在 ttt 时刻从某个位置 i∈[n,2n)i\in[n,2n)i∈[n,2n) 开始往…problem
洛谷链接
solution
结论最优方案中一定有一种是全程不停的。
断环成链接一个 [1,n][1,n][1,n] 在后面形成 2n2n2n 的序列同时将时间戳逆过来。
转化成在 ttt 时刻从某个位置 i∈[n,2n)i\in[n,2n)i∈[n,2n) 开始往前取物品时刻 −1-1−1物品 jjj 在 tjt_jtj 时刻消失要求标记所有的物品。最小化这个 ttt。
ttt 时刻开始从 iii 位置到物品 jjj需要 i−ji-ji−j 的时间即 ∀j∈(i−n,i]t−(i−j)≥Tj\forall_{j\in(i-n,i]}\ t-(i-j)\ge T_j∀j∈(i−n,i] t−(i−j)≥Tj。
显然全程不停歇是更好的。
t−(i−j)≥tj⇒t≥tj−ji,j∈(i−n,i]⇒tminmax{tj−j}i,j∈(i−n,i]t-(i-j)\ge t_j\Rightarrow t\ge t_j-ji,j\in(i-n,i]\Rightarrow t_{\min}\max\{t_j-j\}i,j\in(i-n,i]t−(i−j)≥tj⇒t≥tj−ji,j∈(i−n,i]⇒tminmax{tj−j}i,j∈(i−n,i]。
考虑枚举 i∈[n,2n)i\in[n,2n)i∈[n,2n)算出 [i]tmin[i]t_{\min}[i]tmin 整体取 min\minmin 才是最终答案每个 iii 的计算都要 nlognn\log nnlogn。
令 aiTi−ia_iT_i-iaiTi−i则 ansminn≤i2n{maxi−nj≤i{aj}i}ans\min_{n\le i 2n}\big\{\max_{i-nj\le i}\{a_j\}i\big\}ansminn≤i2n{maxi−nj≤i{aj}i}。
用 iii 替换 in−1in-1in−1有 ansmin1≤i≤n{maxi≤j≤in−1{aj}i}n−1ans\min_{1\le i\le n}\big\{\max_{i\le j\le in-1}\{a_j\}i\big\}n-1ansmin1≤i≤n{maxi≤j≤in−1{aj}i}n−1。
因为 aiTi−iainTi−(in)a_iT_i-ia_{in}T_{i}-(in)aiTi−iainTi−(in)所以稍微扩大 jjj 范围对答案无影响。
即 ansmin1≤i≤n{maxi≤j≤2n{aj}i}n−1ans\min_{1\le i\le n}\big\{\max_{i\le j\le 2n}\{a_j\}i\big\}n-1ansmin1≤i≤n{maxi≤j≤2n{aj}i}n−1。
对 iii 处理一个后缀最大值就能得到答案到此也只是扔了个 logloglog 并没起到多大优化O(nm)O(nm)O(nm) 仍无法接受。
iii 不行转过来考虑 jjj考虑每个 jjj 的答案是怎样的。特别地a0infa_0infa0inf 如果 jjj 是后缀最大值点。 对于 jjj往前找到第一个 akaja_ka_jakaj 的 kkki∈(k,n]i\in(k,n]i∈(k,n] 都是 jjj 处取 max\maxmax当 ik1ik1ik1 时才满足外层的 min\minmin 操作因此 jjj 的贡献应为 ajk1a_jk1ajk1。 由 iii 的限制可以反推得到 knknkn。 如果 jjj 不是那答案仍是后面某个点产生的。 最后就是这些 jjj 贡献取 min\minmin。
基于这样的分类发现可以从后往前维护 aja_jaj 的一个单调递增栈。
假设单调栈内的元素为 s00s1...sxs_00s_1...s_xs00s1...sx。
ansmin1≤i≤x{asisi−11}n−1min1≤i≤x{asisi−1}nans\min_{1\le i\le x}\big\{a_{s_i}s_{i-1}1\big\}n-1\min_{1\le i\le x}\big\{a_{s_i}s_{i-1}\big\}nansmin1≤i≤x{asisi−11}n−1min1≤i≤x{asisi−1}n要求 si−1ns_{i-1}nsi−1n。
用线段树来维护单调栈楼房重建具体合并两个区间单调栈。
右子树答案直接拿。用右子树最大值在做子树内找到最靠近右子树的第一个比其大的位置返回。对该位置前面的取整体最小值。
最优位置 jjj 要满足 sj−1ns_{j-1}nsj−1n 所以要记录这个询问的结果位置。
但最终答案实际上就是 i∈(n,2n]i\in(n,2n]i∈(n,2n] 的最大值在 [1,n][1,n][1,n] 里面二分找 jjj 执行上述流程中得到的。
看似是维护 ai(1≤i≤2n)a_i(1\le i\le 2n)ai(1≤i≤2n) 的最大值事实上 i∈[n,2n)i\in[n,2n)i∈[n,2n) 的最大值 aiTi−ia_iT_i-iaiTi−i就等于 i−n∈[1,n)i-n\in[1,n)i−n∈[1,n) 的最大值 ai−nTi−n−(i−n)Ti−ina_{i-n}T_{i-n}-(i-n)T_i-inai−nTi−n−(i−n)Ti−in 减去 nnn。
所以线段树只需要维护 [1,n][1,n][1,n] 的最大值信息即可再在 [1,n][1,n][1,n] 里面查。
时间复杂度 O((nQ)logn2)O((nQ)\log n^2)O((nQ)logn2)。
code
#include bits/stdc.h
using namespace std;
#define inf 0x7f7f7f7f
#define maxn 100005
int n, m, p;
int t[maxn], Max[maxn 2], Ans[maxn 2];#define lson now 1
#define rson now 1 | 1
#define mid (l r 1)int query( int now, int l, int r, int x ) {if( l r ) return Max[now] x ? x l : inf;if( Max[rson] x ) return query( lson, l, mid, x );else return min( Ans[now], query( rson, mid 1, r, x ) );
}void pushup( int now, int l, int r ) {Max[now] max( Max[lson], Max[rson] );Ans[now] query( lson, l, mid, Max[rson] );
}void build( int now, int l, int r ) {if( l r ) { Max[now] t[l] - l; return; }build( lson, l, mid );build( rson, mid 1, r );pushup( now, l, r );
}void modify( int now, int l, int r, int pos ) {if( l r ) { Max[now] t[pos] - pos; return; }if( pos mid ) modify( lson, l, mid, pos );else modify( rson, mid 1, r, pos );pushup( now, l, r );
}int main() {scanf( %d %d %d, n, m, p );for( int i 1;i n;i ) scanf( %d, t[i] );build( 1, 1, n );int ans query( 1, 1, n, Max[1] - n ) n;printf( %d\n, ans );while( m -- ) {int x, y;scanf( %d %d, x, y );if( p ) x ^ ans, y ^ ans;t[x] y, modify( 1, 1, n, x );ans query( 1, 1, n, Max[1] - n ) n;printf( %d\n, ans );}return 0;
}
