又来填坑了（大雾
#1.为什么用树状数组
做多了题目，看一眼这题就知道要用数据结构了，进一步分析就可以知道这是一道二分和树状数组的题目。（其实用变形的链表 $n\sqrt{n}$ 卡卡常也可以吧）
# 2.具体思路
首先设定 $n$ 个位置，第 $i$ 个位置为 $1$ 代表这个人还没出局，否则代表出局了。很容易发现求 $l$ 到 $r$ 中没出局的人数量就是 $l$ 到 $r$ 的和了。
这样，设当前在第 $now$ 个人，跳过 $x$ 个人后的那个人出局，就相当于找 $now$ 的后面（包括 $now$）的第 $x + 1$ 个为 $1$ 的数字。
# 3.how to do it?
确定完正确思路后，来看怎么求。
这是这道题的关键，我们需要使用 二分 算法，（我这里用的是倍增，更加好写）。
首先看要出局的人在什么位置，因为有可能跨越一个环。
如果 $now$ 到 $n$ 中没出局的人数 $\geq x$，那么答案在 $now$ 到 $n$ 中。否则，$x$ 要减去 $now$ 到 $n$ 的人数，之后就转换成了求 $1$ 到 $now-1$ 第 $x$ 个为 $1$ 的人了。（类似线段树上二分的思想）
当锁定了答案范围之后，现在来讨论如何二分。取 $mid=l+r>>1$，这里如果就按照想的二分，码量会大一点点。
我们可以转换成二分最后一个位置 $loc$，使得 $l$ 到 $loc$ 中没出局的人个数是 $x-1$，那么 $loc+1$ 一定没出局。（否则 $loc+1$ 就是最后一个了啊）我们要求的就是 $loc+1$ 了，这样二分就会简单很多了。（类似倍增求 $LCA$ 的思想）
另外，每次二分完别忘了在这个位置加上 $-1$（出局了），以及更新 $now$ 的值，这题还是环状的，需要取模还有一大堆细节请见代码。
然后就能愉快地 AC 神仙分块甲组题了。
# 4.闲话（其他做法）
其实我也口胡了一个线段树上二分的做法，但是胡完感觉有点困难，$n\log^2 n$ 能过就没写其实。
大概是这样的：这里的线段树二分不是普通的线段树二分，还需要一个备用量 $sum$。如果二分的时候走了右端点那么需要加 $sum$，其实还有一大堆的分类讨论，所以就没写。
关于变形的链表，每个位置不仅存储下一个元素的位置，还会存储下 $\sqrt{n}$ 个元素的位置，这样就可以做到 $n\sqrt{n}$，也是一个不错的解法。
代码很短，压了点行：
#include <iostream>
using namespace std;
int n, now = 1;
int a[500005], c[500005];
void add (int x, int y) {for (; x <= n; x += x & -x) c[x] += y;}
int query (int x) {return x == 0 ? 0 : c[x] + query (x - (x & -x) );}
int sum (int x, int y) {return query (y) - query (x - 1);}
int q (int x) {//求 now（包含）后面第 x 个不为 0 的。
int l = 1, r = n, res = sum (now, n);
if (res >= x) {
l = now;
r = n;
} else {
x -= res;
l = 1, r = now - 1;
}
int ret = l - 1;
for (int i = 19; i >= 0; i --)
if (ret + (1 << i) <= n && sum (l, ret + (1 << i) ) < x) ret += 1 << i;
return ret + 1;
}
int main () {
scanf ("%d", &n);
for (int i = 1; i <= n; i ++) {
scanf ("%d", &a[i]);
++ a[i];
a[i] %= (n - i + 1);
add (i, 1);
}
for (int i = 1; i <= n; i ++) {
if (a[i] == 0) a[i] += n - i + 1;
int x = q (a[i]);
printf ("%d\n", x);
add (x, -1);
now = q (a[i]);
}
return 0;
}
标签：二分,YACS,loc,int,题解,位置,出局,甲组,now From： https://www.cnblogs.com/Xy-top/p/17392216.html