用线段树来表示，每个区间节点存储当期区间剩余的最大长度，每次“贴告示”的时候找到区间中最左的且剩余长度大于告示长度的叶节点，将其剩余长度减去告示长度并更新树。
#includeusing namespace std;struct lineNode;typedef lineNode lineTree;struct lineNode{ int left, right; int val; lineNode(int l=0, int r=0, int val=0) :left(l), right(r), val(val) {}}nodeArr[800020];void build(int pos, int l, int r, int val){ nodeArr[pos] = lineNode(l, r, val); if (l != r) { build(pos * 2, l, (l + r) / 2, val); build(pos * 2 + 1, (l + r) / 2 + 1, r, val); }}void UpdateVal(int node){ int fatherNode = node / 2; if (fatherNode == 0) { return; } int lVal = nodeArr[fatherNode * 2].val; int rVal = nodeArr[fatherNode * 2 + 1].val; nodeArr[fatherNode].val = lVal > rVal ? lVal : rVal; UpdateVal(fatherNode);}void UpdateNode(int node, int val){ nodeArr[node].val = val; UpdateVal(node);}int findMaxValNode(int tree, int val){ if (nodeArr[tree].left == nodeArr[tree].right) { UpdateNode(tree, nodeArr[tree].val - val); return tree; } if (val <= nodeArr[2 * tree].val) { return findMaxValNode(2 * tree, val); } else if (val <= nodeArr[2 * tree + 1].val) { return findMaxValNode(2 * tree + 1, val); } else { return 0; }}int main(){ int h, w, n; while (cin>>h>>w>>n) { if (h > 200005)h = 200005; build(1, 1, h, w); int wi; for (int i = 0; i < n; ++i) { scanf("%d", &wi); if (nodeArr[1].val < wi)printf("-1\n"); else { int tarNode = findMaxValNode(1, wi); if (tarNode == 0) { printf("-1\n"); } else printf("%d\n", nodeArr[tarNode].left); } } }}
另外，如果用指针来表示线段树会MLE。因为线段树是完全二叉树所以用数组来存储是最节约空间的。
