程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [NOI2005] 維修數列

[NOI2005] 維修數列

編輯：C++入門知識

這難度，簡直爽到不行。

前五種操作就不多說了，基礎到不能再基礎。

第六種操作求最大連續子段和，有點像線段樹，沒有思路的建議先看一下POJ2750。

代碼9000+，挫到荼靡。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define _INF 0x3f3f3f3f
#define Mod 9999991

using namespace std;

const int MAXN = 500100;

struct N
{
    //info
    int son[2],pre;

    //data
    int data;
    int same;
    int mark;
    int sum,Max[3];
    int ls,rs,s;
} st[MAXN];

int memo[MAXN];

int Top;

int num[MAXN];

void Output(int root)
{
    if(root == -1)
        return ;
    Output(st[root].son[0]);
    printf("r = %2d p = %2d d = %2d s = %2d m = %2d lm = %2d rm = %2d sum = %2d\n",root,st[root].pre,st[root].data,st[root].s,st[root].Max[2],st[root].Max[0],st[root].Max[1],st[root].sum);
    Output(st[root].son[1]);
}

void Erase(int root)
{
    if(root == -1)
        return ;
    Erase(st[root].son[0]);
    memo[--Top] = root;
    Erase(st[root].son[1]);
}

void Push_Down_mark(int root)
{
    if(st[root].mark == 1)
    {
        st[root].mark = 0;
        if(st[root].son[0] != -1)
            st[st[root].son[0]].mark ^= 1;
        if(st[root].son[1] != -1)
            st[st[root].son[1]].mark ^= 1;

        int temp;
        temp = st[root].son[0];
        st[root].son[0] = st[root].son[1];
        st[root].son[1] = temp;

        temp = st[root].Max[0];
        st[root].Max[0] = st[root].Max[1];
        st[root].Max[1] = temp;

        temp = st[root].ls;
        st[root].ls = st[root].rs;
        st[root].rs = temp;
    }
}

int Get_MAX(int root)
{
    if(root == -1)
        return -(1<<29);
    return st[root].Max[2];
}

int Get_SUM(int root)
{
    if(root == -1)
        return 0;
    return st[root].sum;
}

int Get_LMAX(int root)
{
    if(root == -1)
        return -(1<<29);
    return st[root].Max[st[root].mark];
}

int Get_RMAX(int root)
{
    if(root == -1)
        return -(1<<29);
    return st[root].Max[st[root].mark^1];
}

void Updata(int root)
{
    st[root].ls = 0 , st[root].rs = 0 , st[root].sum = st[root].data;

    if(st[root].son[0] != -1)
    {
        st[root].ls = st[st[root].son[0]].s;
    }
    if(st[root].son[1] != -1)
    {
        st[root].rs = st[st[root].son[1]].s;
    }

    st[root].s = st[root].ls + st[root].rs + 1;

    if(st[root].mark == 1)
        Push_Down_mark(root);

    if(st[root].same == 1)
    {
        st[root].sum = st[root].data * st[root].s;
        st[root].Max[0] = st[root].Max[1] = st[root].Max[2] = max(st[root].data,st[root].data*st[root].s);
    }
    else
    {
        st[root].sum = st[root].data + Get_SUM(st[root].son[0]) + Get_SUM(st[root].son[1]);
        st[root].Max[0] = max(Get_LMAX(st[root].son[0]),Get_SUM(st[root].son[0])+st[root].data+max(0,Get_LMAX(st[root].son[1])));
        st[root].Max[1] = max(Get_RMAX(st[root].son[1]),Get_SUM(st[root].son[1])+st[root].data+max(0,Get_RMAX(st[root].son[0])));
        st[root].Max[2] = st[root].data+max(0,Get_LMAX(st[root].son[1]))+max(0,Get_RMAX(st[root].son[0]));
        st[root].Max[2] = max(st[root].Max[2],max(Get_MAX(st[root].son[0]),Get_MAX(st[root].son[1])));
        st[root].Max[2] = max(st[root].Max[2],max(st[root].Max[0],st[root].Max[1]));
    }
}

void Push_Down_same(int root)
{
    if(st[root].same == 1)
    {
        st[root].Max[0] = st[root].Max[1] = st[root].Max[2] = max(st[root].data,st[root].data*st[root].s);
        st[root].sum = st[root].s * st[root].data;
        st[root].same = 0;

        if(st[root].son[0] != -1)
        {
            st[st[root].son[0]].data = st[root].data;
            st[st[root].son[0]].same = 1;
            Updata(st[root].son[0]);
        }

        if(st[root].son[1] != -1)
        {
            st[st[root].son[1]].data = st[root].data;
            st[st[root].son[1]].same = 1;
            Updata(st[root].son[1]);
        }
    }
}

void Push_Down(int root)
{
    Push_Down_mark(root);
    Push_Down_same(root);
}

void Init(int &root,int s,int e,int pre)
{
    if(s > e)
        return ;
    int mid = (s+e)>>1;
    root = memo[Top++];
    st[root].son[0] = -1,st[root].son[1] = -1;
    st[root].pre = pre;
    st[root].data = num[mid];
    st[root].mark = 0;
    st[root].same = 0;
    Init(st[root].son[0],s,mid-1,root);
    Init(st[root].son[1],mid+1,e,root);

    Updata(root);
}

void Rotate(int root,int dir)
{
    st[st[root].pre].son[dir] = st[root].son[1^dir];
    st[root].son[1^dir] = st[root].pre;

    if(st[st[st[root].pre].pre].son[0] == st[root].pre)
        st[st[st[root].pre].pre].son[0] = root;
    else
        st[st[st[root].pre].pre].son[1] = root;
    int temp = st[root].pre;
    st[root].pre = st[st[root].pre].pre;
    st[temp].pre = root;

    if(st[temp].son[dir] != -1)
        st[st[temp].son[dir]].pre = temp;
    Updata(temp);
    Updata(root);
}

int Splay(int root,int goal)
{
    while(st[root].pre != goal)
    {
        Rotate(root,(st[st[root].pre].son[0] == root ? 0 : 1));
    }

    return root;
}

int Search_Site(int root,int site)
{
    Push_Down(root);

    int temp;

    if(st[root].ls + 1 == site)
        temp = root;
    else if(st[root].ls + 1 < site)
        temp = Search_Site(st[root].son[1],site-st[root].ls-1);
    else
        temp = Search_Site(st[root].son[0],site);

    Updata(root);
    return temp;
}

int Search_Max(int root)
{
    if(st[root].son[1] == -1)
        return root;
    return Search_Max(st[root].son[1]);
}

void Insert(int &R,int pos,int len)
{
    R = Splay(Search_Site(R,pos+1),0);

    R = Splay(Search_Site(R,pos),0);

    int tr = -1;

    Init(tr,1,len,st[R].son[1]);

    st[st[R].son[1]].son[0] = tr;

    Updata(st[R].son[1]);
    Updata(R);
}

void Delete(int &R,int l,int r)
{
    R = Splay(Search_Site(R,r+1),0);
    R = Splay(Search_Site(R,l-1),0);

    Erase(st[st[R].son[1]].son[0]);

    st[st[R].son[1]].son[0] = -1;

    Updata(st[R].son[1]);
    Updata(R);
}

void Get_Sum(int &R,int l,int r)
{
    R = Splay(Search_Site(R,r+1),0);
    R = Splay(Search_Site(R,l-1),0);
    if(st[st[R].son[1]].son[0] == -1)
        printf("0\n");
    else printf("%d\n",st[st[st[R].son[1]].son[0]].sum);
}

void Make_Same(int &R,int l,int r,int x)
{
    R = Splay(Search_Site(R,r+1),0);
    R = Splay(Search_Site(R,l-1),0);

    st[st[st[R].son[1]].son[0]].same = 1;
    st[st[st[R].son[1]].son[0]].data = x;
    Push_Down(st[st[R].son[1]].son[0]);
    Updata(st[st[R].son[1]].son[0]);
    Updata(st[R].son[1]);
    Updata(R);

}

void Reverse(int &R,int l,int r)
{
    R = Splay(Search_Site(R,r+1),0);

    R = Splay(Search_Site(R,l-1),0);

    st[st[st[R].son[1]].son[0]].mark ^= 1;
    Updata(st[st[R].son[1]].son[0]);
    Updata(st[R].son[1]);
    Updata(R);
}

void Max_Sum(int &R)
{
    R = Splay(Search_Max(R),0);
    R = Splay(Search_Site(R,1),0);
    printf("%d\n",st[st[st[R].son[1]].son[0]].Max[2]);
}

int main()
{
    int n,m;

    int root;

    int pos,len,x;

    char order[10];

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

    for(int i = 0;i < MAXN ; ++i)
        memo[i] = i;

    root = -1,Top = 1;

    for(int i = 2; i <= n+1; ++i)
    {
        scanf("%d",&num[i]);
    }

    num[1] = num[n+2] = 0;

    Init(root,1,n+2,0);

    st[0].son[0] = root,st[0].son[1] = -1;

    int sum = n;

    int tt = m;

    while(m--)
    {
        scanf("%*c%s",order);

        if(strcmp(order,"INSERT") == 0)
        {
            scanf("%d %d",&pos,&len);

            for(int i = 1; i <= len; ++i)
                scanf("%d",&num[i]);
            if(len)
                Insert(root,pos+1,len);
        }
        else if(strcmp(order,"DELETE") == 0)
        {
            scanf("%d %d",&pos,&len);
            if(len)
                Delete(root,pos+1,pos+len);
        }
        else if(strcmp(order,"GET-SUM") == 0)
        {
            scanf("%d %d",&pos,&len);
            Get_Sum(root,pos+1,pos+len);
        }
        else if(strcmp(order,"MAKE-SAME") == 0)
        {
            scanf("%d %d %d",&pos,&len,&x);
            if(len)
                Make_Same(root,pos+1,pos+len,x);
        }
        else if(strcmp(order,"REVERSE") == 0)
        {
            scanf("%d %d",&pos,&len);
            if(len)
                Reverse(root,pos+1,pos+len);
        }
        else if(strcmp(order,"MAX-SUM") == 0)
        {
            Max_Sum(root);
        }

    }

    return 0;
}