[CF 514D] R2D2 and Droid Army(라인 트리, RMQ)

【CF 514D】 R2D2 and Droid Army
n개 로봇 m은 총을 모든 몬스터에 대응하고 총 한 자루에 일정한 혈액량을 가지고 m개의 혈액탱크는 모두 비워두고 기계는 끊어버린다
m 총 총 k발 총알 어떻게 쏴요?
1~n 현재 구간 최대치 반복 통계
가장 긴 시퀀스를 출력하는 타법
이 문제는 RMQ로도 코드 양을 줄일 수 있습니다.이 문제를 통해서 RMQ를 배워서 붙여봤습니다.
코드는 다음과 같습니다.

//   
#include <cstdio>
#include <cstdio>
#include <cstring>

using namespace std;

typedef struct Node
{
    int m[5],next;
}Node;

Node tr[400040];//         
int ned[5];//
int st[5];
int rg[100001][5],m;

void SetTree(int site,int l,int r)
{
    if(l == r)
    {
        for(int i = 0; i < m; ++i)
            tr[site].m[i] = rg[l][i];
        return;
    }
    int mid = (l+r)>>1;
    SetTree(site<<1,l,mid);
    SetTree(site<<1|1,mid+1,r);
    for(int i = 0; i < m; ++i)
            tr[site].m[i] = max(tr[site<<1].m[i],tr[site<<1|1].m[i]);
}

void Recut(int site,int l,int r,int ll,int rr)
{
    if(l == ll && r == rr)
    {
        for(int i = 0; i < m; ++i)
        {
            st[i] = max(st[i],tr[site].m[i]);
        }
        return;
    }
    int mid = (l+r)>>1;
    if(mid >= rr) Recut(site<<1,l,mid,ll,rr);
    else if(mid < ll) Recut(site<<1|1,mid+1,r,ll,rr);
    else
    {
        Recut(site<<1,l,mid,ll,mid);
        Recut(site<<1|1,mid+1,r,mid+1,rr);
    }
}

int main()
{
    int n,k,i,j,kk,mlen,sum;
    scanf("%d %d %d",&n,&m,&kk);

    for(i = 1; i <= n; ++i)
        for(k = 0; k < m; ++k)
            scanf("%d",&rg[i][k]);

    SetTree(1,1,n);

    sum = mlen = 0;
    memset(st,0,sizeof(st));
    for(i = 1,j = 1; i <= n; ++i)
    {

        for(k = 0; k < m; ++k)
        {
            if(rg[i][k] > st[k])
            {
                sum += rg[i][k]-st[k];
                st[k] = rg[i][k];
            }
        }

        while(sum > kk)
        {
            if(j == i)
            {
                sum = 0;
                memset(st,0,sizeof(st));
                j++;
                break;
            }
            for(k = 0; k < m; ++k)
            {
                if(rg[j][k] == st[k])
                {
                    memset(st,0,sizeof(st));
                    Recut(1,1,n,j+1,i);
                    sum = 0;
                    for(k = 0; k < m; ++k)
                        sum += st[k];
                    break;
                }
            }
            ++j;
        }
        if(i-j+1 > mlen)
        {
            mlen = i-j+1;
            for(k = 0; k < m; ++k)
                ned[k] = st[k];
        }
    }

    for(i = 0; i < m; ++i)
    {
        if(i) putchar(' ');
        printf("%d",ned[i]);
    }
    puts("");
    return 0;
}

//RMQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int rq[100001][18][5];
int ned[5];
int st[5];
int m,n;

void Init()
{
    int i,j,k;
    for(j = 1; (1<<j) <= n; ++j)
        for(i = 1; i <= n; ++i)
            if(i + (1<<j) -1 <= n)
                for(k = 0; k < m; ++k)
                    rq[i][j][k] = max(rq[i][j-1][k],rq[i+(1<<(j-1))][j-1][k]);
}

int main()
{
    int k,i,j,kk,mlen,sum,t;

    scanf("%d %d %d",&n,&m,&kk);

    sum = mlen = 0;
    memset(st,0,sizeof(st));

    for(i = 1,j = 1; i <= n; ++i)
    {
        for(k = 0; k < m; ++k)
        {
            scanf("%d",&rq[i][0][k]);
        }
    }

    Init();

    for(i = 1,j = 1; i <= n; ++i)
    {
        for(k = 0; k < m; ++k)
        {
            if(rq[i][0][k] > st[k])
            {
                sum +=rq[i][0][k]-st[k];
                st[k] = rq[i][0][k];
            }
        }
        while(sum > kk)
        {
            if(j == i)
            {
                sum = 0;
                memset(st,0,sizeof(st));
                j++;
                break;
            }
            for(k = 0; k < m; ++k)
            {
                if(rq[j][0][k] == st[k])
                {
                    memset(st,0,sizeof(st));
                    sum = 0;
                    for(k = 0; k < m; ++k)
                    {
                        t = log10(i-j)/log10(2);
                        st[k] = max(rq[j+1][t][k],rq[i-(1<<t)+1][t][k]);
                        sum += st[k];
                    }
                    break;
                }
            }
            ++j;
        }
        if(i-j+1 > mlen)
        {
            mlen = i-j+1;
            for(k = 0; k < m; ++k)
                ned[k] = st[k];
        }
    }

    for(i = 0; i < m; ++i)
    {
        if(i) putchar(' ');
        printf("%d",ned[i]);
    }
    puts("");
    return 0;
}