宝山网站建设哪家好,做网站最下面写什么,宣传片报价单明细,免费签名logo设计多重映射
典题#xff0c;多次整体修改#xff0c;把所有的 a i x a_ix aix 改成 a i y a_iy aiy 。时间逆序。
圆
朴素区间 DP 时间是 O ( n 3 ) O(n^3) O(n3) 的#xff0c;考虑如何枚举以达到优化。
优化思路类似于【智乃想考一道完全背包】。
外向树
较好…多重映射
典题多次整体修改把所有的 a i x a_ix aix 改成 a i y a_iy aiy 。时间逆序。
圆
朴素区间 DP 时间是 O ( n 3 ) O(n^3) O(n3) 的考虑如何枚举以达到优化。
优化思路类似于【智乃想考一道完全背包】。
外向树
较好的题。易得结论每次将 [ q l , q r ] [ql, qr] [ql,qr] 规定为特殊点问 [ q l , q r ] [ql, qr] [ql,qr] 中有多少个点的子树里没有特殊点。
分为两个子问题
求得每个点 i i i 的子树内大于 i i i 的最小编号和小于 i i i 的最大编号组成区间 s i s_i si。问 [ q l , q r ] [ql, qr] [ql,qr] 内有多少个 i ∈ [ q l , q r ] i\in[ql, qr] i∈[ql,qr] 满足 [ q l , q r ] ⊂ s i [ql, qr]\subset s_i [ql,qr]⊂si 。
对于一不完全
启发式合并 O ( n log 2 n ) O(n\log^2 n) O(nlog2n) 。dfs 序上主席树区间查询 O ( n log n ) O(n\log n) O(nlogn) 。max 线段树单点修改区间查询。从小到大枚举编号 i i i 使得前缀 [ 1 , i ) [1, i) [1,i) 的点在dfs序上添加到线段树内并区间查询最大值。时间复杂度 O ( n log n ) O(n\log n) O(nlogn) 。
对于二不完全
对每个查询区间问有多少个节点区间满足 u l ≤ q l ≤ u ≤ q r ≤ u r ul\leq ql\leq u\leq qr\leq ur ul≤ql≤u≤qr≤ur
cdq 分治转化为离线三维偏序问题时间复杂度 O ( n log 2 n ) O(n\log^2 n) O(nlog2n)容斥等于 ∣ u l ≤ q l ≤ q r ≤ u r ∣ − ∣ u l ≤ u ≤ q l ∣ − ∣ q r ≤ u ≤ u r ∣ |ul\leq ql \leq qr\leq ur|-|ul\leq u\leq ql|-|qr\leq u\leq ur| ∣ul≤ql≤qr≤ur∣−∣ul≤u≤ql∣−∣qr≤u≤ur∣ 二维数点二位偏序解决时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
13解法
AC代码https://ac.nowcoder.com/acm/contest/view-submission?submissionId68612445
小红的元素交换
不考虑元素限制相当于置换环上的交换。对于一个环 l l l 选择两个点进行交换等价于数组上对应位置的元素交换则拆分为两个环 l 1 , l 2 ( l 1 l 2 l ) l1, l2(l1l2l) l1,l2(l1l2l) 。环长和不变但是环数变多。
对于此题相当于只能 01 元素才能交换。对于 01 环可以单独解决对于 0 环和 1 环可以配对解决。
AC代码https://ac.nowcoder.com/acm/contest/view-submission?submissionId68610245
小红的数组操作
此题关键是末端铺平并利用 栈大小每次最多增大 1 来保证时间复杂度的线性。
题解kjhhjki的博客
AC代码https://ac.nowcoder.com/acm/contest/view-submission?submissionId68618210
小苯的逆序对
这题的 trick 也比较典型容斥原理求最大公约数为 k 的数对个数
大致思路就是定义 b i b_i bi 表示 i i i 的倍数对于 i i i 的倍数两两配对进行 g c d gcd gcd 运算的结果一定还是 i i i 的倍数。定义 f i f_i fi 表示 g c d ( a x , a y ) i gcd(a_x, a_y)i gcd(ax,ay)i 的对数可以知道 ∑ k 1 i × k ≤ n f k × i C b i 2 \sum_{k1}^{i\times k \leq n} f_{k\times i}C_{b_i}^2 ∑k1i×k≤nfk×iCbi2 。容斥一下即可。
类似的题目D. Counting Rhyme
小苯的逆序对
AC代码https://ac.nowcoder.com/acm/contest/view-submission?submissionId68619463
