比赛的时候一直念叨链表怎么加速，比完赛吃饭路上突然想到倍增- -
/*
HDU 6107 - Typesetting [ 尺取法, 倍增 ] | 2017 Multi-University Training Contest 6
题意：
文章包含N个字符串和 1 个图片
字符串之间要求空 1 格
告诉你纸张宽度 W 固定，图片的左右留白宽度 dw, W-pw-dw 固定
每次询问给定图片的高h和首行x
问 字符串加图片总共占多少行
分析：
nxt[W][i] = j 代表 行宽为 W 时第 i 个字符串为某行行首时，下一行首个字符串 j
预处理 nxt[W], nxt[dw], nxt[W-pw-dw] 三个跳转数组
对于 x 行第一个字符串是什么，可以预处理 head[x] = j
然后用 nxt[dw] + nxt[W-pw-dw] 一直跳到第x+h行，这部分用倍增优化
对于包括第 p 个字符串的之后的总行数，可以预处理 tail[p] = tail[nxt[p]]+1
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int nxt[N], nxt2[N], nxt3[N];
int s[N];
int tail[N], head[N], Maxt;
int t, n, w, q;
int pw, dw;
void init(int nxt[], int w)
{
int i = 1, j = 1, sum = 0;
while (i <= n && j <= n)
{
while (j <= i && sum+s[i]+1 > w+1)
{
nxt[j] = i;
sum -= s[j]+1;
j++;
}
sum += s[i]+1;
i++;
}
}
int fnxt[N][15];
int two[15];
void init2()
{
tail[0] = head[0] = 0;
for (int i = n; i >= 1; i--)
{
if (nxt[i] == 0) tail[i] = 1;
else tail[i] = tail[nxt[i]]+1;
}
for (int i = 1, j = 1; i; i = nxt[i], j++)
{
head[j] = i;
Maxt = j;
}
for (int i = 1; i <= n; i++) nxt2[i] = nxt3[nxt2[i]];
for (int i = n; i >= 1; i--)
fnxt[i][0] = nxt2[i];
for (int j = 1; j <= 14; j++)
for (int i = 1; i <= n; i++)
fnxt[i][j] = fnxt[fnxt[i][j-1]][j-1];
}
int x, h;
int solve()
{
int p = head[x];
for (int i = 14; i >= 0; i--)
if (h&two[i])
p = fnxt[p][i];
return x+h-1+tail[p];
}
int main()
{
two[0] = 1;
for (int i = 1; i <= 14; i++) two[i] = two[i-1] * 2;
scanf("%d", &t);
while (t--)
{
memset(nxt, 0, sizeof(nxt));
memset(nxt2, 0, sizeof(nxt2));
memset(nxt3, 0, sizeof(nxt3));
scanf("%d%d%d%d", &n, &w, &pw, &dw);
for (int i = 1; i <= n; i++) scanf("%d", &s[i]);
init(nxt, w);
init(nxt2, dw);
init(nxt3, w-pw-dw);
init2();
scanf("%d", &q);
while (q--)
{
scanf("%d%d", &x, &h);
if (x > Maxt) printf("%d
", Maxt + h);
else printf("%d
", solve());
}
}
}