BZoj 1500 [NOI2005]维修数列 (Splay 模板)

系统管理员 2023-07-06 14:46 2阅读 0赞

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1500

题意：

题目首先给出一个数列，然后进行下列6种操作  
\* 1:INSERT post tot c1,c2,...ctot :在当前数列的第pos个数字后插入tot个数字  
\* 2:DELETE pos tot : 从当前数列的第pos个数字开始连续 删除tot个数字  
\* 3:MAKE-SAME pos tot c :将当前数列的第pos个数字开始连续的tot个数字统一修改为c  
\* 4:REVERSE pos tot : 翻转当前数列的第pos个数字来说的连续的tot个数字  
\* 5:GET-SUM pos tot :计算当前数列的第pos个数字来说的连续的tot个数字的和并输出  
\* 6：MAX-SUM ：求出当前数列中和最大的一段序列，输出最大和

debug 完这道题之后整个人都斯巴达了。。。。。。。

目测电气自动化专业这学期天书略多。。。。。

Splay最基本的功能这道题基本都包括了，参考了上一篇博文提到的博客。下一题要开始自己想了。

这里有一个别人的模板：

[splay 的普通平衡树功能 - 鲜花会有的，AC会有的！ - 博客频道 - CSDN.NET][splay _ - _AC_ - _ - CSDN.NET]

#include <cstdio>
    #include <algorithm>
    using namespace std;
    #define min(a,b) ((a)<(b)?(a):(b))
    #define max(a,b) ((a)>(b)?(a):(b))
    
    #define Key_value ch[ch[root][1]][0] //根节点右孩子的左孩子
    #define Key_Value ch[ch[root][1]][0]
    
    const int N=500010;
    const int INF=0x3f3f3f3f;
    //分别表示父结点,左右孩子(0为左孩子，1为右孩子),键值,结点规模
    int pre[N],ch[N][2],key[N],size[N];
    //加法延迟标记,翻转延迟标记,最小值
    int add[N],rev[N],m[N];
    //区间和延迟标记,区间修改相同延迟标记
    int sum[N],same[N];
    //最大连续和
    int lx[N],rx[N],mx[N];
    int root,tot1;  //根节点,节点数量
    int s[N],tot2;//内存池、内存池容量
    int data[N];  //初始数列数组
    int n,q;
    
    ///   debug  
    void Treavel (int x)
    {
        if(x)
        {
            Treavel(ch[x][0]);
            printf("结点 %2d:左儿子 %2d 右儿子 %2d  父结点 %2d key=%2d,size=%2d,rev=%2d\n",x,ch[x][0],ch[x][1],pre[x],key[x],size[x],rev[x]);
            Treavel(ch[x][1]);
        }
    }
    void debug ()
    {
        printf("root:%d\n",root);
        Treavel(root);
    }
    /
    
    void NewNode (int &r,int father,int k)
    {
        if (tot2)r=s[tot2--];
        else r=++tot1;
        ch[r][0]=ch[r][1]=0;
        pre[r]=father;
        size[r]=1;
    	sum[r]=k;
    	same[r]=0;
        add[r]=rev[r]=0;
        key[r]=m[r]=k;
    	lx[r]=rx[r]=mx[r]=k;
    }
    void Update_Rev (int r)  //更新r节点的翻转值
    {
        if(!r)return;
        swap(ch[r][0],ch[r][1]);
    	swap(lx[r],rx[r]);        注意这里,记得交换
        rev[r]^=1;
    }
    void Update_Same (int r,int v)
    {
        if(!r)return;
        key[r]=v;
        sum[r]=v*size[r];
        lx[r]=rx[r]=mx[r]=max(v,v*size[r]);
        same[r]=1;
    }
    
    void Update_Add (int r,int ADD) //更新r节点的加法值
    {
        if(!r)return;
        add[r]+=ADD;
        key[r]+=ADD;
        m[r]+=ADD;
    }
    
    void Push_Up (int r) //向上更新,由r节点的儿子更新r节点
    {
        size[r]=size[ch[r][0]]+size[ch[r][1]]+1;
    	//更新最小值
        m[r]=key[r];
        if(ch[r][0])m[r]=min(m[r],m[ch[r][0]]);
        if(ch[r][1])m[r]=min(m[r],m[ch[r][1]]);
    	//更新和及最大连续和
    	int lson=ch[r][0],rson=ch[r][1];
        sum[r]=sum[lson]+sum[rson]+key[r];
        lx[r]=max(lx[lson],sum[lson]+key[r]+max(0,lx[rson]));
        rx[r]=max(rx[rson],sum[rson]+key[r]+max(0,rx[lson]));
        mx[r]=max(0,rx[lson])+key[r]+max(0,lx[rson]);
        mx[r]=max(mx[r],max(mx[lson],mx[rson]));
    }
    void Push_Down (int r)  //向下更新,由r节点更新其儿子节点
    {
    	if (same[r])
    	{
    		Update_Same(ch[r][0],key[r]);
    		Update_Same(ch[r][1],key[r]);
    		same[r]=0;
    	}
        if (rev[r])
        {
            Update_Rev(ch[r][0]);
            Update_Rev(ch[r][1]);
            rev[r]=0;
        }
        if (add[r])
        {
            Update_Add(ch[r][0],add[r]);
            Update_Add(ch[r][1],add[r]);
            add[r]=0;
        }
    	
    }
    
    void Build (int &x,int l,int r,int father)
    {//利用数组data建树,data从1开始,有n个元素
    //调用格式 Build(Key_value,1,n,ch[root][1]);
        if (l>r) return;
        int mid=(l+r)>>1;
        NewNode(x,father,data[mid]);
        Build(ch[x][0],l,mid-1,x);
        Build(ch[x][1],mid+1,r,x);
        Push_Up(x);
    }
    
    void Init ()
    {//Splay初始化
        root=tot1=tot2=0;
        ch[root][0]=ch[root][1]=size[root]=pre[root]=key[root]=0;
    	add[root]=rev[root]=sum[root]=same[root]=0;
    	lx[root]=rx[root]=mx[root]=-INF;
        m[root]=INF;//这个不用也可以,如果在push_up那判断了的话，否则需要
    	///视求最大最小值修改///
    	NewNode(root,0,-1);
    	NewNode(ch[root][1],root,-1);
    	
    	NewNode(root,0,INF);
    	NewNode(ch[root][1],root,INF);  
    }
    
    void Init_Array ()
    {
    	for (int i=1;i<=n;i++) scanf("%d",&data[i]);
    	Init ();
    	Build(Key_value,1,n,ch[root][1]);
    	Push_Up(ch[root][1]);
    	Push_Up(root);
    }
    
    void Rotate (int x,int kind)
    {//旋转
        int y=pre[x];
        Push_Down(y);
        Push_Down(x);
        ch[y][!kind]=ch[x][kind];
        pre[ch[x][kind]]=y;
        if(pre[y])
            ch[pre[y]][ch[pre[y]][1]==y]=x;
        pre[x]=pre[y];
        ch[x][kind]=y;
        pre[y]=x;
        Push_Up(y);
    }
    
    void Splay (int r,int goal) 
    {//Splay调整,将第r节点调整到goal位置
    	
        Push_Down(r);
        while (pre[r]!=goal)
        {
            if (pre[pre[r]]==goal)
            {
                //这题有反转操作，需要先push_down,再判断左右孩子
                Push_Down(pre[r]);
                Push_Down(r);
                Rotate(r,ch[pre[r]][0]==r);
            }
    
            else
            {
                //这题有反转操作，需要先push_down,再判断左右孩子
                Push_Down(pre[pre[r]]);
                Push_Down(pre[r]);
                Push_Down(r);//printf("nani?\n");
                int y=pre[r];
                int kind=(ch[pre[y]][0]==y);
                //两个方向不同，则先左旋再右旋
                if (ch[y][kind]==r)
                {
                    Rotate(r,!kind);
                    Rotate(r,kind);
                }
                //两个方向相同，相同方向连续两次
                else
                {
                    Rotate(y,kind);
                    Rotate(r,kind);
                }
            }
        }
        Push_Up(r);
    	//更新根节点
        if(goal==0)root=r;
    }
    
    int Get_Kth (int r,int k)   //找第k个节点
    {
        Push_Down(r);
        int t=size[ch[r][0]]+1;
        if(t==k)return r;
        if(t>k)return Get_Kth(ch[r][0],k);
        else return Get_Kth(ch[r][1],k-t);
    }
    
    int Get_Min (int r)
    {
        Push_Down(r);
        while (ch[r][0])
        {
            r=ch[r][0];
            Push_Down(r);
        }
        return r;
    }
    
    int Get_Max (int r)
    {
        Push_Down (r);
        while (ch[r][1])
        {
            r=ch[r][1];
            Push_Down(r);
        }
        return r;
    }
    
    //下面是操作了
    
    void Add (int l,int r,int D)
    {//区间l到r全部加D
        Splay(Get_Kth(root,l),0);
        Splay(Get_Kth(root,r+2),root);
        Update_Add(Key_value,D);
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void Reverse (int l,int r)
    {//区间l到r全部翻转
        Splay(Get_Kth(root,l),0);
        Splay(Get_Kth(root,r+2),root);
        Update_Rev(Key_value);
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void Revolve (int l,int r,int T)
    {//循环右移T长度,其实就是交换区间
        int len=r-l+1;
        T=(T%len+len)%len;
        if (T==0)return;
        int c=r-T+1;//将区间[c,r]放在[l,c-1]前面
        Splay(Get_Kth(root,c),0);
        Splay(Get_Kth(root,r+2),root);
        int tmp=Key_value;
        Key_value=0;   //此时已将区间拆下
        Push_Up(ch[root][1]);  //拆下后记得更新
        Push_Up(root);
        Splay(Get_Kth(root,l),0);
        Splay(Get_Kth(root,l+1),root);  //放在l之前
        Key_value=tmp;
        pre[Key_value]=ch[root][1];//这个不要忘记
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void Insert (int x,int P)
    {//在第x个数后面插入P
        Splay(Get_Kth(root,x+1),0);
        Splay(Get_Kth(root,x+2),root);
        NewNode(Key_value,ch[root][1],P);
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void Insert_Array (int pos,int tot)
    {//在第pos个数后插入tot个数
        for (int i=0;i<tot;i++)
    		scanf("%d",&data[i]);
        Splay(Get_Kth(root,pos+1),0);
        Splay(Get_Kth(root,pos+2),root);
        Build(Key_value,0,tot-1,ch[root][1]);
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void erase (int r)
    {//回收内存
        if(r)
        {
            s[++tot2]=r;
            erase(ch[r][0]);
            erase(ch[r][1]);
        }
    }
    
    void Delete (int x)
    {//删除第x个数
        Splay(Get_Kth(root,x),0);
        Splay(Get_Kth(root,x+2),root);
        erase(Key_value);
        pre[Key_value]=0;
        Key_value=0;
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void Delete_Array (int pos,int tot)
    {//从第pos个数开始连续删除tot个数
        Splay(Get_Kth(root,pos),0);
        Splay(Get_Kth(root,pos+tot+1),root);
        erase(Key_value);
        pre[Key_value]=0;
        Key_value=0;
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    void Make_Same (int pos,int tot,int c)
    {//从第pos个数连续开始的tot个数修改为c
        Splay(Get_Kth(root,pos),0);
        Splay(Get_Kth(root,pos+tot+1),root);
        Update_Same(Key_value,c);
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    
    int Get_Sum (int pos,int tot)
    {//求和
        Splay(Get_Kth(root,pos),0);
        Splay(Get_Kth(root,pos+tot+1),root);
        return sum[Key_value];
    }
    
    int Get_MaxSum (int pos,int tot)
    {//从pos开始连续tot个数中最大连续和
        Splay(Get_Kth(root,pos),0);
        Splay(Get_Kth(root,pos+tot+1),root);
        return mx[Key_value];
    }
    
    int Query_Min (int l,int r)
    {//查找区间最小
        Splay(Get_Kth(root,l),0);
        Splay(Get_Kth(root,r+2),root);
        return m[Key_value];
    } 
    
    int cnt=0;  //中序遍历输出,每次遍历之后需要将cnt置0
    //注意该函数需要知道数据规模,既全局变量n
    void Inorder (int r)   
    {
    	if (!r) return;
    	Push_Down(r);
    	Inorder(ch[r][0]);
    	if (cnt>=1 && cnt<=n)
    		printf(cnt<n?"%d ":"%d\n",key[r]);
    	cnt++;
    	Inorder (ch[r][1]);
    }
    
    char str[20];
    
    int main ()
    {  
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int m;
    	while (~scanf("%d%d",&n,&m))
    	{
    		Init_Array ();
    		while (m--)
    		{
    			int x,y,z;
    			scanf("%s",str);    
    			switch (str[2])  
    			{  
    			case 'S':  
    				scanf("%d%d", &x,&y);  
    				Insert_Array(x,y);
    				break;  
    			case 'L':    
    				scanf("%d%d", &x,&y);
    				Delete_Array(x,y);
    				break;
    			case 'K':
    				scanf("%d%d%d", &x,&y,&z);
    				Make_Same(x,y,z);
    				
    				break;
    			case 'V':     
                    scanf("%d%d", &x,&y);  
                    Reverse(x,x+y-1);
    				break;
    			case 'T':
    				scanf("%d%d", &x,&y);
    				printf("%d\n",Get_Sum(x,y));
    				break;
    			case 'X':
    				printf("%d\n",Get_MaxSum(1,size[root]-2));
    			}
    		}
    	}
    	return 0;
    }

[splay _ - _AC_ - _ - CSDN.NET]: http://blog.csdn.net/crazy_ac/article/details/8034190