洛谷云剪贴板

作者: EndSaH 发表时间: 2019-02-14 22:02 https://www.luogu.org/paste/ivmvw8f1 公开

$\text{P4008}$ 块状链表

/**********************************************************
 * Author        : EndSaH
 * Email         : hjxhb1@gmail.com
 * Created Time  : 2019-02-14 13:53
 * FileName      : temp.cpp
 * Website       : https://endsah.cf
 * *******************************************************/

#include <cstdio>
#include <cctype>
#include <forward_list>
#include <vector>

typedef std::forward_list<std::vector<char> >::iterator ptr;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The message in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define __bufsize (1 << 20)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[20];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__;

inline int read()
{
    register int x = 0;
    register char ch;
    while (!isdigit(ch = getchar()));
    while (x = (x << 3) + (x << 1) + (ch & 15), isdigit(ch = getchar()));
    return x;
}

inline void read(char* str)
{
    while (isspace(*str = getchar()));
    while (!isspace(*++str = getchar()));
    *str = '\0';
}

template <typename _INT>
inline void write(_INT x)
{
    while (*++stkpos = x % 10 ^ 48, x /= 10, x);
    while (stkpos != _stk)
        putchar(*stkpos--);
}

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

int t, size = 23333, pos;
char opt[7];
std::vector<char> temp;
std::forward_list<std::vector<char> > List;

inline ptr Next(ptr x)
{ return ++x; }

inline ptr Find(int& x) // Attention! &!
{
    for (register ptr i = List.begin(); i != List.end(); ++i)
    {
        if (x <= i->size())
            return i;
        x -= i->size();
    }
    return List.before_begin();
}

inline void Output(int l, int r) // [l, r)
{
    register ptr L = Find(l), R = Find(r);
    if (L == R)
        for (register int i = l; i < r; ++i)
            putchar(L->at(i));
    else
    {
        for (register int i = l; i < L->size(); ++i)
            putchar(L->at(i));
        for (++L; L != R; ++L)
            for (register int i = 0; i < L->size(); ++i)
                putchar(L->at(i));
        for (register int i = 0; i < r; ++i)
            putchar(R->at(i));
    }
    putchar('\n');
}

inline void Merge(ptr x) {
    x->insert(x->end(), Next(x)->begin(), Next(x)->end());
    List.erase_after(x);
}

inline void Split(ptr x, int pos)
{
    if (pos == x->size())
        return;
    List.insert_after(x, std::vector<char>(x->begin() + pos, x->end()));
    x->erase(x->begin() + pos, x->end());
}

inline void Update()
{
    for (register ptr i = List.begin(); i != List.end(); ++i)
    {
        while (i->size() >= (size << 1))
            Split(i, i->size() - size);
        while (Next(i) != List.end() and i->size() + Next(i)->size() <= size)
            Merge(i);
        while (Next(i) != List.end() and Next(i)->empty())
            List.erase_after(i);
    }
}

inline void Insert(int pos, const std::vector<char>& ins)
{
    register ptr curr = Find(pos);
    if (!List.empty())
        Split(curr, pos);
    List.insert_after(curr, ins);
    Update();
}

inline void Delete(int l, int r) // [l, r)
{
    register ptr L, R;
// Attention! This can be wrong:
// L = Find(l), R = Find(r);
// Split(L, l), Split(R, r);
    L = Find(l), Split(L, l);
    R = Find(r), Split(R, r);
    for (++R; Next(L) != R; List.erase_after(L));
    Update();
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("temp.in", "r", stdin);
    freopen("temp.out", "w", stdout);
#endif
    t = read();
    while (t--)
    {
        read(opt);
        switch (opt[0])
        {
        case 'M' :
            pos = read();
            break;
        case 'I' :
            temp.clear(), temp.resize(read());
            for (register unsigned int i = 0; i < temp.size(); ++i)
                while (temp[i] = getchar(), temp[i] == '\r' or temp[i] == '\n');
            Insert(pos, temp);
            break;
        case 'D' :
            Delete(pos, pos + read());
            break;
        case 'G' :
            Output(pos, pos + read());
            break;
        case 'P' :
            --pos;
            break;
        case 'N' :
            ++pos;
            break;
        default :
            break;
        }
    }
    return 0;
}

源码  复制

# $\text{P4008}$ 块状链表

```cpp
/**********************************************************
 * Author        : EndSaH
 * Email         : hjxhb1@gmail.com
 * Created Time  : 2019-02-14 13:53
 * FileName      : temp.cpp
 * Website       : https://endsah.cf
 * *******************************************************/

#include <cstdio>
#include <cctype>
#include <forward_list>
#include <vector>

typedef std::forward_list<std::vector<char> >::iterator ptr;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The message in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define __bufsize (1 << 20)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[20];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__;

inline int read()
{
    register int x = 0;
    register char ch;
    while (!isdigit(ch = getchar()));
    while (x = (x << 3) + (x << 1) + (ch & 15), isdigit(ch = getchar()));
    return x;
}

inline void read(char* str)
{
    while (isspace(*str = getchar()));
    while (!isspace(*++str = getchar()));
    *str = '\0';
}

template <typename _INT>
inline void write(_INT x)
{
    while (*++stkpos = x % 10 ^ 48, x /= 10, x);
    while (stkpos != _stk)
        putchar(*stkpos--);
}

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

int t, size = 23333, pos;
char opt[7];
std::vector<char> temp;
std::forward_list<std::vector<char> > List;

inline ptr Next(ptr x)
{ return ++x; }

inline ptr Find(int& x) // Attention! &!
{
    for (register ptr i = List.begin(); i != List.end(); ++i)
    {
        if (x <= i->size())
            return i;
        x -= i->size();
    }
    return List.before_begin();
}

inline void Output(int l, int r) // [l, r)
{
    register ptr L = Find(l), R = Find(r);
    if (L == R)
        for (register int i = l; i < r; ++i)
            putchar(L->at(i));
    else
    {
        for (register int i = l; i < L->size(); ++i)
            putchar(L->at(i));
        for (++L; L != R; ++L)
            for (register int i = 0; i < L->size(); ++i)
                putchar(L->at(i));
        for (register int i = 0; i < r; ++i)
            putchar(R->at(i));
    }
    putchar('\n');
}

inline void Merge(ptr x) {
    x->insert(x->end(), Next(x)->begin(), Next(x)->end());
    List.erase_after(x);
}

inline void Split(ptr x, int pos)
{
    if (pos == x->size())
        return;
    List.insert_after(x, std::vector<char>(x->begin() + pos, x->end()));
    x->erase(x->begin() + pos, x->end());
}

inline void Update()
{
    for (register ptr i = List.begin(); i != List.end(); ++i)
    {
        while (i->size() >= (size << 1))
            Split(i, i->size() - size);
        while (Next(i) != List.end() and i->size() + Next(i)->size() <= size)
            Merge(i);
        while (Next(i) != List.end() and Next(i)->empty())
            List.erase_after(i);
    }
}

inline void Insert(int pos, const std::vector<char>& ins)
{
    register ptr curr = Find(pos);
    if (!List.empty())
        Split(curr, pos);
    List.insert_after(curr, ins);
    Update();
}

inline void Delete(int l, int r) // [l, r)
{
    register ptr L, R;
// Attention! This can be wrong:
// L = Find(l), R = Find(r);
// Split(L, l), Split(R, r);
    L = Find(l), Split(L, l);
    R = Find(r), Split(R, r);
    for (++R; Next(L) != R; List.erase_after(L));
    Update();
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("temp.in", "r", stdin);
    freopen("temp.out", "w", stdout);
#endif
    t = read();
    while (t--)
    {
        read(opt);
        switch (opt[0])
        {
        case 'M' :
            pos = read();
            break;
        case 'I' :
            temp.clear(), temp.resize(read());
            for (register unsigned int i = 0; i < temp.size(); ++i)
                while (temp[i] = getchar(), temp[i] == '\r' or temp[i] == '\n');
            Insert(pos, temp);
            break;
        case 'D' :
            Delete(pos, pos + read());
            break;
        case 'G' :
            Output(pos, pos + read());
            break;
        case 'P' :
            --pos;
            break;
        case 'N' :
            ++pos;
            break;
        default :
            break;
        }
    }
    return 0;
}
```