Fan_HD's Blog

闲来做水题，结果把线段树码成了Spaly。。。。。。

智商果然下降了。。。

#include <cstdio>
#include <cstring>
using namespace std;

int N, M;
char S[50004];
struct Splay
{
    Splay *P, *L, *R;
    int v, c, d, f;// v : Value, d : Delta, c : Current, f : Cover;
    bool ff;// ff : Whether Cover;
    int Size;
    Splay()
    {
        P = L = R = NULL;
        v = c = d = f = 0;
        ff = false;
        Size = 1;
    }
    void Update()
    {
        Size = 1;
        if (L) Size += L->Size;
        if (R) Size += R->Size;
    }
}Data[50004], *Top;
inline void Zig(Splay *X)
{
    Splay *Y = X->P;
    if (Y->P) (Y->P->L == Y) ? Y->P->L = X : Y->P->R = X;
    X->P = Y->P, Y->P = X;
    Y->L = X->R, X->R = Y;
    if (Y->L) Y->L->P = Y;
    Y->Update();
}
inline void Zag(Splay *X)
{
    Splay *Y = X->P;
    if (Y->P) (Y->P->L == Y) ? Y->P->L = X : Y->P->R = X;
    X->P = Y->P, Y->P = X;
    Y->R = X->L, X->L = Y;
    if (Y->R) Y->R->P = Y;
    Y->Update();
}
Splay *T[50004];
int Cnt;
inline void Cover(Splay *X, int f)
{
    if (X)
    {
        X->ff = true;
        X->v = X->f = f;
        X->d = X->c = 0;
    }
}
inline void Plus(Splay *X, int c, int d)
{
    c = c % 26;
    if (c < 0) c += 26;
    X->v += c, X->c += c, X->d += d;
}
inline int Rs(Splay *X)
{
    return (X->R) ? X->R->Size : 0;
}
inline int Ls(Splay *X)
{
    return (X->L) ? X->L->Size : 0;
}
inline void Down(Splay *X)
{
    if (X->ff)
    {
        Cover(X->L, X->f), Cover(X->R, X->f);
        X->ff = false;
    }
    if (X->L) Plus(X->L, X->c - (Rs(X->L) + 1) * X->d, X->d);
    if (X->R) Plus(X->R, X->c + (Ls(X->R) + 1) * X->d, X->d);
    X->c = X->d = 0;
}
inline void splay(Splay *X)
{
    Splay *Y, *Z, *K;
    for (K = X, Cnt = 0; K; T[++ Cnt] = K, K = K->P);
    for (int i = Cnt; i; i --) Down(T[i]);
    while (X->P)
    {
        Y = X->P;
        if (Y->P)
        {
            Z = Y->P;
            if (Z->L == Y)
            {
                if (Y->L == X) Zig(Y), Zig(X);
                else Zag(X), Zig(X);
            }else
            {
                if (Y->R == X) Zag(Y), Zag(X);
                else Zig(X), Zag(X);
            }
        }else
        {
            if (Y->L == X) Zig(X);
            else Zag(X);
        }
    }
    X->Update(), Top = X;
}
Splay *Build(Splay *S, int Len, Splay *P = NULL)
{
    if (Len == 1)
    {
        S[1].P = P;
        return S + 1;
    }
    if (Len == 0) return NULL;
    int mid = (1 + Len) >> 1;
    S[mid].P = P;
    S[mid].L = Build(S, mid - 1, S + mid);
    S[mid].R = Build(S + mid, Len - mid, S + mid);
    S[mid].Update();
    return S + mid;
}
inline Splay *Find(int x)
{
    Splay *C = Top;
    int ss;
    while (true)
    {
        ss = Ls(C);
        if (ss + 1 == x) break;
        if (ss >= x) C = C->L;
        else {
            x -= ss + 1;
            C = C->R;
        }
    }
    splay(C);
    return C;
}
inline void CMD1()
{
    int i, j, X;
    scanf("%d%d%s", &i, &j, S);
    X = S[0] - 'A';
    if (i == j)
    {
        Find(j)->v = X;
        return;
    }
    Splay *u = Find(j), *v = Find(i);
    while (u->P != v)
    {
        Down(u->P);
        if (u->P->L == v) Zig(u);
        else Zag(u);
        u->Update();
    }
    Down(v), Down(u);
    Cover(u->L, X);
    v->v = u->v = X;
}
inline void CMD2()
{
    int i, j, X;
    scanf("%d%d%d", &i, &j, &X);
    if (i == j)
    {
        Find(j)->v += X;
        return;
    }
    Splay *u = Find(j), *v = Find(i);
    while (u->P != v)
    {
        Down(u->P);
        if (u->P->L == v) Zig(u);
        else Zag(u);
        u->Update();
    }
    Down(v), Down(u);
    v->v +=X, u->v +=X;
    if (u->L) Plus(u->L, X, 0);
}
inline void CMD3()
{
    int K;
    scanf("%d", &K);
    if (K == N) return;
    Splay *u = Find(K), *v = u->R;
    v->P = NULL;
    u->R = NULL, u->Update();
    u = Find(1), u->L = v;
    v->P = u, u->Update();
}
inline void CMD4()
{
    int i, j;
    scanf("%d%d", &i, &j);
    if (i == j)
    {
        Find(i)->v ++;
        return;
    }
    Splay *u = Find(j), *v = Find(i);
    while (u->P != v)
    {
        Down(u->P);
        if (u->P->L == v) Zig(u);
        else Zag(u);
        u->Update();
    }
    Down(v), Down(u);
    if (u->L) Plus(u->L, Ls(u->L) + 2, 1);
    v->v ++, u->v += j - i + 1;
}
inline void Print(Splay *X = Top)
{
    Down(X);
    if (X->L) Print(X->L);
    putchar('A' + X->v % 26);
    if (X->R) Print(X->R);
}
int main()
{
    scanf("%d%d", &N, &M);
    scanf("%s", S + 1);
    for (int i = 1; i <= N; i ++) Data[i].v = S[i] - 'A';
    Top = Build(Data, N);
    for (int i = 1, opt; i <= M; i ++)
    {
        scanf("%s", S);
        scanf("%d", &opt);
        if (opt == 1) CMD1();
        if (opt == 2) CMD2();
        if (opt == 3) CMD3();
        if (opt == 4) CMD4();
    }
    Print();
    return 0;
}