题意

在矩形广告牌上塞广告，每个广告宽为w高为1，规则从上至下，从左至右塞，塞不进去输出-1

思路

对广告牌高度建线段树，维护高度区间剩余宽度最大值，线段树查找可以塞的位置，并更新那个位置的剩余宽度，注意到h可能很大，但其实n只有200000，所以我们最多只需要建200000就可以了，因为如果这200000的高度如果还塞不进去后面的肯定也塞不进去了。

1 #define IO std::ios::sync_with_stdio(0); 2 #include 
     
       3 #define iter ::iterator 4 using namespace  std; 5 typedef long long ll; 6 typedef pair
      
       P; 7 #define pb push_back 8 #define se second 9 #define fi first10 #define rs o*2+111 #define ls o*212 const int N=2e5+5;13 int n,m,q,ans;14 int maxv[N*4];15 void build(int o,int l,int r){16     if(l==r){17         maxv[o]=m;18         return;19     }20     int m=(l+r)/2;21     build(ls,l,m);22     build(rs,m+1,r);23     maxv[o]=max(maxv[ls],maxv[rs]);24 }25 void query(int o,int l,int r,int v){26     if(maxv[o]
       
        =v){28         maxv[o]-=v;29         ans=l;30         return;31     }32     int m=(l+r)/2;33     if(maxv[ls]>=v)query(ls,l,m,v);34     else if(maxv[rs]>=v)query(rs,m+1,r,v);35     maxv[o]=max(maxv[ls],maxv[rs]);36 }37 int main(){38     while(~scanf("%d%d%d",&n,&m,&q)){39         n=min(n,q);40         build(1,1,n);41         while(q--){42             int x;43             scanf("%d",&x);44             ans=-1;45             query(1,1,n,x);46             printf("%d\n",ans);47         }48     }49 }