欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-12 17:32:10
...

原题传送门: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;
}