wordpress博客建站教程,进入公众号闪退怎么回事,网站谁做的比较好,做二手房怎找房源网站Description
有 n n n 架无人机参与比赛#xff0c;第 i i i 架无人机飞过一个单位距离需 t i t_i ti 秒。
赛道为一条直线#xff0c;上面有 m m m 个存档点#xff0c;第 i i i 个存档点距起点 s i s_i si 个单位长度#xff0c;保证 s i 1 s i s_{i1…Description
有 n n n 架无人机参与比赛第 i i i 架无人机飞过一个单位距离需 t i t_i ti 秒。
赛道为一条直线上面有 m m m 个存档点第 i i i 个存档点距起点 s i s_i si 个单位长度保证 s i 1 s i s_{i1}s_i si1si。
一共有 n n n 场比赛第 k k k 场比赛有前 k k k 架无人机参加比赛按如下方式进行。
定义一个阶段为当前还未完赛的所有无人机从其存档点开始飞行直到有一架无人机到达了下一个存档点我们称这架无人机为此阶段的赢家。若有多架无人机同时到达则编号最小的为赢家。
该阶段结束后所有非赢家的无人机将被传送回此阶段开始时其所在的存档点而赢家则更新其存档点。若赢家此时到达了第 m m m 个存档点那么它将完赛后面的阶段都不参加。
当所有无人机都完赛时那么这场比赛就结束了。
你需要对于这 n n n 场比赛中的每一场分别求出比赛中所有无人机的传送次数之和。
Solution
依题意得一个阶段中只有赢家改变存档点对非赢家造成传送而非赢家之间的相对位置都不改变不会互相造成传送。
于是总传送次数可以拆成两两之间所造成的贡献之和并且这只与它们两有多少个阶段输赢不同有关即对于 i , j i,j i,j两机互相造成的贡献为 i , j i,j i,j 中第一架无人机完赛时已经经过了多少个阶段。
对于一架无人机 i i i我们定义 w j ( s j − s j − 1 ) × t i w_j(s_j-s_{j-1})\times t_i wj(sj−sj−1)×ti。
那么对于 i , j i,j i,j 算贡献可以通过归并 i , j i,j i,j 的两个 w w w 序列来求出。然而 w w w 并不有序但我们可以通过 UR #26 石子合并 中的结论即对于同一序列的 w w w若 w i 1 ≤ w i w_{i1}\le w_i wi1≤wi 那么 w i 1 w_{i1} wi1 会在 w i w_i wi 弹出后紧接地弹出在归并后的数组中相邻。
而同一组中的 w w w 大小关系与 t t t 无关与 s s s 的差分数组有关所以可以对 s s s 的差分数组进行操作将会紧邻弹出的数合在一起设其总共有 k k k 个这样的段。每个段计 a i , b i a_i,b_i ai,bi表示这一段段头的值以及这一段的长度。
因为 a i a_i ai 是严格递增的那么由于 a 1 a 2 ⋯ a k s m ≤ 1.5 × 1 0 5 a_1a_2\cdotsa_ks_m\le1.5\times10^5 a1a2⋯aksm≤1.5×105所以 k k k 的大小是 O ( V ) O(\sqrt{V}) O(V ) 的 V V V 是 1.5 × 1 0 5 1.5\times10^5 1.5×105 级别的。
回到对 i , j ( i j ) i,j(ij) i,j(ij) 算贡献发现比较好算了 t i ≤ t j t_i\le t_j ti≤tj那么 i i i 先完赛先加上 m m m 的贡献即 i i i 对 j j j 造成的贡献。 j j j 对 i i i 造成的贡献就是看在 i i i 完赛时 j j j 到了第几个存档点也就是找到最大的 x x x 使得 a k × t i a x × t j a_k\times t_ia_x\times t_j ak×tiax×tj然后加上 b 1 b 2 ⋯ b x b_1b_2\cdotsb_x b1b2⋯bx 的贡献。 t i t j t_it_j titj那么 j j j 先完赛同样先加上 m m m 的贡献。然后找到最大的 x x x 使得 a x × t i ≤ a k × t j a_x\times t_i\le a_k\times t_j ax×ti≤ak×tj同样加上 b 1 ⋯ b x b_1\cdots b_x b1⋯bx 的贡献注意是 小于等于因为 i j ij ij所以当两人用时相等时赢家是 i i i。
找 x x x 用二分那么至此我们用 O ( n 2 log V ) O(n^2\log\sqrt{V}) O(n2logV ) 的复杂度解决了问题比暴力分多 10 10 10 分可喜可贺。
那么怎么继续优化呢
考虑上扫描线我们从小到大扫 i i i对于每一个可能的 x x x先二分找到 j j j 的限制两种情况再对这两段区间加上 b x b_x bx注意我们已经把贡献分成了 m m m 和 b 1 ⋯ b x b_1\cdotsb_x b1⋯bx。
计算答案就是扫到 j j j 时取出其在线段树内的值然后加上 j × ( j − 1 ) 2 × m \dfrac{j\times(j-1)}{2}\times m 2j×(j−1)×m 的贡献。
注意线段树上维护的是 离散后的 t t t 的值二分也是找离散后的值同时要 先算贡献再查值不然若 t i t j t_it_j titj 时会重复算贡献。
现在时间复杂度变为了 O ( n V ( log n log n ) ) O(n\sqrt{V}(\log n\log n)) O(nV (lognlogn))前面的 log \log log 是二分后面的 log \log log 是区间修改单点查询的线段树。但这个复杂度跑不过去需要进一步优化。
注意到区间修改有 O ( n V ) O(n\sqrt{V}) O(nV ) 级别而询问只有 O ( n ) O(n) O(n) 级别那么可以用区间修改 O ( 1 ) O(1) O(1)单点查询 O ( n ) O(\sqrt{n}) O(n ) 的分块来平衡复杂度具体的维护每个点和每个块的差分数组修改时修改两个点和两个块的值查询即查询差分数组的前缀和。
但二分的 O ( log n ) O(\log n) O(logn) 还没去掉观察到当 x x x 相同时 i i i 递增时其对应 j j j 的限制也递增 i , j i,j i,j 是离散后 t t t 数组的下标。那么可以预处理出 t a g i , x tag_{i,x} tagi,x表示二分出来的限制用双指针维护做到时间 O ( n V ) O(n\sqrt{V}) O(nV )空间 O ( n V ) O(n\sqrt{V}) O(nV )。注意两种限制的双指针有所不同细节较多。
这个题就用时间 O ( n ( V n ) ) O(n(\sqrt{V}\sqrt{n})) O(n(V n ))空间 O ( n V ) O(n\sqrt{V}) O(nV ) 的复杂度做完了吗
实际上 k k k 的极限并不是 1.5 × 1 0 5 \sqrt{1.5\times10^5} 1.5×105 而是 550 550 550 。所以开两个 t a g tag tag 会爆空间不过只要先处理一种算贡献再处理另外一种算贡献就可以了。
时间上有略微卡常只需在求 t a g tag tag 时使访问较为连续即可先枚 i i i再枚 x x x。
还有一些细节具体见代码。
Code
#includebits/stdc.h
using namespace std;
#define ll long long
int n,m,k,cnt,len;
int t[150010],s[150010],tt[150010],id[150010];
int tag[150010][560];
int st[150010],hd;
int a[560],b[560];
ll fin1[150010],fin2[560],ans[150010];
void init(){cinnm;for(int i1;in;i){cint[i],tt[i]t[i];}sort(tt1,tt1n);cntunique(tt1,tt1n)-tt-1;lensqrt(cnt)1;for(int i1;in;i){t[i]lower_bound(tt1,tt1cnt,t[i])-tt;}for(int i1;icnt1;i){id[i](i-1)/len1;}for(int i1;im;i){cins[i];}for(int im;i;i--){while(hds[st[hd]]-s[st[hd]-1]s[i]-s[i-1]) hd--;st[hd]i;}st[0]m1;for(int ihd;i;i--){a[k]s[st[i]]-s[st[i]-1];b[k]st[i-1]-st[i];}
}
void update(int l,int r,ll v){ //O(1)更新fin1[l]v,fin1[r1]-v;fin2[id[l]]v,fin2[id[r1]]-v;
}
ll query(int x){ //O(sqrt(n)) 查询ll sum0;for(int i1;iid[x];i){sumfin2[i];}for(int i(id[x]-1)*len1;ix;i){sumfin1[i];}return sum;
}
void pres1(){ //titjfor(int j1;jcnt;j){for(int i1;ik;i){int fltag[j-1][i];while(1){tag[j][i]fl;if(fl1cnt||(ll)tt[j]*a[k](ll)tt[fl1]*a[i]) break;fl;}}}
}
void pres2(){ //titj两个双指针细节多一定要理解充分for(int j1;jcnt;j){for(int i1;ik;i){int fltag[j-1][i];while(1){if((ll)tt[j]*a[i](ll)a[k]*tt[fl]){tag[j][i]fl;break;}fl;}}}
}
void solve(){pres1();for(int i1;in;i){ans[i]query(t[i]);for(int j1;jk;j){if(tag[t[i]][j]t[i]){update(t[i],tag[t[i]][j],b[j]);}}}pres2();for(int i1;icnt;i) fin1[i]0; //记得清空分块for(int i1;iid[cnt1];i) fin2[i]0;for(int i1;in;i){ans[i]ans[i-1]query(t[i]);coutans[i](ll)i*(i-1)/2*m\n;for(int j1;jk;j){if(tag[t[i]][j]t[i]){update(tag[t[i]][j],t[i]-1,b[j]);}}}
}
int main(){ios::sync_with_stdio(0);cin.tie(nullptr);init();solve();return 0;
}
