分块太暴力惹... 没做出来。看了题解qaq 分析： 两头$\sqrt{n}$暴力维护 预处理ans[i][j],sum[i][j] sum[i][j]是一个前缀和，前i块值为j的数量 ans[i][j]表示第i块到第j块的答案总和 询问的时候先做两头，最后把ans[][]加上去就好了！ 主要难点在预处理和卡常 1 #pragma GCC optimize(3) 2 #pragma GCC optimize(2) 3 #pragma GCC optimize("Ofast") 4 #include<bits/stdc++.h> ...

原来左偏树还可以打tag，get了 和线段树打tag一样，时不时Push_Down就好了 然后这里显然也是要先乘法后加法的 tag打上了之后还是其他一般左偏树差不多，有些细节注意一下 然后开 long long!!!   1 #include<bits/stdc++.h> 2 #define int long long 3 #define writeln(x) write(x),puts("") 4 #define writep(x) write(x),putchar(' ') 5 using namespace std; ...

题意可真的是有毒 第一眼树形背包可做？（反正我没用树形背包打过，边上巨佬打的背包似乎没拿分） 后来发现可以贪心搞，我们先把一个节点所有的儿子都取进去，之后不行的话再从大的开始拿走就好了 问题就变成了了如何快速维护各个节点子树中的最大值，优先队列就好了！ 关键是还要资瓷合并，pb_ds库就好了，手打左偏树就好了 有人说这是裸题...但我真的看了好久...肯定是我tcl 1 #include<bits/stdc++.h> 2 #define int long long 3 #define writeln(x) write(x),puts("&quot...

多...多组数据... awsl 死命的MLE，原来是忘记清空数组了.... 左偏树模板？ 对于每一个操作，我们把两个节点$x,y$的祖先$fx,fy$找到，然后把他们的左右儿子分别合并 最后把$v[fx],v[fy]$分别>>1再合并回去就好了 1 // luogu-judger-enable-o2 2 #include<bits/stdc++.h> 3 #define writeln(x) write(x),puts("") 4 #define writep(x) write(x),putchar(' ') 5 ...

CDQ分治，归并排序写错调了一天可海星 考虑哈夫曼距离特点： $$dis(A,B)=|A_x-B_x|+|A_y-B_y|$$ 若能够把绝对值去掉岂不是很妙！ $$dis(A,B)=(A_x+A_y)-(B_x+B_y)$$ 由于A坐标已经定下来了，我们只要找B坐标使得$B_x+B_y$ 最大，就可以是距离最小了！ 然后套上CDQ三维偏序求解就好了 因为不一定每个点都在当前询问点的左下方（也就是说绝对值不能直接去掉，我们把所有点转个方向再做3遍就吼了）   Tip:这道题卡常，请使用归并排序，并且求解区间最值时不要使用线段树，改用树状数组！！ （虽然某人说正常人用的都是树状...

    夹缝 问题描述： 二维空间内有两面相对放置的，向无限远延伸的镜子，以镜子的方向及其法向量建立坐标系，我们选定一个法向量方向下面称“上”。在镜子上的整数位置，存在着一些传感器，传感器不影响光线的反射，光线仍旧满足反射定律（即入射角等于出射角）。你可以在两面镜子上各选定一个整数位置的点 A 与 B，并从其中一个点向另一个射出一条光线，我们希望接收到光线的传感器数量尽可能的多。   考试打了暴力+随机骗分。然而还没有一些巨佬直接小范围暴力求答案取max来的分高... 首先是结论：①假设步长为k，那么步长为(2t+1)k的时候覆盖的点是没有直接K来的优秀的，简单易证...

呀呀呀，临走10分钟刷一道水题 然而只是记一下第一次hash被卡 各种模数都被卡了... 本来想打双哈希了，后来皮了一下，模数改成了998244353，然后竟然A掉了   正着hash一遍，反着hash一遍 对于一个串都取正反hash值的min值，若其相同，则必然是相同串（不被卡的话） 计数用set就好了 1 #include<bits/stdc++.h> 2 #define ull unsigned long long 3 using namespace std; 4 inline int read(){ 5 int ans=0,f=1;c...