14106: 【原4106】Watashi kininarimasu！

题目描述

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

为了搜查出秘密社团——“女郎蜘蛛会”的招新便条，折木和千反田正在分析公告板上的所有社团招新海报。由于神山高中以社团活动丰富多彩为传统，巨大的公告板几乎已经被各式各样的招新海报贴满。幸好，为了方便管理，社团的招新海报都按照总务委员会的规定设计和张贴，因此相当整齐。总务委员会的规定是这样的：公告板的高为\(H\)（个单位长度），宽为\(W\)，从上往下的行标为\(1\sim H\)，从左往右的列标为\(1\sim W\)；而招新海报的高度必须为\(1\)，宽可以为任意的正整数。海报是各个社团在不同时间张贴上去的（即非同时，有唯一顺序），张贴时必须遵守“海报之间不能重叠，张贴时必须张贴在可以张贴的最高的位置（行标尽可能小），如果这样的位置有多个就张贴在最左边的那个位置上（列标尽可能小）”的规则，而且海报中也必须写上张贴的时间。如果无法张贴，就只能叠在公告板旁边的盒子里面了，谁让你来得太晚/海报做的太宽了呢。

当然，对公告板的内容分析完成之后，上面并没有女郎蜘蛛会的招新便条（不然早被总务委员会撕了），于是折木开始一边回家一边思考（为了节能）那张招新便条到底藏在了哪里。机智如折木，他仅仅花了九分又二十五秒就推理（YY）出了便条藏在那张覆盖了某某坐标的海报之后，这张海报所属的社团里面一定有内鬼。然而折木并不记得覆盖那个坐标的海报是哪个社团的了，于是他去询问旁边记忆力超群的千反田；然而由于千反田对于每张海报的具体内容过于“我很好奇”，她只记住了每张海报（包括公告板上放不下的那些）的宽度以及该张海报的张贴时间（即记住了所有海报的粘贴顺序），却没有记住每张海报的位置，于是她把这些信息告诉了折木。机智如折棒，他一下子就发现有这些信息就可以立刻推断出每张海报的张贴位置，而且还推断出暴力枚举时间复杂度只需\(O(N^2)\)，如果开个线段树之类的数据结构维护某些信息还能做到\(O(N\log N)\)。然而由于折木很节能（懒癌晚期），他进一步推断出你写个线段树把这道水题切了比他用人脑思考或者浪费二十分钟回学校看一眼更加节能，于是他直接把这个任务甩给了你。

Input Format

第一行一个整数\(T\)，为数据组数。（本题10大组数据，但每个大组数据下分\(T\)个小组，一个小组错误则该大组0分，时间限制为一个大组的时间限制。）

接下来共\(T\)行，每行为一组数据。每行的前三个正整数为\(H,W,N\)，代表告示板的高度为\(H\)，宽度为\(W\)，总共有\(N\)张海报；接下来的\(N\)个正整数\(w_i\)表示每张海报的宽度，当然是已经按照时间顺序排好序的。

Output Format

输出共\(T\)行，每行\(N\)个数字，代表每张海报的所在行数（列数就不需要了，节省输出）。如果这张海报贴不上公告板，则所在行数为-1。

Sample Input

1
3 5 5 2 4 3 3 3

Sample Output

1 2 1 3 -1

Data Range

对于\( 50\% \) 的数据，\( 1 \le N \le 5000\)，\( 1 \le H,W,w_i \le 1000\)。

对于\( 100\% \) 的数据，\( 1 \le T \le 5\)，\( 1 \le N \le 200000\)，\( 1 \le H,W,w_i \le 10^9\)。

友情提示：计算机系统这门课程告诉我们，对磁盘大量重复进行读一个文件/写另一个文件/读一个文件/写另一个文件这种操作会浪费大量IO时间在寻道上（显然每次往回转需要磁盘多转一整圈，而顺序读入或写入只需向下移动一点）。

另一个友情提示：经过实测，scanf不论是先读后写还是边读边写的用时都很长，建议使用cin，即能够以用时约60%的时间限制通过。如果再加上字符串式读入优化/关闭stdio同步读入优化，用时可以进一步缩短到三分之一。

本题时间限制2s。

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;
}