ZYB有一个序列所有的逆序数前缀和，$a_1,a_2,a_3,…,a_n$，他们各个都表示从1到$i$的逆序数的前缀和。
树状数组+二分
首先我们可以倒着看，对于最后一个数字，他的逆序数减前面的逆序数就代表着前面大于他的个数。所以我们就可以把问题转化为，已知数字$a_i$在前$i$个中的位置，求$a_i是多少。
我们可以用树状数组来维护，$sum(i)$表示到$i$代表着$i$是第几个数字，每当一个数字用过之后，他后面的数字都要-1，因为他们的排序相当于减少了一个，第四个数字变成第三个数字。
+n 没有想到这个序列是单调的，所以可以二分。居然想的是怎么让整个数组往前挪。
1 |
|
BOB走在$[1,n]$的路上，每两个点中间都有一个红绿灯，每一秒钟，
$t(p,q)$就是$p$走到$q所需要的时间。
问： BOB从 $\sum^{n-1}{p=0} \sum{q=p+1}^nt(p,q)$的时间总和。
对于第$i$个单独的红绿灯我们可以证明他对答案的贡献是
$(i)(len-i+1)(t(i))$
我们对于两个灯进行分析。
01 第一个零要2s，第二个一要1s
10 第一个一要1s，第二个零要1s
00 第一个零要2s，第二个一要2s
11 第一个一要1s，第二个一要2s
综上可以发现，
我他妈sb了，不应该看着一段一段的区间，应该把红绿灯作为每一次状态的扩展，从红绿灯这$n$个出发开始计算，不应该考虑一个一个的单位为1的区间。
1 | // CSL 代码 |
1 |
|
reference:
https://blog.csdn.net/tianyizhicheng/article/details/82728350
概率dp有两种题型，一种是求概率一种是求期望。
来结合一下题目
一个人在一条线上掷骰子，在线上有类似飞行棋的可以直接到达某个点的特殊点，问从$0$到$n$掷骰子次数的数学期望是多少？
期望dp，dp最重要的就是从一个已知的最优状态转化到另一个最优状态。
为什么期望要反着求呢，因为你并不知道$dp[0]$这个点的值，因为我们定义$dp[x]$为$x$点到$n$点的掷骰子数的数学期望。而$dp[n]$的数学期望我们是知道的，是0，因为已经在$n$点了。之后我们倒推前面点的数学期望，因为你骰子是6面，从一个点可以到后面的六个点并且是等概率的，所以
$dp[i] = \sum_{j=i+1}^{i+6}dp[j]/6+1$
而且如果是特殊的飞行点，那么他的数学期望直接就是他的到的点的数学期望。
+2：没有从n-1开始，居然sb到从n开始计算。
1 |
|
跟上面的差不多，就是求期望。
跟上面基本相似。
1 |
|
1 | template <typename T> |
$n$个人围成环，每个人可以选择$[0,2^k-1]$中的一个数字，要求相邻两人不能同或为0。
递归。
可以YY出，第一个人有$2^k$种选择，之后第2到第$n-1$个人有$2^k-1$种选择，最后一个人可能可以选$2^k-2$，也可能可以选$2^k-1$。这取决于倒数第二个人是否跟第一个人选一样的。这时候我们就可以加上如果第一个人和倒数第二个人选择相同，并且，最后一个人多选了那$2^k-1-(2^k-2)$种，那么他们三个点变成一个点来选择了。
1 |
|
两个人玩游戏，给出$[0,3]$个选项和一个$m$初始值，两个人依次选择，有以下三种选择
两个人一个想将值变大，一个想让值变小，两个人都知晓所有情况和选项，在最优情况下，问谁赢。
博弈论dp+记忆化搜索
因为数据量很小，范围也在200之间，所以记忆化状态回复的很多。
$dp[pos][val]$表示在pos位置数值是val,之后dp代表的是最优可以赢还是输还是平，分别用2,1,0代表。
之后对于边界值要处理一下。数组存不了负值，我们统一加100处理。
妈的。我看到这个以为是纯博弈论直接人傻了。之后想着能不能记忆化搜索，但是看到$n=1000$还以为他喵的会爆，但是这道题的情况限制在范围$-100到100$，所以情况很少。所以可以直接记忆化，不过对于答案的选择和状态转移我可能还是不会太轻松地做出来，带int的dfs我还是不怎么熟悉，这按道理应该是算是博弈论dp了。从最优状态转移到最优状态。
1 |
|
在一条线上有二种操作
求某一个点和与之相连点的个数。
线段树设左右标志或者是树状数组二分
HDOJ可以线段树+二分。
Cnm hdoj 多组数据不给提示
如果是树状数组500ms，线段树+二分1500ms。
POJ卡了线段树+二分。HDOJ没有写多组输入害得我WA成sb了。
垃圾HDOJ还造假数据，毁坏多个碉堡。也是服了。
1 |
|
1 |
|
Alice去一排$n$的花盆中种花，有两种操作
询问
线段树，$sum$表示花的个数，用$lazy$来懒惰标记。
妈的，我线段树还是不够熟悉，居然使用了$update(p,n,1)$这样子的形式，以为每个区间的$rt$都是随机的，其实线段树的区间都是固定的，你只能通过$lson,rson$来寻找每一个区间，不能自己xjb改区间。
寻找p开始位置的时候，需要思考一下。image一下中点和左端与p的关系就好了。
1 |
|
作为一名acm选手，不能连线段树都不会，练就完事了。而且我越发觉得在赛场上不能卡机，中档题才是区分牌子的题目。只有慢慢思索的题目才能真正地提高自己，立下一个flag，每十天完成一个kuangbin专题。现在时间9/6。必须在9/16完成这个线段树专题，就算是困死也得完成。
左右区间还是注意一下，保不准出题人恶趣味。
初始化不能想当然$n$多大树多大，有可能他是一个范围，$n$只是代表着式子的个数罢了。
数组居然还是又一次忘记开4倍。
lazy数组忘记初始化，或者lazy可以为0但是还是初始化为0了。
这如果我没有记错，应该是人生中第一个线段树题目，很是经典。单点修改，区间查询。
线段树。
1 |
|
单点修改，区间最值。
线段树。
1 |
|
区间查询，区间修改。
线段树
lazy需也要开两倍
1 |
|
贴线段，每次贴都会覆盖掉前面的线。问贴到最后能看到多少种不同的线。
线段树+离散化
覆盖线段的范围是1e8，无法建树所以需要离散化，把线段长度按照排序的顺序重新赋值。由于有$2n$个长度所以记得$maxn$要开两倍。
区间修改，单点查询。
1 |
|
区间修改，区间查询
线段树
1 |
|
在一条线上区间涂颜色。
问所有颜色出现的区间块的数量。
线段树+懒惰标记
需要注意的是，$n$不代表着数据的范围，8000才是数据的范围，并且由于区块间有空隙，所以离散化还有点不好做。虽然数据也只有8000。注意的是初始化的范围要覆盖到8000，不能以为到$n$就好了。
+5 $n$当坐范围
+3 误以为build函数能够初始化所有的点，但其实是要memset(vis,-1,sizeof(vis));
1 |
|
求区间最大值和最小值的差
可以用ST表预处理，也可以用树状数组或者是线段树，线段树的常数比较大，但他们的复杂度均是$O(nlogn)$
1 |
|
区间数字根号，区间查询数字和。
线段树＋智力门槛
因为所有数字最多根号8次就会变成1。所以我们只需要处理一下当数字为1就不用再更新区间内的数了。
acm还是靠智力和眼力啊，我想了半天都没想出来什么数学方法，原来只需要看出规律和找到最关键的突破点就ok了。
+1超时忘记开4倍数组了。。
+1 虚伪的看到了提醒要注意l,r的大小关系，妈的，这都卡，是不是人啊。
1 |
|
1 |
|
dfs序+线段树模板题
同上
+1 lazy数组没有初始化，没适应无build建树
1 | #include<bits/stdc++.h> |
有四种操作。
线段树
对于线段树的懒惰标记和取模运算细节要求很高。
相信对于sum数组的转化大家都能够推得出来，但是关于pushdown的操作是另有玄机。
首先他的顺序很重要。得先将lazy[1]递推下去，也就是操作3把数字变成$val$，之后再进行乘法和加法的操作。对于乘法很重要的一点是你在lazy[2]标记递推的时候，其实你把子树中的加法也相当于乘了$val$，所以递推不仅要递推乘法标记，还要递推加法标记。
+3 更新Pushdown中你也要更新lazy数组的值
+1 更新的次序也有关系
+1初始化 有的要1.
+1 少写一个|1 rt[rt<<1|1]写成了rt<<1
+10000 有一个r-l+1写错了，下次写成 len 。不然很容易出错妈了个鸡
1 |
|
做过 在我之前博客里面有。
做过
+2 忘记掉可能初始不能放在A点，所以要加入一个全局变量flag，初始化maxl。
1 |
|
对每一次查询寻找$val$长度的最前面空闲时间并占据他。
线段树的区间合并。
这里由于要维护两个线段树，所以用结构体来构造树，不过确实使用结构体封装之后复用性高了很多。
这样就可以更新了。
一棵树代表屌丝+女神占有的，一棵树代表女神占有的。
查询分为三种方向
+1 区间合并中 更新父节点必须每个都更新，所以有时候你在return 之前也要更新一下。
1 |
|
求多个矩形周长的并
扫描线+线段树
这道题目没有离散化$X$坐标就可以做。而且例子也只有一个。。
1 |
|