板子题，FHQ-treap秒杀 只要将懒标记定义为翻转所有数即可 #include<bits/stdc++.h> using namespace std; using ll = long long ; const int M=2e5+10; ll cnt,x,y,z,root; struct FHQ_Treap {ll x,ls,rs,sz,lz,key;}s[M]; inline ll NewNode(ll v) { s[++cnt]=(FHQ_Treap){v,0,0,1,0,rand()}; return cnt; } inline void push_up(...

比较简单的一题，只要注意下有几种情况即可 第一种，每个组都能拥有两个或两个以上的学生 第二种，只有部分组有。 那么我们考虑到底有几个组能获得两个以上的，那不就是先分配一个给他们再分配两个。 那么假如有十个学生分配7组，我们就可以知道有3组是有两个的，但如果是10个学生分配三组，那么必然每组都两个朝上。 仔细观测我们会发现，有几组有两个朝上其实可以用一个式子表示 k=min(k,n−k)k=min(k,n-k)k=min(k,n−k) 下面是代码 #include<bits/stdc++.h> using namespace std; int main() { int n,k...

平衡树板子题，随便整个平衡树都能做。 下面是代码，用的是FHQ treap，核心是维护一个节点下所有节点的总和与个数，还有懒标记，区间加就拆开来维护中间那颗树的头节点，插入就是拆开来然后加入一个树再合并，区间查询就不用我多说了吧。 #include<bits/stdc++.h> using namespace std; using ll = long long ; const int M=2e5+10; ll cnt,x,y,z,root; struct FHQ_Treap {ll x,ls,rs,sz,lz,sum,key;}s[M]; inline ll NewNode(ll ...

前排提示，本文章内容来源于牛客进阶课程计算几何。（本人仅转述加总结，想要了解更多请点击牛客竞赛课程专栏购买） 本博客为菜鸡转述，如有错误请轻喷，大佬请点击右上角离开。 本次为题目讲解，由于是做题不是搞研究，所以那些比较难证明但是又可以感觉出来的性质，我们都是直接掏出来用的，请原谅本菜鸡，因为证明实在过分繁琐困难了，我就不证直接用了。 首先是题目链接 首先A题，还记得我们前面讲的非数NaN吗,当NaN与任何数字比较的时候，只有不等于操作返回true，所以该题需要我们凑出一个NaN，怎么整出NaN可以百度，这里我们简单的输出 0 0就可以了。 B题，是一个光线回转法的板子题，这个我们稍后再讲，顺便...

简单的模板题。利用扩展欧几里得即可求。 首先，你要知道在初等数论里，我们把a和b的最大公约数记错记作(a,b)，把b可被a整除记作a|b,把b不可被a整除记作a∤b 扩展欧几里得的证明需要用翡蜀定理 对任意的正整数a b，必然存在x y，使得ax+by=(a,b) 若b=0，那么（a,b）=a。此时定理显然成立 若（a，b）!=0,那么将ax+by=(x,y)转换成证bx+(a%b)y=(b,a%b)，由欧几里得算法得知该式最终会将b变成0，即变成第一步，得证。 当b=0的时候，我们可以看出x=1，y=0必然是个满足的解，那么我们可以通过反递推得到最终的x，y的值。 那么假设原先x，y值为...