文件名称：线段树例题之——sort.cpp
文件大小：4KB
文件格式：CPP
更新时间：2024-04-06 17:46:42
算法
T1 本题极其无聊，3T强行捏成1T，差最大 显然是 前一半后一半，差最小显然是间隔着放，方案数显然是卡特兰数列 关于卡特兰数列，直接放公式了h(n)=C(2n,n)/(n+1) (n=0,1,2,...) or h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...) 也就是2n 个数0 1，保证在任何位置都有：之前的1的个数<= 0的个数 之类的问题 维护： 1.求和数组，每次右半边的和 - 左半边的和 2.奇正偶负数组，每次询问时判断L是奇是偶在考虑正负 3.组合数