先是维修数列
题解看这里，但是我写的跑得很慢
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, idx[500005], a[500005], rot=0, uu, vv, sta[500005], din, ww, cnt;
const int oo=0x3f3f3f3f;
char ss[25];
struct Splay{
int zdz[500005], sum[500005], lma[500005], rma[500005], siz[500005], val[500005];
int s[500005][2], fa[500005];
bool tag[500005], rev[500005];
void clr(int x){
zdz[x] = sum[x] = lma[x] = rma[x] = siz[x] = val[x] = s[x][0] = s[x][1] = fa[x] = 0;
tag[x] = rev[x] = 0;
}
int gx(int x){
return s[fa[x]][1]==x;
}
void recycle(int x){
if(s[x][0]) recycle(s[x][0]);
if(s[x][1]) recycle(s[x][1]);
sta[++din] = x;
clr(x);
}
void upd(int x){
int l=s[x][0], r=s[x][1];
sum[x] = sum[l] + sum[r] + val[x];
siz[x] = siz[l] + siz[r] + 1;
zdz[x] = max(max(zdz[l], zdz[r]), lma[r]+val[x]+rma[l]);
lma[x] = max(lma[l], sum[l]+val[x]+lma[r]);
rma[x] = max(rma[r], sum[r]+val[x]+rma[l]);
}
void build(int l, int r, int f){
int mid=(l+r)>>1, now=idx[mid], pre=idx[f];
if(l==r){
clr(now);
zdz[now] = sum[now] = a[l];
lma[now] = rma[now] = max(a[l], 0);
siz[now] = 1;
}
if(l<mid) build(l, mid-1, mid);
if(mid<r) build(mid+1, r, mid);
val[now] = a[mid]; fa[now] = pre;
upd(now);
s[pre][mid>=f] = now;
}
void pushDown(int x){
int l=s[x][0], r=s[x][1];
if(tag[x]){
tag[x] = rev[x] = 0;
if(l) tag[l] = 1, val[l] = val[x], sum[l] = siz[l] * val[x];
if(r) tag[r] = 1, val[r] = val[x], sum[r] = siz[r] * val[x];
if(val[x]>=0){
if(l) lma[l] = rma[l] = zdz[l] = sum[l];
if(r) lma[r] = rma[r] = zdz[r] = sum[r];
}
else{
if(l) lma[l] = rma[l] = 0, zdz[l] = val[x];
if(r) lma[r] = rma[r] = 0, zdz[r] = val[x];
}
}
if(rev[x]){
rev[x] = false; rev[l] ^= 1; rev[r] ^= 1;
swap(lma[l], rma[l]); swap(lma[r], rma[r]);
swap(s[l][0], s[l][1]); swap(s[r][0], s[r][1]);
}
}
int queryLoc(int x, int w){
pushDown(x);
if(w<=siz[s[x][0]]) return queryLoc(s[x][0], w);
else if(w>siz[s[x][0]]+1) return queryLoc(s[x][1], w-siz[s[x][0]]-1);
else return x;
}
void xf(int x){
if(fa[x]) xf(fa[x]);
pushDown(x);
}
void rotate(int x){
int old=fa[x], oldf=fa[old], w=gx(x);
s[old][w] = s[x][w^1]; s[x][w^1] = old;
fa[s[old][w]] = old; fa[old] = x; fa[x] = oldf;
if(oldf) s[oldf][s[oldf][1]==old] = x;
else rot = x;
upd(old); upd(x);
}
void splay(int x, int goal){
xf(x);
while(fa[x]!=goal){
int f=fa[x];
if(fa[f]!=goal) rotate(gx(f)==gx(x)?f:x);
rotate(x);
}
upd(x);
}
void insert(int uu, int vv){
for(int i=1; i<=vv; i++){
scanf("%d", &a[i]);
if(din) idx[i] = sta[din--];
else idx[i] = ++cnt;
}
build(1, vv, 0);
int ww=idx[(vv+1)>>1];
int tx=queryLoc(rot, uu+1), ty=queryLoc(rot, uu+2);
splay(tx, 0); splay(ty, rot);
s[ty][0] = ww; fa[ww] = ty;
upd(ty); upd(tx);
}
int spilt(int uu, int vv){
int tx=queryLoc(rot, uu), ty=queryLoc(rot, uu+vv+1);
splay(tx, 0); splay(ty, rot);
return s[ty][0];
}
void shanssu(int uu, int vv){
int x=spilt(uu, vv), y=fa[x];
recycle(x); s[y][0] = 0;
upd(y); upd(fa[y]);
}
void modify(int uu, int vv, int ww){
int x=spilt(uu, vv), f=fa[x];
val[x] = ww; tag[x] = true; sum[x] = siz[x] * ww;
if(ww>=0) lma[x] = rma[x] = zdz[x] = sum[x];
else lma[x] = rma[x] = 0, zdz[x] = ww;
upd(f); upd(fa[f]);
}
void reverse(int uu, int vv){
int x=spilt(uu, vv), f=fa[x];
if(!tag[x]){
rev[x] ^= 1;
swap(s[x][0], s[x][1]);
swap(lma[x], rma[x]);
upd(f); upd(fa[f]);
}
}
int getSum(int uu, int vv){
int x=spilt(uu, vv);
return sum[x];
}
}splay;
int main(){
cin>>n>>m;
splay.zdz[0] = a[1] = a[n+2] = -oo;
for(int i=1; i<=n; i++) scanf("%d", &a[i+1]);
for(int i=1; i<=n+2; i++) idx[i] = i;
splay.build(1, n+2, 0);
rot = (n + 3) >> 1;
cnt = n + 2;
while(m--){
scanf("%s", ss);
if(ss[0]=='I'){
scanf("%d %d", &uu, &vv);
splay.insert(uu, vv);
}
if(ss[0]=='D'){
scanf("%d %d", &uu, &vv);
splay.shanssu(uu, vv);
}
if(ss[0]=='M' && ss[2]=='K'){
scanf("%d %d %d", &uu, &vv, &ww);
splay.modify(uu, vv, ww);
}
if(ss[0]=='R'){
scanf("%d %d", &uu, &vv);
splay.reverse(uu, vv);
}
if(ss[0]=='G'){
scanf("%d %d", &uu, &vv);
printf("%d\n", splay.getSum(uu, vv));
}
if(ss[0]=='M' && ss[2]=='X')
printf("%d\n", splay.zdz[rot]);
}
return 0;
}下面是poj的，稍加改动即可ac洛谷。
如果想看题意分析及讲解请看这里，讲得很好，一下就让我明白splay维护区间了。
splay的价值在于维护区间，如果只是维护点的话完全可以用treap等平衡树代替
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, m, uu, vv, ww, rot, sze;
const int oo=0x3f3f3f3f;
char ss[15];
struct Splay{
int s[200005][2], zxz[200005], val[200005], fa[200005], siz[200005];
int rev[200005], tag[200005];
void clr(int x){
s[x][0] = s[x][1] = zxz[x] = val[x] = fa[x] = siz[x] = rev[x] = tag[x] = 0;
}
int gx(int x){
return s[fa[x]][1]==x;
}
int newNode(int x){
clr(++sze); siz[sze] = 1;
val[sze] = zxz[sze] = x; return sze;
}
void ins(int x){
newNode(x); s[rot][1] = sze; fa[sze] = rot; splay(sze, 0);
}
int queryLoc(int now, int x){
pushDown(now);
if(x<=siz[s[now][0]]) return queryLoc(s[now][0], x);
else if(x>siz[s[now][0]]+1) return queryLoc(s[now][1], x-siz[s[now][0]]-1);
else return now;
}
void upd(int x){
siz[x] = siz[s[x][0]] + siz[s[x][1]] + 1;
zxz[x] = val[x];
if(s[x][0]) zxz[x] = min(zxz[x], zxz[s[x][0]]);
if(s[x][1]) zxz[x] = min(zxz[x], zxz[s[x][1]]);
}
void rotate(int x){
int old=fa[x], oldf=fa[old], w=gx(x);
s[old][w] = s[x][w^1]; s[x][w^1] = old;
fa[s[old][w]] = old; fa[old] = x; fa[x] = oldf;
if(oldf) s[oldf][s[oldf][1]==old] = x;
else rot = x;
upd(old); upd(x);
}
void pushDown(int x){
if(tag[x])
for(int i=0; i<2; i++)
if(s[x][i]){
zxz[s[x][i]] += tag[x];
val[s[x][i]] += tag[x];
tag[s[x][i]] += tag[x];
}
if(rev[x]){
if(s[x][0]) rev[s[x][0]] ^= 1;
if(s[x][1]) rev[s[x][1]] ^= 1;
swap(s[x][0], s[x][1]);
}
tag[x] = rev[x] = 0;
}
void xf(int x){
if(fa[x]) xf(fa[x]);
pushDown(x);
}
void splay(int x, int goal){
xf(x);
while(fa[x]!=goal){
int f=fa[x];
if(fa[f]!=goal) rotate(gx(x)==gx(f)?f:x);
rotate(x);
}
upd(x);
}
void update(int uu, int vv, int ww){
int tx=queryLoc(rot, uu), ty=queryLoc(rot, vv+2);
splay(tx, 0); splay(ty, rot);
val[s[ty][0]] += ww; zxz[s[ty][0]] += ww; tag[s[ty][0]] += ww;
}
void reverse(int uu, int vv){
int tx=queryLoc(rot, uu), ty=queryLoc(rot, vv+2);
splay(tx, 0); splay(ty, rot);
rev[s[ty][0]] ^= 1;
}
void revolve(int uu, int vv, int ww){
int len=vv-uu+1;
ww = (ww%len+len)%len;
int tx=queryLoc(rot, vv-ww+1), ty=queryLoc(rot, vv+2);
int x=queryLoc(rot, uu), y=queryLoc(rot, uu+1);
splay(tx, 0); splay(ty, rot);
int tmp=s[ty][0]; s[ty][0] = 0;
splay(x, 0); splay(y, rot);
s[y][0] = tmp; fa[s[y][0]] = y;
}
void insert(int uu, int vv){
int tx=queryLoc(rot, uu+1), ty=queryLoc(rot, uu+2);
splay(tx, 0); splay(ty, rot);
s[ty][0] = newNode(vv); fa[s[ty][0]] = ty;
}
void shanchu(int uu){
int tx=queryLoc(rot, uu), ty=queryLoc(rot, uu+2);
splay(tx, 0); splay(ty, rot);
s[ty][0] = 0;
}
int queryMin(int uu, int vv){
int tx=queryLoc(rot, uu), ty=queryLoc(rot, vv+2);
splay(tx, 0); splay(ty, rot);
return zxz[s[ty][0]];
}
}splay;
int main(){
cin>>n;
rot = splay.newNode(oo);
for(int i=1; i<=n; i++){
scanf("%d", &uu);
splay.ins(uu);
}
splay.ins(oo);
cin>>m;
while(m--){
scanf("%s", ss);
if(ss[0]=='A'){
scanf("%d %d %d", &uu, &vv, &ww);
splay.update(uu, vv, ww);
}
if(ss[0]=='R' && ss[3]=='E'){
scanf("%d %d", &uu, &vv);
splay.reverse(uu, vv);
}
if(ss[0]=='R' && ss[3]=='O'){
scanf("%d %d %d", &uu, &vv, &ww);
splay.revolve(uu, vv, ww);
}
if(ss[0]=='I'){
scanf("%d %d", &uu, &vv);
splay.insert(uu, vv);
}
if(ss[0]=='D'){
scanf("%d", &uu);
splay.shanchu(uu);
}
if(ss[0]=='M'){
scanf("%d %d", &uu, &vv);
printf("%d\n", splay.queryMin(uu, vv));
}
}
return 0;
}转载于:https://wwwblogs/poorpool/p/8043983.html
更多推荐
splay模板三合一 luogu2042 [NOI2005]维护数列/bzoj1500 [NOI2005]维修数列 | poj3580 SuperMemo |
发布评论