首页 > 代码库 > BZOJ1500: [NOI2005]维修数列[splay ***]

BZOJ1500: [NOI2005]维修数列[splay ***]

2024-08-25 01:18:24   222人阅读

1500: [NOI2005]维修数列

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 12278  Solved: 3880
[Submit][Status][Discuss]

Description

技术分享

Input

输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

Output

对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。

Sample Input

9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

Sample Output

-1
10
1
10

 

太神了

splay维护序列

额外维护信息:rev翻转标记，tag修改标记，sum子树和，mx lm rm最大连续和那一套

update和paint和pushDown与线段树类似(修改之后翻转标记就可以忽略了)

build前注意

a[1]=a[n+2]=-INF;//防止计入mx中t[0].mx=t[0].lm=t[0].rm=-INF;t[0].sum=0;

加入哨兵节点

「注意update和更新父子关系」

INSERT：提取区间k+1,k+2把新序列建树然后加到k+2.lc上

DELETE：提取k+1,k+1+tot 递归删除k+1+tot.lc每个节点

MAKE-SAME：提取 打标记

REVERSE：提取 打标记

GET-SUM：提取 sum

MAX-SUM：根.mx

注意要回收节点编号，所以用nw()，建树每个节点必须分配一个编号，不能直接用下标了

 

kth的时候pushDown过了，splay和update就不用了

 

 

1.仿照前人的做法写了一份

技术分享
  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<cmath>  6 using namespace std;  7 typedef long long ll;  8 #define lc t[x].ch[0]  9 #define rc t[x].ch[1] 10 #define pa t[x].fa 11 const int N=5e5+5,INF=1e9; 12 int read(){ 13     char c=getchar();int x=0,f=1; 14     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} 15     while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} 16     return x*f; 17 } 18 int n,m,a[N],pos,tot,v; 19 char s[100]; 20 struct node{ 21     int ch[2],fa,size,v,rev,tag,sum,mx,lm,rm; 22 }t[N]; 23 int cnt,root; 24 inline int wh(int x){return t[pa].ch[1]==x;} 25 int st[N],top=0; 26 inline int nw(){ 27     int x; 28     if(top) x=st[top--];else x=++cnt; 29     lc=rc=pa=t[x].tag=t[x].rev=0; 30     t[x].size=1; 31     t[x].mx=t[x].sum=t[x].lm=t[x].rm=-INF; 32     return x;r 33 } 34 inline void update(int x){ 35     t[x].size=t[lc].size+t[rc].size+1; 36     t[x].sum=t[lc].sum+t[rc].sum+t[x].v; 37     t[x].mx=max(max(t[lc].mx,t[rc].mx), max(0,t[lc].rm)+t[x].v+max(0,t[rc].lm)); 38     t[x].lm=max(t[lc].lm,t[lc].sum+t[x].v+max(0,t[rc].lm)); 39     t[x].rm=max(t[rc].rm,t[rc].sum+t[x].v+max(0,t[lc].rm)); 40 } 41 inline void paint(int x){//reverse 42     if(!x) return; 43     t[x].rev^=1; 44     swap(lc,rc); 45     swap(t[x].lm,t[x].rm); 46 } 47 inline void paint(int x,int v){//make_same 48     if(!x) return; 49     t[x].v=v;t[x].sum=v*t[x].size; 50     t[x].lm=t[x].rm=t[x].mx=max(v,t[x].sum); 51     t[x].tag=1;t[x].rev=0; 52 } 53  54 inline void pushDown(int x){ 55     if(t[x].rev){ 56         if(lc) paint(lc); 57         if(rc) paint(rc); 58         t[x].rev=0; 59     } 60     if(t[x].tag){ 61         if(lc) paint(lc,t[x].v); 62         if(rc) paint(rc,t[x].v); 63         t[x].tag=0; 64     } 65 } 66 inline void rotate(int x){ 67     int f=t[x].fa,g=t[f].fa,c=wh(x); 68     if(g) t[g].ch[wh(f)]=x;t[x].fa=g; 69     t[f].ch[c]=t[x].ch[c^1];t[t[f].ch[c]].fa=f; 70     t[x].ch[c^1]=f;t[f].fa=x; 71     update(f);update(x); 72 } 73 inline void splay(int x,int tar){ 74     for(;t[x].fa!=tar;rotate(x)) 75         if(t[pa].fa!=tar) rotate(wh(pa)==wh(x)?pa:x); 76     if(tar==0) root=x; 77 } 78 void build(int l,int r,int x){ 79     int mid=(l+r)>>1; 80     t[x].v=a[mid]; 81     if(l==r){t[x].sum=t[x].lm=t[x].rm=t[x].mx=t[x].v;t[x].size=1;return;} 82     if(l<mid){lc=nw();t[lc].fa=x;build(l,mid-1,lc);} 83     if(mid<r){rc=nw();t[rc].fa=x;build(mid+1,r,rc);} 84     update(x);//printf("build %d %d %d  %d %d %d\n",l,r,t[x].sum,t[x].mx,t[lc].mx,t[rc].mx); 85 } 86 //int build(int l,int r){ 87 //    if(l>r) return 0; 88 //    int mid=(l+r)>>1,x=nw(); 89 //    lc=build(l,mid-1);rc=build(mid+1,r); 90 //    t[lc].fa=t[rc].fa=x; 91 //    t[x].v=a[mid]; 92 //    t[x].sum=t[x].lm=t[x].rm=t[x].mx=t[x].v;t[x].size=1; 93 //    update(x); 94 //    return x; 95 //} 96 int kth(int k){ 97     int x=root,ls=0; 98     while(x){ 99         pushDown(x);100         int _=ls+t[lc].size;101         if(_<k&&k<=_+1) return x;102         if(k<=_) x=lc;103         else ls=_+1,x=rc;104     }105     return -1;106 }107 void Insert(int k,int tot){108     for(int i=1;i<=tot;i++) a[i]=read();109     int p=kth(k+1);splay(p,0);110     int x=kth(k+2);splay(x,p);111     lc=nw();t[lc].fa=x;112     build(1,tot,lc);113     update(x);update(p);114 }115 void erase(int x){116     if(!x) return;117     st[++top]=x;118     if(lc) erase(lc);119     if(rc) erase(rc);120 }121 void Delete(int k,int tot){122     int p=kth(k);splay(p,0);123     int x=kth(k+tot+1);splay(x,p);124     erase(lc);125     t[lc].fa=0;lc=0;126     update(x);update(p);127 }128 void Make(int k,int tot,int v){129     int p=kth(k);splay(p,0);130     int x=kth(k+tot+1);splay(x,p);131     paint(lc,v);132     update(x);update(p);133 }134 void Reverse(int k,int tot){135     int p=kth(k);splay(p,0);136     int x=kth(k+tot+1);splay(x,p);137     paint(lc);138     update(x);update(p);139 }140 int Sum(int k,int tot){141     int p=kth(k);splay(p,0);142     int x=kth(k+tot+1);splay(x,p);143     return t[lc].sum;144 }145 int main(){146     n=read();m=read();147     for(int i=1;i<=n;i++) a[i+1]=read();a[1]=a[n+2]=-INF;148     t[0].mx=t[0].lm=t[0].rm=-INF;t[0].sum=0;149     root=nw();150     build(1,n+2,root);151     for(int i=1;i<=m;i++){152         scanf("%s",s);153         if(s[0]==‘I‘) pos=read(),tot=read(),Insert(pos,tot);154         else if(s[0]==‘D‘) pos=read(),tot=read(),Delete(pos,tot);155         else if(s[4]==‘-‘) pos=read(),tot=read(),v=read(),Make(pos,tot,v);156         else if(s[0]==‘R‘) pos=read(),tot=read(),Reverse(pos,tot);157         else if(s[0]==‘G‘) pos=read(),tot=read(),printf("%d\n",Sum(pos,tot));158         else if(s[3]==‘-‘) printf("%d\n",t[root].mx);159     }160 }
View Code

 

 

 

 

 

BZOJ1500: [NOI2005]维修数列[splay ***]


联系
我们