# 14106: 【原4106】Watashi kininarimasu！

### 题目描述

author: 黄俊翔 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4106 ﻿## Description

## Sample Input

``````1
3 5 5 2 4 3 3 3
``````

## Sample Output

``````1 2 1 3 -1
``````

## FineArtz's solution

``````/* Watashi kininarimasu! */
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int MAXN = 200000;

struct Node{
int l = 0, r = 0;
int maxx = 0;
};

Node a[MAXN * 4 + 5];

int t;
int h, w, n;

void pushUp(int x){
if (a[x * 2].maxx >= a[x * 2 + 1].maxx)
a[x].maxx = a[x * 2].maxx;
else
a[x].maxx = a[x * 2 + 1].maxx;
}

void buildTree(int x, int l, int r){
a[x].l = l;
a[x].r = r;
if (l == r){
a[x].maxx = w;
return;
}
int mid = (l + r) / 2;
buildTree(x * 2, l, mid);
buildTree(x * 2 + 1, mid + 1, r);
pushUp(x);
}

void update(int x, int line, int len){
if (a[x].l == a[x].r){
a[x].maxx -= len;
return;
}
int mid = (a[x].l + a[x].r) / 2;
if (line <= mid)
update(x * 2, line, len);
else
update(x * 2 + 1, line, len);
pushUp(x);
}

int query(int x, int len){
if (a[x].l == a[x].r)
return a[x].l;
if (a[x * 2].maxx >= len)
return query(x * 2, len);
else
return query(x * 2 + 1, len);
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t--){
cin >> h >> w >> n;
buildTree(1, 1, min(n, h));
for (int i = 1; i <= n; ++i){
int m;
cin >> m;
if (m > a[1].maxx){
cout << "-1\n";
continue;
}
int line = query(1, m);
cout << line << '\n';
update(1, line, m);
}
}
return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int tr[1050000],m,h,w,n,t,x,f,ans[200001];//丐版线段树 请勿模仿
int main() {
ios::sync_with_stdio(false);
cin>>t;
for (int i=0;i<t;++i)
{
memset(tr,0,sizeof(tr));
cin>>h>>w>>n;
h=min(h,n);
for (m=1;m<h;m<<=1);
for (int j=1+m;j<=m+h;++j)
tr[j]=w;
for (int j=m+h+1;j<=m<<1;++j)
tr[j]=0;
for (int j=m;j>=1;--j)
tr[j]=max(tr[j<<1],tr[(j<<1)+1]);//以上为建树
for (int j=0;j<n;++j)
{
cin>>x;
if (tr[1]<x)
{
ans[j]=-1;
continue;
}
f=1;
while (f<=m)
if (tr[f<<=1]<x) f+=1;//单点查询
tr[f]-=x;
ans[j]=f-m;
for (f>>=1;f>=1;f>>=1) tr[f]=max(tr[f<<1],tr[(f<<1)+1]);//单点修改
}
for (int j=0;j<n;++j)
cout<<ans[j]<<" ";
cout<<endl;
}
return 0;
}
``````