主要是模型的转换,如何把本题和线段树联系起来。如右图所示,把图片左转90度,也就是 w 实际上是树的深度。左上角优先,意味着做孩子,叶子节点优先。
所以在更新查询的时候尽量向左下走。
#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; #define INF -100000000; int maxx[200010<<2]; int w,h,n; void pushup(int root) { maxx[root] = max(maxx[root<<1],maxx[root<<1 | 1]); } void build(int l ,int r,int root) { maxx[root] = w; if(l == r) return ; int mid = (l + r) >> 1; build(l,mid,root<<1); build(mid+1,r,root<<1 | 1); } int query(int p,int l,int r,int root) { if(l == r) { maxx[root] -= p; return l; } int mid = (l+r)>>1; int ans; ans = p <= maxx[root<<1] ?query(p,l,mid,root<<1):query(p,mid+1,r,root<<1 | 1); pushup(root); return ans; } int main() { //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); int x; while(~scanf("%d%d%d",&h,&w,&n)) { if(h>n) h = n; build(1,h,1); while(n--) { scanf("%d",&x); printf("%d\n",(maxx[1]<x?-1:query(x,1,h,1))); } } return 0; }