Lvat_s Blog

疯狂的块状链表……

我写个半成品程序放这儿坑着……不知道哪天会填坑……

感觉写到快崩溃了……

jcvb写的完整版也就我这么长……但我只写了一半……orzorz

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

struct List{
long long cur[1105],cover,rev,tag,sum,mx,mn,siz;
List *prev,*next;
List(List *pre,List *nex){
siz=0;
mx=-21000000000ll;
mn=21000000000ll;
sum=0;
rev=0;
tag=0;
cover=-21000000000ll;
prev=pre;
next=nex;
}
void Renew(long long k){
mx=max(mx,k);
mn=min(mn,k);
sum+=k;
}
void Fix(){
prev->next=this;
next->prev=this;
}
}*root,*Null=new List(Null,Null);

int m,n,block_size;
long long a[100005],tmp[1105];

void Read(long long &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

void PushTag(List *p){
if(p->tag){
	for(int i=0;i<p->siz;i++)p->cur[i]+=p->tag;
	p->tag=0;
}
}

void PushCover(List *p){
if(p->cover!=-21000000000ll){
	for(int i=0;i<p->siz;i++)p->cur[i]=p->cover;
	p->cover=-21000000000ll;
}
}

void PushRev(List *p){
if(p->rev){
	for(int i=0;i<p->siz/2;i++)swap(p->cur[i],p->cur[p->siz-i-1]);
	p->rev=0;
}
}

void Pushdown(List *p){
PushTag(p);
PushCover(p);
PushRev(p);
}

void CopyTags(List *p,List *q){
p->cover=q->cover;
p->tag=q->tag;
p->rev=q->rev;
}

List* Split(List *lis,int k){
List *p=new List(lis,lis->next);
lis->next=p;
lis->Fix();
p->Fix();
PushRev(lis);
CopyTags(p,lis);
lis->mx=-21000000000ll;
lis->mn=21000000000ll;
lis->sum=0;
for(int i=0;i<=k;i++){
	lis->Renew(lis->cur[i]);
}
lis->siz=k+1;
if(p->cover)return p;
for(int i=k+1;i<lis->siz;i++){
	p->cur[p->siz++]=lis->cur[i];
	p->Renew(lis->cur[i]);
}
return p;
}

List* Merge(List *p,List *q){
p->next=q;
q->prev=p;
p->Fix();
q->Fix();
Pushdown(p);
Pushdown(q);
for(int i=0;i<q->siz;i++){
	p->cur[p->siz++]=q->cur[i];
	p->Renew(q->cur[i]);
}
return p;
}

void Swap(List *p,List *q){
p->prev->next=q;
q->next->prev=p;
p->next->prev=q;
q->prev->next=p;
swap(p->next,q->next);
swap(p->prev,q->prev);
}

pair<List*,int> Location(int pos){
List *i;
for(i=root;i!=Null && pos>i->siz;pos-=i->siz,i=i->next);
return make_pair(i,pos-1);
}
///Wo Mei You You Hua block_size;
void Insert(int pos,long long val){
pair<List*,int> Real=Location(pos);
Real.second++;
Pushdown(Real.first);
for(int i=Real.first->siz;i>Real.second;i--){
	Real.first->cur[i]=Real.first->cur[i-1];
}
Real.first->siz++;
Real.first->cur[Real.second]=val;
Real.first->Renew(val);
if(Real.first->siz>2*block_size){Split(Real.first,Real.first->siz/2);}
}

void Delete(int pos){
pair<List*,int> Real=Location(pos);
Pushdown(Real.first);
Real.first->mx=-2100000000ll;
Real.first->mn=21000000000ll;
Real.first->sum=0;
for(int i=0;i<Real.second;i++)Real.first->Renew(Real.first->cur[i]);
for(int i=Real.second+1;i<Real.first->siz;i++){
	Real.first->Renew(Real.first->cur[i]);
	Real.first->cur[i-1]=Real.first->cur[i];
}
Real.first->siz--;
if(Real.first->siz<block_size/2){
	if(Real.first->next!=Null){Merge(Real.first,Real.first->next);}
	else {
		if(Real.first->prev!=Null){Merge(Real.first->prev,Real.first);}
	}
}
}

void Reverse(int l,int r){
pair<List*,int> R1=Location(l),R2=Location(r);
Pushdown(R1.first);
Pushdown(R2.first);
List *p=Split(R1.first,R1.second),*q=Split(R2.first,R2.second)->prev;
int flag=0;
for(List *i=p;i!=q;i=i->next){i->rev^=1;}
for(;p!=q && p!=q->next;p=p->next,q=q->prev)Swap(p,q);
}

void True_rotate(List *lis,int k){
int cnt=0,Circle=lis->siz;
for(int i=0;i<Circle;i++){
	tmp[(++cnt+k-1)%Circle+1]=lis->cur[i];
}
for(int i=0;i<Circle;i++){
	lis->cur[i]=tmp[i-k+1];
}
}

void Rotate(int l,int r,int k){
pair<List*,int> R1=Location(l),R2=Location(r);
if(R1.first==R2.first){
	List *p=Split(R1.first,R1.second-1),*q=Split(R1.first->next,R2.second-R1.second+1)->prev;
	p=Merge(p,q);
	True_rotate(p,k);
	return;
}
if(R1.first->next==R2.first){
    List *p=Split(R1.first,R1.second-1),*q=Split(R2.first,R2.second)->prev;
	p=Merge(p,q);
	True_rotate(p,k);
	return;
}

}

void Add(int l,int r,long long v){

}

void Cover(int l,int r,long long val){

}

long long Sum(int l,int r){}

long long MinAbs(int l,int r){}

long long PrevNext(int l,int r,long long val){}

long long Kth(int l,int r,int k){}

int Rank(int l,int r,long long val){}

int main(){
freopen("3337.in","r",stdin);
freopen("3337.out","w",stdout);
Read(n);
for(int i=1;i<=n;i++){
	Read(a[i]);
}
block_size=(int)sqrt((double)n);
root=new List(Null,Null);
List *p=root;
int Count=0;
for(int i=1;i<=n;i++){
if((i-1)%block_size==0 && i!=1){
	p->next=new List(p,Null);
	p->siz=Count;
	p=p->next;
	Count=0;
}
p->Renew(a[i]);
p->cur[Count++]=a[i];
}
p->siz=Count;
Read(m);
while(m--){
	int opt,l,r,k;
	long long v;
	Read(opt);
	if(opt==1){
		Read(k);Read(v);
		Insert(k,v);
	}
	if(opt==2){
		Read(k);
		Delete(k);
	}
	if(opt==3){
		Read(l);Read(r);
		Reverse(l,r);
	}
	if(opt==4){
		Read(l);Read(r);Read(k);
		Rotate(l,r,k);
	}
	if(opt==5){
		Read(l);Read(r);Read(v);
		Add(l,r,v);
	}
	if(opt==6){
		Read(l);Read(r);Read(v);
		Cover(l,r,v);
	}
	if(opt==7){
		Read(l);Read(r);
		printf("%lld\n",Sum(l,r));
	}
	if(opt==8){
		Read(l);Read(r);
		printf("%lld\n",MinAbs(l,r));
	}
	if(opt==9){
		Read(l);Read(r);Read(v);
		printf("%lld\n",PrevNext(l,r,v));
	}
	if(opt==10){
		Read(l);Read(r);Read(k);
		printf("%lld\n",Kth(l,r,k));
	}
	if(opt==11){
		Read(l);Read(r);Read(v);
		printf("%d\n",Rank(l,r,v));
	}
}
return 0;
}