这一类题还有一个重点就是
数据结构 倒序考虑会存在某种关系的思虑 十分重要
铭记这种思路
题意：
n个人每个人有一个id还有一个numI ，开始从第k个人开始，第k个被拿出去，然后下一个被拿出去的是从第k个人往下数numI个，如果numI是正数那么就顺时针数numI个，如果是负数,就逆时针数abs（numI）个。第i个被拿出的人，得的分数，为i的因子个数。问谁的分数最高.
解答：
首先求最大分数是求反素数问题
先看什么是反素数
对于任何正整数x,起约数的个数记做g(x).例如g(1)=1,g(6)=4. 如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数. 现在给一个N,求出不超过N的最大的反素数.
然后求第I个人是谁
如果模拟是 n^2的时间复杂度。但是用线段数做可以降低到 nlogn
已知当前轮的所有人的新编号，怎么知道下一个被拿走的人的编号呢？
看约瑟夫环问题怎么进行更新
现在n中第k个人被杀死，他逆时针的第m个人（下个被杀死的），那个人在剩余的n-1个人中是第(（k-m2-1）%（n-1）+(n-1))%(n-1)+1个,他顺时针第m2个人（下一个被杀死）在那个人是剩余的n-1个人中是第(（k+m2-2）%（n-1）+(n-1))%(n-1)+1 （规则人从1到n编号，被杀死后，依然是按照原来的顺序从1到n-1编号）
先看线段数结构
struct tnode { int l,r,sum; int mid(){return (l+r)/2;} }
sum是这一段上还剩多少人。
所以在查找的时候我们相当于是二分查找剩下的第 i 个人是原来最开始的第 几号。并且更新把这个人剔除后的sum值。
见下面
int find(int nod,int m) { tree[nod].sum--; if(tree[nod].l==tree[nod].r) return tree[nod].l; if(tree[L(nod)].sum>=m) return find( L(nod),m ); if(tree[L(nod)].sum<m) return find(R(nod),m-tree[L(nod)].sum); }
这样就可以找到 这一轮谁被剔除。
这个方法很巧妙。
poj 2828也是这一类问题的拓展
题意
N 个人排队，
4 （4个人排队）
0 77
1 51
1 33
2 69 表示 名字叫77那个人插到第0位，名字为51那个人插到第1位，名字为33那个人插到第1位，名字为69那个人插到第2位，最后排队序列77 33 69 51。求这个最后排队序列。
主要是考虑倒序关系，然后用线段树预留位置。预留位置线段树操作跟约瑟夫十分类似
