疯狂的块状链表……
我写个半成品程序放这儿坑着……不知道哪天会填坑……
感觉写到快崩溃了……
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;
}
