首页 > 代码库 > [NOI2005]维修数列
[NOI2005]维修数列
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
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
10
1
10
题解：
splay，几乎所有模式都在里面
注意这个splay维护的是位置
插入：将第pos旋到根，第pos+1(名次树操作)旋到根的右子树
这里的插入用了一种二分的方法，可以保证有序，且可以直接反转
删除：将第pos旋到根，第pos+tot+1旋到根的右子树
如果用了内存池还要递归回收（详见erase）
反转：留下反转标记，每次直接交换左右节点
修改同上，注意0
求和直接维护
求最大子序列和有点复杂，维护节点最大子序列和，右端最大和，左端最大和，详见（pushdown）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int MAXN=500010; 7 int tot2,tot1,s[MAXN],pre[MAXN],ch[MAXN][2],key[MAXN],sum[MAXN],maxsum[MAXN],lx[MAXN],rx[MAXN],a[MAXN]; 8 int size[MAXN],same[MAXN],root,n,m; 9 bool rev[MAXN]; 10 int gi() 11 { 12 char ch=getchar();int s=0;int sign=1; 13 while (ch<‘0‘||ch>‘9‘) 14 {if (ch==‘-‘) sign=-1;ch=getchar();} 15 while (ch>=‘0‘&&ch<=‘9‘) 16 {s=s*10+ch-‘0‘;ch=getchar();} 17 return s*sign; 18 } 19 void NewNode(int &r,int fa,int k) 20 { 21 if (tot2) r=s[tot2--]; 22 else 23 r=++tot1; 24 pre[r]=fa; 25 ch[r][0]=ch[r][1]=0; 26 key[r]=k; 27 sum[r]=k; 28 rev[r]=same[r]=0; 29 lx[r]=rx[r]=maxsum[r]=k; 30 size[r]=1; 31 } 32 void pushup(int x) 33 { 34 int lson=ch[x][0],rson=ch[x][1]; 35 size[x]=size[lson]+size[rson]+1; 36 sum[x]=sum[lson]+sum[rson]+key[x]; 37 lx[x]=max(lx[lson],sum[lson]+key[x]+max(0,lx[rson])); 38 rx[x]=max(rx[rson],sum[rson]+key[x]+max(0,rx[lson])); 39 maxsum[x]=max(0,rx[lson])+key[x]+max(0,lx[rson]); 40 maxsum[x]=max(maxsum[lson],max(maxsum[x],maxsum[rson])); 41 } 42 void update_same(int x,int c); 43 void update_Reverse(int x); 44 void pushdown(int x) 45 { 46 if (same[x]) 47 { 48 update_same(ch[x][0],key[x]); 49 update_same(ch[x][1],key[x]); 50 same[x]=0; 51 } 52 if (rev[x]) 53 { 54 update_Reverse(ch[x][0]); 55 update_Reverse(ch[x][1]); 56 rev[x]=0; 57 } 58 } 59 void build(int &x,int l,int r,int fa) 60 { 61 if (l>r) return; 62 int mid=(l+r)/2; 63 NewNode(x,fa,a[mid]); 64 build(ch[x][0],l,mid-1,x); 65 build(ch[x][1],mid+1,r,x); 66 pushup(x); 67 } 68 int getkth(int r,int k) 69 { 70 pushdown(r); 71 int x=size[ch[r][0]]+1; 72 if (k==x) return r; 73 if (k<x) getkth(ch[r][0],k); 74 else getkth(ch[r][1],k-x); 75 } 76 void rotate(int x,bool t) 77 { 78 int y=pre[x]; 79 pushdown(y);pushdown(x); 80 ch[y][!t]=ch[x][t]; 81 pre[ch[x][t]]=y; 82 if (pre[y]) 83 ch[pre[y]][ch[pre[y]][1]==y]=x; 84 pre[x]=pre[y]; 85 ch[x][t]=y; 86 pre[y]=x; 87 pushup(y); 88 } 89 void splay(int x,int goal) 90 { 91 pushdown(x); 92 while (pre[x]!=goal) 93 { 94 if (pre[pre[x]]==goal) 95 { 96 pushdown(pre[x]); 97 pushdown(x); 98 rotate(x,ch[pre[x]][0]==x); 99 } 100 else 101 { 102 pushdown(pre[pre[x]]); 103 pushdown(pre[x]); 104 pushdown(x); 105 int y=pre[x],kind=ch[pre[y]][0]==y; 106 if (ch[y][kind]==x) 107 { 108 rotate(x,!kind); 109 rotate(x,kind); 110 } 111 else 112 { 113 rotate(y,kind); 114 rotate(x,kind); 115 } 116 } 117 } 118 pushup(x); 119 if (goal==0) root=x; 120 } 121 void insert(int pos,int tot) 122 {int i; 123 for (i=1; i<=tot; i++) 124 { 125 a[i]=gi(); 126 } 127 splay(getkth(root,pos+1),0); 128 splay(getkth(root,pos+2),root); 129 build(ch[ch[root][1]][0],1,tot,ch[root][1]); 130 pushup(ch[root][1]); 131 pushup(root); 132 } 133 void erase(int r) 134 { 135 if (!r) return ; 136 s[++tot2]=r; 137 erase(ch[r][0]); 138 erase(ch[r][1]); 139 } 140 void Delete(int pos,int tot) 141 { 142 splay(getkth(root,pos),0); 143 splay(getkth(root,pos+tot+1),root); 144 erase(ch[ch[root][1]][0]); 145 pre[ch[ch[root][1]][0]]=0; 146 ch[ch[root][1]][0]=0; 147 pushup(ch[root][1]); 148 pushup(root); 149 } 150 void update_same(int x,int c) 151 { 152 if (!x) return; 153 key[x]=c; 154 sum[x]=size[x]*c; 155 lx[x]=rx[x]=maxsum[x]=max(c,size[x]*c); 156 same[x]=1; 157 } 158 void Make_same(int pos,int tot,int c) 159 { 160 splay(getkth(root,pos),0); 161 splay(getkth(root,pos+tot+1),root); 162 update_same(ch[ch[root][1]][0],c); 163 pushup(ch[root][1]); 164 pushup(root); 165 } 166 void update_Reverse(int x) 167 { 168 if (!x) return; 169 swap(ch[x][0],ch[x][1]); 170 swap(lx[x],rx[x]); 171 rev[x]^=1; 172 } 173 void Reverse(int pos,int tot) 174 { 175 splay(getkth(root,pos),0); 176 splay(getkth(root,pos+tot+1),root); 177 update_Reverse(ch[ch[root][1]][0]); 178 pushup(ch[root][1]); 179 pushup(root); 180 } 181 int getsum(int pos,int tot) 182 { 183 splay(getkth(root,pos),0); 184 splay(getkth(root,pos+tot+1),root); 185 return sum[ch[ch[root][1]][0]]; 186 } 187 int Max_sum() 188 { 189 splay(getkth(root,1),0); 190 splay(getkth(root,size[root]),root); 191 return maxsum[ch[ch[root][1]][0]]; 192 } 193 int main() 194 {int i,j,x,y,z; 195 char str[101]; 196 cin>>n>>m; 197 for (i=1; i<=n; i++) 198 { 199 a[i]=gi(); 200 } 201 lx[root]=rx[root]=maxsum[root]=-2e9; 202 NewNode(root,0,-1); 203 NewNode(ch[root][1],root,-1); 204 build(ch[ch[root][1]][0],1,n,ch[root][1]); 205 pushup(ch[root][1]); 206 pushup(root); 207 for (i=1; i<=m; i++) 208 { 209 scanf("%s",str); 210 if (str[0]==‘I‘) 211 { 212 x=gi();y=gi(); 213 insert(x,y); 214 } 215 else if (str[0]==‘D‘) 216 { 217 x=gi();y=gi(); 218 Delete(x,y); 219 } 220 else if (str[0]==‘M‘&&str[4]==‘-‘) 221 { 222 x=gi();y=gi();z=gi(); 223 Make_same(x,y,z); 224 } 225 else if (str[0]==‘R‘) 226 { 227 x=gi(); 228 y=gi(); 229 Reverse(x,y); 230 } 231 else if (str[0]==‘G‘) 232 { 233 x=gi(); 234 y=gi(); 235 printf("%d\n",getsum(x,y)); 236 } 237 else if (str[0]==‘M‘&&str[3]==‘-‘) 238 { 239 printf("%d\n",Max_sum()); 240 } 241 } 242 }
[NOI2005]维修数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。