【题解】Luogu P1204 [USACO1.2]挤牛奶Milking Cows

原题传送门：P1204 [USACO1.2]挤牛奶Milking Cows

实际是道很弱智的题目qaq

但窝还是觉得用珂朵莉树写会++rp（窝都初二了，还要考pj）

前置芝士：珂朵莉树

窝博客里对珂朵莉树的介绍

没什么好说的自己看看吧

每个农夫就assign_val一下，但要注意一下细节qaq

窝不会告诉你因这个错调了我十几分钟qaq

应该写assign_val(l,r-1,1)，查询时应写query（lmin，rmax，1/0）

其他没什么好说的了，细节详见程序

#pragma GCC optimize("O3")

#include<bits/stdc++.h>

#define IT set<node>::iterator

using namespace std;

struct IO_Tp

{

    static const int _I_Buffer_Size = 1 << 24;

    char _I_Buffer[_I_Buffer_Size];

    char* _I_pos;

    static const int _O_Buffer_Size = 1 << 24;

    char _O_Buffer[_O_Buffer_Size];

    char* _O_pos;

    IO_Tp() : _I_pos(_I_Buffer), _O_pos(_O_Buffer)

    {

        fread(_I_Buffer, 1, _I_Buffer_Size, stdin);

    }

    ~IO_Tp()

    {

        fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout);

    }

    inline bool is_digit(const char ch)

    {

        return '0' <= ch && ch <= '9';

    }

    inline IO_Tp& operator>>(int& res)

    {

        res = 0;

        while (!is_digit(*_I_pos))

            ++_I_pos;

        do

            (res *= 10) += (*_I_pos++) & 15;

        while (is_digit(*_I_pos));

        return *this;

    }

    inline IO_Tp& operator<<(int n)

    {

        static char _buf[10];

        char* _pos(_buf);

        do

            *_pos++ = '0' + n % 10;

        while (n /= 10);

        while (_pos != _buf)

            *_O_pos++ = *--_pos;

        return *this;

    }

    inline IO_Tp& operator<<(char ch)

    {

        *_O_pos++ = ch;

        return *this;

    }

} IO;

inline int Max(register int a,register int b)

{

    return a>b?a:b;

}

inline int Min(register int a,register int b)

{

    return a<b?a:b;

}

struct node

{

    int l,r;

    mutable bool v;

    node(int L, int R=-1, bool V=0):l(L), r(R), v(V) {}

    bool operator<(const node& o) const

    {

        return l < o.l;

    }

};

set<node> s;

IT split(int pos)

{

    IT it = s.lower_bound(node(pos));

    if (it != s.end() && it->l == pos)

        return it;

    --it;

    int L = it->l, R = it->r;

    bool V = it->v;

    s.erase(it);

    s.insert(node(L, pos-1, V));

    return s.insert(node(pos, R, V)).first;

}

void assign_val(int l,int r,bool v)

{

    IT itr = split(r+1),itl = split(l);

    s.erase(itl, itr);

    s.insert(node(l, r, v));

}

inline int query(register int l,register int r,register bool v)

{

    int sum=0,res=0;

    IT itr = split(r+1),itl = split(l);

    for(;itl!=itr;++itl)

        if(itl->v==v)

            sum+=itl->r-itl->l+1;

        else

        {

            res=Max(res,sum);

            sum=0;

        }

    return res;

}

int main()

{

    int n;

    IO>>n;

    int a=1000005,b=0;

    s.insert(node(0,1000005));

    while(n--)

    {

        int l,r;

        IO>>l>>r;

        assign_val(l,r-1,1);

        a=Min(a,l);

        b=Max(b,r);

    }

    IO<<query(a,b,1)<<' '<<query(a,b,0);

    return 0;

}

巴特西

【题解】Luogu P1204 [USACO1.2]挤牛奶Milking Cows

原题传送门：P1204 [USACO1.2]挤牛奶Milking Cows

实际是道很弱智的题目qaq

但窝还是觉得用珂朵莉树写会++rp（窝都初二了，还要考pj）

前置芝士：珂朵莉树

窝博客里对珂朵莉树的介绍

没什么好说的自己看看吧

每个农夫就assign_val一下，但要注意一下细节qaq

窝不会告诉你因这个错调了我十几分钟qaq

应该写assign_val(l,r-1,1)，查询时应写query（lmin，rmax，1/0）

其他没什么好说的了，细节详见程序

最新文章

热门文章