1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MB
[ 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
HINT
Source
入门题 涵盖splay基本所有操作，不会爆int，1000*50000 我对平衡树还是不很了解 主要是maxsum怎么求 其实就像线段树，左右维护一个左子集最大，右子集最大，合并信息就行了 mx[x] = max( max(mx[l],mx[r]), rx[l]+v[x]+lx[r] );
lx[x] = max( lx[l], sum[l]+v[x]+lx[r] );
进行区间修改的时候，把左端点转到根节点，右端点转到根节点的右儿子，区间就在根节点的右儿子的左子树里面 事实上队列只是用来节约空间
#include<iostream>
#include<cstdio>
#include<queue>
#define inf 1000000000
const int N = 1000000 + 5;
using namespace std;
int n,m,root,cnt,a[N],id[N],fa[N],c[N][2],sum[N],siz[N],v[N],mx[N],lx[N],rx[N];
bool flag[N],rev[N];
queue<int> q;
void update( int x ){
int l = c[x][0], r = c[x][1];
sum[x] = sum[l] + sum[r] + v[x];
siz[x] = siz[l] + siz[r] + 1;
mx[x] = max(max(mx[l],mx[r]),rx[l]+v[x]+lx[r]);
lx[x] = max(lx[l],sum[l]+v[x]+lx[r]);
rx[x] = max(rx[r],sum[r]+v[x]+rx[l]);
}
void pushdown( int x ){
int l = c[x][0], r = c[x][1];
if( flag[x] ){
rev[x] = flag[x] = 0;
if( l ) flag[l] = 1, v[l] = v[x], sum[l] = v[l]*siz[l];
if( r ) flag[r] = 1, v[r] = v[x], sum[r] = v[r]*siz[r];
if( v[x] >= 0 ){
if( l ) lx[l] = rx[l] = mx[l] = sum[l];
if( r ) lx[r] = rx[r] = mx[r] = sum[r];
} else{
if( l ) lx[l] = rx[l] = 0, mx[l] = v[x];
if( r ) lx[r] = rx[r] = 0, mx[r] = v[x];
}
}
if( rev[x] ){
rev[l] ^= 1; rev[r] ^= 1; rev[x] = 0;
swap( c[l][0], c[l][1] ); swap( c[r][0], c[r][1] );
swap( lx[l], rx[l] ); swap( rx[r], lx[r] );
}
}
void rotate( int x, int &k ){
int y = fa[x], z = fa[y], l, r;
l = (c[y][0]!=x); r = l^1;
if( y == k ) k = x;
else c[z][c[z][1]==y] = x;
fa[x] = z; fa[y] = x; fa[c[x][r]] = y;
c[y][l] = c[x][r]; c[x][r] = y;
update(y); update(x);
}
void splay( int x, int &k ){
while( x != k ){
int y = fa[x], z = fa[y];
if( y != k ){
if( c[y][0]==x^c[z][0]==y ) rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}//**/
int find( int x, int rank ){
pushdown(x);
if( siz[c[x][0]]+1 == rank ) return x;
if( siz[c[x][0]] >= rank ) return find(c[x][0],rank);
return find(c[x][1],rank-siz[c[x][0]]-1);
}
void clear( int x ){
if( !x ) return;
clear(c[x][0]); clear(c[x][1]); q.push(x);
fa[x] = c[x][0] = c[x][1] = flag[x] = rev[x] = 0;
}
int move( int k, int tot ){
int x = find(root,k), y = find(root,k+tot+1);
splay(x,root); splay(y,c[x][1]);
return c[y][0];
}
void query( int k, int tot ){
int x = move( k, tot );
printf("%d\n", sum[x]);
}
void delet( int k, int tot ){
int x = move(k,tot), y = fa[x];
clear(x); c[y][0] = 0;
update(y); update(fa[y]);
}
void modify( int k, int tot, int val ){
int x = move(k,tot), y = fa[x];
v[x] = val; flag[x] = 1; sum[x] = siz[x]*val;
if( val >= 0 ) lx[x] = rx[x] = mx[x] = sum[x];
else lx[x] = rx[x] = 0, mx[x] = val;
update(y); update(fa[y]);
}
void rever( int k, int tot ){
int x = move(k,tot), y = fa[x];
if( !flag[x] ){
rev[x] ^= 1;
swap(c[x][0],c[x][1]);
swap(lx[x],rx[x]);
update(y); update(fa[y]);
}
}
void build( int l, int r, int f ){
if( l > r ) return;
int mid = (l+r)>>1, now = id[mid], last = id[f];
if( l == r ){
mx[now] = sum[now] = a[r]; siz[now] = 1;
rev[now] = flag[now] = 0;
lx[now] = rx[now] = (a[l]) ? a[l] : 0;
} else build( l, mid-1, mid ), build( mid+1, r, mid );
v[now] = a[mid]; fa[now] = last; update(now); c[last][mid>=f] = now;
}
void insert( int k, int tot ){
for( int i = 1; i <= tot; i++ ) scanf("%d", &a[i]);
for( int i = 1; i <= tot; i++ ) if(!q.empty()) id[i] = q.front(),q.pop(); else id[i] = ++cnt;
build( 1, tot, 0 ); int f = id[(tot+1)>>1];
int x = find(root,k+1), y = find(root,k+2);
splay( x, root ); splay( y, c[x][1] );
c[y][0] = f; fa[f] = y;
update(y); update(x);
}
int main(){
scanf("%d%d", &n, &m);
mx[0] = a[1] = a[n+2] = -inf;
for( int i = 1; i <= n ; i++ ) scanf("%d", &a[i+1]);
for( int i = 1; i <= n+2; i++ ) id[i] = i;
build(1,n+2,0); root = (n+3)>>1; cnt = n+2;
while(m--){
int k,tot,val;char ch[10];
scanf("%s",ch);
if(ch[0]=='I')scanf("%d%d", &k, &tot),insert(k,tot);
if(ch[0]=='D')scanf("%d%d", &k, &tot),delet(k,tot);
if(ch[0]=='M'){
if(ch[2]=='X')printf("%d\n",mx[root]);
else scanf("%d%d%d", &k, &tot, &val),modify(k,tot,val);
}
if(ch[0]=='R')scanf("%d%d", &k, &tot),rever(k,tot);
if(ch[0]=='G')scanf("%d%d", &k, &tot),query(k,tot);
}
return 0;
}
大家不要看yjq打游戏，他这么叼怎么没有进国家队呢 总结