https://www.luogu.org/problemnew/show/P1896 题意：求在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。其中 1<=N<=9, 0<=K<=N∗N 1 <= N <= 9 , 0 <= K <= N ∗ N 1 <=N <=9,\ 0 <= K <=

0~3操作都是很裸的线段树操作，主要是这个4操作有点复杂。 定义一下数组的含义： l0/1：从左端点开始连续的0/1的个数 r0/1：从右端点开始连续的0/1的个数 m0/1：连续的最长的0/1串 sum：1的个数 在update操作的时候，l和r数组的更新都可以直接由孩子得到，但要注意一类情况：比如左孩子全部是1，那么就可以把右孩子左端的1连起来。m数组由两种情况得到，一种是孩子的m

做两次三分，第一次三分第一条线段上走出去的点，第二次三分第二条线段上到达的点。 证明这里就不写了，一堆三角函数。。。。反正一阶导数求出来一个过原点的二次函数，一开始是正，后来变成负，所以原函数是个凹函数（还是叫下凸函数？？） 我一开始很鸡冻啊！为啥啊？导数直接取0不就好了？对啊是直接可以求出那条斜线和两条直线的夹角的，但是还要考虑这个角度能不能取到，还要考虑两条直线本身和坐标轴的夹角·····

考虑这样转化问题：从(0,0)出发走向(n+m,n-m)，字符串中1表示向右上角斜走一格，0表示向右下角斜走一格，1的数量少于0的数量等价于碰到直线y=-1。 如果不考虑约束条件，答案就是C(n+m,n)。 对于经过y=-1这个条件，可以将(0,0)对称到(0,-2)，从(0,-2)走到(n+m,n-m)的情况就是所有从(0,0)出发走到(n+m,n-m)的情况，一共有C(n+m,m-1)中。

直接容斥即可，是的这个做法不会爆，不会爆，不会爆。。。 可以发现，在容斥不断找lcm的时候，这些数字之间的gcd很小，只需少量的几个数字就可以直接爆掉区间上限，很快就能结束（也就是说位数较多的那几个数根本不可能参与容斥），反正最后做出来是对的就行了。。。 有一个问题：输入上限是1e10，如果两个数很大，求lcm可能会导致爆long long。。。。这个时候就要用先把结果暂存在一个double变