#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#define inf 2147483648
using namespace std;
struct Splay
{
	long long pre;
	long long ch[2];
	long long bh;
	long long number;
	long long lazy;
	long long size;
	long long lazynum;
	long long min;
}t[600005];
long long root,rf=0;
long long cnt;

void pushdown(long long a)
{
    if(a==0) return;
	t[a].lazy=t[a].lazy%2; 
	if(t[a].lazy==1)
	{
		long long swap=t[a].ch[0];
		t[a].ch[0]=t[a].ch[1];
		t[a].ch[1]=swap;
		if(t[a].ch[1]) t[t[a].ch[1]].lazy+=1;
		if(t[a].ch[0]) t[t[a].ch[0]].lazy+=1;
		t[a].lazy=0;
	}
	if(t[a].lazynum!=0)
	{
		t[a].number+=t[a].lazynum;
		t[a].min+=t[a].lazynum;
		if(t[a].ch[0]) t[t[a].ch[0]].lazynum+=t[a].lazynum;
		if(t[a].ch[1]) t[t[a].ch[1]].lazynum+=t[a].lazynum;
		t[a].lazynum=0;
	}
}

void update(long long a)
{
    pushdown(a);
	t[a].size=1;
	t[a].size+=t[t[a].ch[0]].size;
	t[a].size+=t[t[a].ch[1]].size;
	
	t[a].min=t[a].number;
	long long lm,rm;
	lm=rm=inf;
	if(t[a].ch[0]) lm=t[t[a].ch[0]].min+t[t[a].ch[0]].lazynum;
	if(t[a].ch[1]) rm=t[t[a].ch[1]].min+t[t[a].ch[1]].lazynum;
	if(t[a].min>lm) t[a].min=lm;
	if(t[a].min>rm) t[a].min=rm;
	
}

void insert(long long a,long long b)
{
	if(t[a].bh>t[b].bh)
	{
		if(t[a].ch[0]==0)
		{
			t[b].pre=a;
			t[a].ch[0]=b;
			update(b);
		}
		else
		{
			insert(t[a].ch[0],b);
		}
	}
	else
	{
		if(t[a].ch[1]==0)
		{
			t[b].pre=a;
			t[a].ch[1]=b;
			update(b);
		}
		else
		{
			insert(t[a].ch[1],b);
		}
	}
	update(a);
}


void rotate(long long a,long long type)
{
	long long fa=t[a].pre;
	long long gfa=t[fa].pre;
	
	if(fa==root) root=a;

	pushdown(a);
	
	t[a].pre=gfa;
	t[gfa].ch[t[gfa].ch[1]==fa]=a;
	
	long long son=t[a].ch[type];
	
	t[fa].ch[!type]=son;
	t[son].pre=fa;
	
	t[a].ch[type]=fa;
	t[fa].pre=a;
	
	update(fa);
	update(a);
}


void splay(long long a,long long b)
{
	while(t[a].pre!=b)
	{	
        pushdown(t[a].pre);
        pushdown(a);
		long long fa=t[a].pre;
		if(t[fa].pre==b)
        { 
            long long k;
            if(t[fa].ch[1]==a) k=1;
            else k=0;
            rotate(a,(k+1)%2);
        }
		else
		{
			long long gfa=t[fa].pre;
			long long apl=(t[fa].ch[1]==a);
			long long fapl=(t[gfa].ch[1]==fa);
			if(apl==fapl)
			{
				rotate(fa,(fapl+1)%2);
				rotate(a,(apl+1)%2);
			}
			else
			{
				rotate(a,(apl+1)%2);
				rotate(a,(fapl+1)%2);
			}
		}
	}
}

long long find(long long a,long long b)
{
	pushdown(a);
	long long lsize; 
	if(t[a].ch[0]!=0) lsize=t[t[a].ch[0]].size;
	else lsize=0;
	if(lsize+1>b) return find(t[a].ch[0],b);
	if(lsize+1==b)
	{
		return t[a].bh;
	}
	if(lsize+1<b) return find(t[a].ch[1],b-lsize-1);
}

void reverse(long long a,long long b)
{
	long long afind=find(root,a-1);
	splay(afind,rf);
	long long bfind=find(root,b+1);
	splay(bfind,root);
	t[t[bfind].ch[0]].lazy++;
}

void remove(long long a)
{
	long long afind=find(root,a-1);
	splay(afind,rf);
	long long bfind=find(root,a+1);
	splay(bfind,root);
	t[bfind].ch[0]=0;
	update(bfind);
	update(afind);
}

void newsplay(long long a)
{
    t[a].ch[0]=t[a].ch[1]=t[a].lazy=t[a].lazynum=0;
	t[a].size=1;
	t[a].number=inf;
	t[a].min=inf;
	t[a].bh=a;
}

void add(long long a,long long b)
{
    cnt++;
    newsplay(cnt);
    t[cnt].bh=cnt;
    t[cnt].number=b;
    t[cnt].min=b;
	long long afind=find(root,a);
	splay(afind,rf);
	afind=find(root,a+1);
	splay(afind,root);
	t[afind].ch[0]=cnt;
	t[cnt].pre=afind;
	update(cnt);
	update(afind);
	update(t[afind].pre);
}

void revolve(long long a,long long b,long long c)
{
	c=c%(b-a+1);
	while(c<0) c+=(b-a+1);
	if(c==0) return;
	reverse(a,b);
	reverse(a,a+c-1);
	reverse(a+c,b);
}

void inorder(long long a)
{
	pushdown(a);
	if(t[a].ch[0]!=0) inorder(t[a].ch[0]);
	if(t[a].ch[1]!=0) inorder(t[a].ch[1]);
}

void addlazynum(long long a,long long b,long long c)
{
    long long afind=find(root,a-1);
    long long bfind=find(root,b+1);
    splay(afind,rf);
    splay(bfind,root);
    t[t[bfind].ch[0]].lazynum+=c;
    update(t[bfind].ch[0]);
    update(bfind);
    update(afind);
}

long long getmin(long long a,long long b)
{
    long long afind=find(root,a-1);
    splay(afind,rf);
    long long bfind=find(root,b+1);
    splay(bfind,root);
    pushdown(afind);
    pushdown(bfind);
    return t[t[bfind].ch[0]].min;
}

int main()
{
	long long a;
	cin>>a;
	cnt=a+1;
	root=1;
	newsplay(1);   
	for(long long i=2;i<=a+1;i++)
	{
		cin>>t[i].number;
		t[i].ch[0]=t[i].ch[1]=t[i].lazy=t[i].lazynum=0;
		t[i].size=1;
		t[i].min=t[i].number;
		t[i].bh=i;
		insert(root,i);
	}
	
	newsplay(a+2);
	insert(root,a+2);
	cnt=a+2;
	
	long long czs;
	cin>>czs;

	
	for(long long i=0;i<czs;i++)
	{
        
        char op[100];
        cin>>op;
        long long x,y,z;
        if(strcmp(op,"MIN")==0)
        {
            cin>>x>>y;
            cout<<getmin(x+1,y+1)<<endl;
        }
        else if(strcmp(op,"ADD")==0)
        {
            cin>>x>>y>>z;
            addlazynum(x+1,y+1,z);
        }
        else if(strcmp(op,"INSERT")==0)
        {
            cin>>x>>y;
            add(x+1,y);
        }
        else if(strcmp(op,"REVERSE")==0)
        {
            cin>>x>>y;
            reverse(x+1,y+1);
        }
        else if(strcmp(op,"REVOLVE")==0)
        {
            cin>>x>>y>>z;
            revolve(x+1,y+1,z);
        }
        else if(strcmp(op,"DELETE")==0)
        {
            cin>>x;
            remove(x+1);
        }
    }
    system("pause");
	return 0;
}

• Re:求各路大神帮忙看看哪里有问题……过了所有能找到的数据，但是WA (23) yanph2003 2016-04-07 14:21:56
  • Re:求各路大神帮忙看看哪里有问题……过了所有能找到的数据，但是WA (4514) chenyuqi 2016-04-07 15:54:39