题目描述
输入格式
输入的第1行包含两个数N 和M(M ≤20 000),N 表示初始时数列中数的个数,M表示要进行的操作数目。第2行包含N个数字,描述初始时的数列。以下M行,每行一条命令,格式参见问题描述中的表格。任何时刻数列中最多含有500 000个数,数列中任何一个数字均在[-1 000, 1 000]内。插入的数字总数不超过4 000 000个,输入文件大小不超过20MBytes。
输出格式
对于输入数据中的GET-SUM和MAX-SUM操作,向输出文件依次打印结果,每个答案(数字)占一行。
题目解析
说实话,splay真是蛮好玩的。虽然有点效率问题而且调试麻烦,但是只要使用得当,姿势正确,功能还是十分强大的。
作为我切的第一道数据结构题,维修数列这道题教我做人……据说这是NOI史上考过最BT的数据结构题,全面考察了splay的各种操作,堪称splay的终极BOSS。我也真是手好,一上来居然就点进了这道题目。好吧,下面说说这道题。
首先我们定义splay上的基本操作 extract(l,r) ,表示提取开区间(l,r),即闭区间[l+1,r-1]到一颗完整的子树中,这样可以方便地统计答案。具体操作是,先将元素l旋转到根,再将元素r旋转到根下。根据平衡树的性质,此时根节点(l)的右儿子(r)的左子树就对应区间[l+1,r-1]。方便起见,我们称这课子树为Ta,其根节点为root(Ta)。
开始之前,不要忘了建一个首结点和尾结点。
操作1,extract(posi,posi+1),此时Ta为空。先递归建一棵小型平衡树,然后把这棵子树作为Ta接上去就可以了。操作2,extract(posi-1,posi+tot),把Ta删掉。由于插入的数可能很多,为了防止爆内存,建议空间回收,即将删掉的结点建一个栈,重复利用。操作3/4,extract(posi-1,posi+tot),在root(Ta)上打标记。向下走时下传标记。在下传标记前,该结点的值就应修改完毕,标记唯一的作用是用来下传。操作5,extract(posi-1,posi+tot),增加一个属性sum,记录子树点权之和。询问时直接输出sum(root(Ta))即可。
本题的重难点在于操作6。最大和子序列在静态或者带修改时都好做,但变成带插入时情况就没那么简单了。这里就运用了splay自身的灵活性。维护四个量,vmax,lmax,rmax,totmax,lmax表示从以该结点为根的子树所代表的区间的左端开始的最大和,rmax表示从区间的右端开始的最大和,totmax表示整一段区间的最大和,这样转移上去就得到最大子序列和(totmax(root(Ta)))。但这里有一个小问题,如果这个序列中的所有值都小于0,那么用这个方法会直接返回0(不取任何元素),然而在这里是不可取的(必须要取一个)。所以还要维护vmax,为子树中最大值,若区间中最大值小于0,则直接返回vmax(root(Ta))。
至此,本题的难点都被解决,只要在实现时细心一点就好。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 |
/************************************************************** Problem: 1500 User: frank_c1 Language: C++ Result: Accepted Time:4976 ms Memory:55976 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ #define LC ch[x][0] #define RC ch[x][1] #define SC ch[ch[rt][1]][0] const int maxn=1000005; const int INF=(int)(1e9)+100; int fa[maxn],ch[maxn][2]; int sz[maxn],val[maxn],flip[maxn],all[maxn],vsum[maxn]; int lmx[maxn],rmx[maxn],mx[maxn],vmx[maxn]; int seq[maxn],stk[maxn]; int rt,idx,top; inline int dir(int x) {return ch[fa[x]][1]==x;} inline void rep(int x,int v) { all[x]=val[x]=vmx[x]=v; vsum[x]=sz[x]*v; lmx[x]=rmx[x]=mx[x]=max(0,vsum[x]); } inline void rev(int x) { flip[x]^=1; swap(LC,RC); swap(lmx[x],rmx[x]); } inline void pd(int x) { if(all[x]!=-INF) { if(LC) rep(LC,all[x]); if(RC) rep(RC,all[x]); all[x]=-INF; } if(flip[x]) { if(LC) rev(LC); if(RC) rev(RC); flip[x]=0; } } inline void pu(int x) { sz[x]=sz[LC]+sz[RC]+1; vsum[x]=vsum[LC]+vsum[RC]+val[x]; vmx[x]=max(val[x],max(vmx[LC],vmx[RC])); lmx[x]=max(lmx[LC],vsum[LC]+val[x]+lmx[RC]); rmx[x]=max(rmx[RC],vsum[RC]+val[x]+rmx[LC]); mx[x]=max(rmx[LC]+val[x]+lmx[RC],max(rmx[x],lmx[x])); mx[x]=max(mx[x],max(mx[LC],mx[RC])); } inline void rot(int x) { int d=dir(x)^1,p=fa[x]; pd(p);pd(x); ch[p][d^1]=ch[x][d]; fa[ch[x][d]]=p; fa[x]=fa[p]; if(fa[x]) ch[fa[p]][dir(p)]=x; ch[x][d]=p;fa[p]=x;pu(p); } inline void splay(int x,int goal=0) { pd(x); while(fa[x]!=goal) { pd(fa[fa[x]]); pd(fa[x]);pd(x); if(fa[fa[x]]==goal) rot(x); else if(dir(x)!=dir(fa[x])) rot(x),rot(x); else rot(fa[x]),rot(x); } pu(x);if(goal==0) rt=x; } inline void rto(int k,int goal=0) { int x=rt;pd(x); for(;x && k!=sz[LC]+1;) { if(k<sz[LC]+1) x=LC; else {k-=sz[LC]+1;x=RC;} pd(x); } if(x) splay(x,goal); } inline void newnode(int& x,int v,int p) { if(top) x=stk[top--]; else x=++idx; LC=RC=0;sz[x]=1; fa[x]=p;val[x]=vsum[x]=vmx[x]=v; flip[x]=0;all[x]=-INF; lmx[x]=rmx[x]=mx[x]=max(val[x],0); } void build(int& x,int l,int r,int p) { if(l>r) return; int mid=(l+r)>>1; newnode(x,seq[mid],p); build(LC,l,mid-1,x); build(RC,mid+1,r,x); pu(x); } inline void init() { rt=idx=top=0; vmx[0]=-INF; newnode(rt,-INF,0); newnode(ch[rt][1],-INF,rt); build(SC,1,seq[0],ch[rt][1]); pu(rt); } void del(int x) { if(!x) return; stk[++top]=x; del(LC);del(RC); } void print(int x) { if(x) { pd(x); print(LC); if(val[x]!=-INF) printf("%d ",val[x]); print(RC); } } char op[10]; int main() { int n,m,cnt,k,tot,c; read(n);read(m); seq[0]=0; REP(i,1,n) read(seq[++seq[0]]); cnt=n;init(); REP(i,1,m) { scanf("%s",op); if(strcmp(op,"INSERT")==0) { read(k);read(tot); seq[0]=0; REP(i,1,tot) read(seq[++seq[0]]); rto(k+1);rto(k+2,rt); build(SC,1,seq[0],ch[rt][1]); pu(ch[rt][1]);pu(rt); cnt+=tot; } if(strcmp(op,"DELETE")==0) { read(k);read(tot); rto(k);rto(k+1+tot,rt); del(SC);SC=0; pu(ch[rt][1]);pu(rt); cnt-=tot; } if(strcmp(op,"MAKE-SAME")==0) { read(k);read(tot);read(c); rto(k);rto(k+1+tot,rt); rep(SC,c); pu(ch[rt][1]);pu(rt); } if(strcmp(op,"REVERSE")==0) { read(k);read(tot); rto(k);rto(k+1+tot,rt); rev(SC); pu(ch[rt][1]);pu(rt); } if(strcmp(op,"GET-SUM")==0) { read(k);read(tot); rto(k);rto(k+1+tot,rt); printf("%d\n",vsum[SC]); } if(strcmp(op,"MAX-SUM")==0) { rto(1);rto(cnt+2,rt); if(vmx[SC]<=0) printf("%d\n",vmx[SC]); else printf("%d\n",mx[SC]); } } return 0; } |
-
章可循