T2
CYJian
2018-09-29 20:51:47
比赛前三天蒟蒻打了一个暴力想要看看数据强度的时候,发现正解挂了!!!
然后调了出题人一个下午终于肝出来了..
~~(蒟蒻出题人再也不出毒瘤数据结构题了..)~~
首先我们可以预处理出$1$~$10^7$所有的数能分解的质因子个数..
这个可以用欧拉线性筛筛出来..虽然这个并不是积性函数..
我们可以预处理出斐波那契数列的前$40$项..这么多已经够用了..
然后我们把第$i$项改成原来的第$i$项减去第$i-1$项..
这样子就变成了与上一个隔多少个就再取一个数了..
比如说原来的斐波那契数列是:1, 2, 3, 5, 8...
然后我们把它魔改成:1, 1, 1, 2, 3...(实际上是右移了两下..)
对于第一行来说,上面五个数就表示: 第一个要选的是上一个(没有为$0$)的后一位: $1$
第二个要选的就是上一个($1$)的后一位: $2$
第三个要选的就是上一个($2$)的后一位: $3$
第四个要选的就是上一个($3$)的后两位: $5$
第五个要选的就是上一个($5$)的后三位: $8$
...
然而还是斐波那契数列..
~~这个有个$\pi$(pi)用啊!!!~~
当然有用啊..
~~改成了这样后我们就可以搞$60$的暴力辣!!!~~
首先我们发现前10的分组是这样的:
|1| 2| 3| 4| 5| 6| 7| 8| 9| 10|...|
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
|1| 1| 1| 2| 1| 2| 2| 1| 3| 2|...|
没有发现什么吗??
然后让我们把之前的候选的东西放进去:
|数字|1| 2| 3| 4| 5| 6| 7| 8| 9| 10|...|
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
|**归属**|1|1|1|2|1|2|2|1|3|2|...|
|**第$1$行的候选**|1|1|1|2|1|3|2|1|5|4|...|
|**第$2$行的候选**|(1)-|(1)-|(1)-|1|(1)-|1|1|(1)-|2|1|...|
|**第$3$行的候选**|(1)-|(1)-|(1)-|(1)-|(1)-|(1)-|(1)-|(1)-|1|(1)-|...|
当然,这里面打'-'的表示不可能选到的..括号表示没有改变(或者说是无关的)候选..
然后一个很显然的一点: 一个数字如果属于前面的行是不可能影响到后面的行的候选的..
#### 而且从数字为10的时候我们可以看出:如果当前候选的有多个为1的(第$2$行和第$3$行),优先选择行数小的(第$2$行),并且行数大的(第$3$行)候选不改变(虽然这里貌似看不出来,但是可以自己多写写就可以看出来了)..并且不是可选行且比当前选择行(第$2$行)小的(第$1$行)候选也要减..
不信可以自己试试..~~Markdown的表格真难写..~~
然后这个就可以离线询问然后$O(NK)$模拟了..
至于正解..
我们发现这个就是一个区间最小值,区间减法,这个直接用线段树搞就好了..
附上一个小优化:如果当前$10^4$的行内候选都大于$1$(假设是$x$),那么后面$x-1$的数都肯定不是这$10^4$行内的东西..所以可以直接在枚举$N$的时候加上$x-1$,然后$1$~$10^4$区间减去$x-1$就好了..
附上丑陋而异常臃肿的代码..
```cpp
#include <bits/stdc++.h>
using namespace std;
#define reg register
#define enter putchar('\n')
#define ls (Node << 1)
#define rs ((Node << 1) | 1)
#define MAXN 5000000
#define MAXT 1000000
#define MAXK 10000
const char FI[] = "queue.in";
const char FO[] = "queue.out";
typedef short sh;
inline int Min(reg int a, reg int b) { return a < b ? a : b; }
inline int read() {
reg int s = 0, t = 1; reg char ch = getchar();
while(ch > '9' || ch < '0') t *= ch == '-' ? -1 : 1, ch = getchar();
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * t;
}
struct Node {
sh k;
int n;
int id;
}Ask[MAXT + 1];
bool operator < (Node a, Node b) {
return a.n < b.n;
}
int T;
sh s[MAXN + 1];
int res[MAXT + 1];
int fib[50] = {1, 1};
int prime[40 * MAXK];
bitset<MAXN + 1>Check;
int Id[MAXK << 5];
int pos[MAXK << 5];
int tag[MAXK << 5];
int Tree[MAXK << 5];
inline void init() {
reg int tot = 0;
for(reg int i = 2; i <= MAXN; i++) {
if(!Check[i]) prime[++tot] = i, s[i] = 1;
for(reg int j = 1; j <= tot && i * prime[j] <= MAXN; j++) {
Check[i * prime[j]] = 1, s[i * prime[j]] = s[i] + 1;
if(i % prime[j] == 0) break;
}
}
for(reg int i = 2; i < 50; i++) fib[i] = fib[i - 1] + fib[i - 2];
for(reg int i = 49; i > 1; i--) fib[i] -= fib[i - 1];
T = read();
for(reg int i = 1; i <= T; i++)
Ask[i].n = read(), Ask[i].k = read(), Ask[i].id = i;
sort(Ask + 1, Ask + T + 1);
}
inline void build(reg int Node, reg int L, reg int R) {
Tree[Node] = 1;
if(L == R) {
Id[Node] = L, pos[Node] = Node;
return ;
}
reg int mid = (L + R) >> 1;
build(ls, L, mid), build(rs, mid + 1, R);
pos[Node] = pos[ls];
}
inline void Add(reg int Node, reg int L, reg int R, reg int l, reg int r, reg int k) {
if(l <= L && R <= r) {
Tree[Node] += k, tag[Node] += k;
return ;
}
Tree[ls] += tag[Node]; tag[ls] += tag[Node];
Tree[rs] += tag[Node]; tag[rs] += tag[Node];
tag[Node] = 0;
reg int mid = (L + R) >> 1;
if(l <= mid) Add(ls, L, mid, l, r, k);
if(r > mid) Add(rs, mid + 1, R, l, r, k);
Tree[Node] = min(Tree[ls], Tree[rs]);
pos[Node] = (Tree[Node] == Tree[ls] ? pos[ls] : pos[rs]);
}
int main() {
init();
reg int M = Ask[T].n;
reg int id = 1;
reg int g[MAXK + 1];
reg int ans[MAXK + 1]; memset(ans, -1, sizeof(ans));
for(reg int i = 1; i <= 10000; i++) g[i] = 1;
build(1, 1, 10000);
for(reg int i = 1, Mi, add, ID; id <= T && i <= M; i++) {
Mi = pos[1], ID = Id[Mi];
Add(1, 1, 10000, ID, ID, 0);
add = Tree[Mi];
Add(1, 1, 10000, 1, ID, -add);
if(add > 1 && ID < 10000)
Add(1, 1, 10000, ID + 1, 10000, 1 - add);
Add(1, 1, 10000, ID, ID, fib[++g[ID]]);
while(id <= T && Ask[id].n < i + add - 1) res[Ask[id].id] = ans[Ask[id].k], id++;
i += add - 1;
if(i > M || id > T) break;
ans[ID] += s[i] + (ans[ID] < 0);
while(id <= T && Ask[id].n <= i) res[Ask[id].id] = ans[Ask[id].k], id++;
}
for(reg int i = 1; i <= T; i++) printf("%d", res[i]), enter;
return 0;
}
```