[NOI2005]维修数列

C++(g++ 7.5.0) 解法, 执行用时: 456ms, 内存消耗: 121984K, 提交时间: 2022-11-23 18:14:42

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define lc (ch[x][0])
#define se second
#define U unsigned
#define rc (ch[x][1])
#define Re register
#define LL long long
#define MP std::make_pair
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5000000+5;

int f[MAXN],ch[MAXN][2],size[MAXN],val[MAXN],sum[MAXN],ls[MAXN],rs[MAXN],max[MAXN];
int rev[MAXN],tag[MAXN];

int a[MAXN],bin[MAXN],cnt,top,N,M;

inline void pushup(int x){
    size[x] = size[lc] + size[rc] + 1;
    sum[x] = sum[lc] + sum[rc] + val[x];
    max[x] = std::max(std::max(max[lc],max[rc]),rs[lc]+ls[rc]+val[x]);
    ls[x] = std::max(ls[lc],sum[lc]+val[x]+ls[rc]);
    rs[x] = std::max(rs[rc],sum[rc]+val[x]+rs[lc]);
}

inline void pushdown(int x){
    if(tag[x]){
        tag[x] = rev[x] = false;
        if(lc){
            tag[lc] = true;val[lc] = val[x];sum[lc] = val[x]*size[lc];
        }
        if(rc){
            tag[rc] = true;val[rc] = val[x];sum[rc] = val[x]*size[rc];
        }
        if(val[x] >= 0){
            if(lc) ls[lc] = rs[lc] = max[lc] = sum[lc];
            if(rc) ls[rc] = rs[rc] = max[rc] = sum[rc];
        }
        else{
            if(lc) ls[lc] = rs[lc] = 0,max[lc] = val[x];
            if(rc) ls[rc] = rs[rc] = 0,max[rc] = val[x];
        }
    }
    if(rev[x]){
        rev[x] = 0;rev[lc] ^= 1;rev[rc] ^= 1;
        std::swap(ls[lc],rs[lc]);std::swap(ls[rc],rs[rc]);
        std::swap(ch[lc][0],ch[lc][1]);std::swap(ch[rc][0],ch[rc][1]);
    }
}

inline void rotate(int x){
    int y = f[x],z = f[y],k = ch[y][1] == x,w = ch[x][!k];
    ch[z][ch[z][1] == y] = x;f[x] = z;
    ch[x][!k] = y;f[y] = x;
    ch[y][k] = w;f[w] = y;
    pushup(y);pushup(x);
}
int root;
inline void splay(int x,int v){
    int y,z;
    while((y = f[x]) != v){
        if((z = f[y]) != v) rotate((ch[z][1] == y)^(ch[y][1] == x) ? x : y);
        rotate(x);
    }
    if(!v) root = x;
}

int getkth(int rk){
    int x = root;
    while(233){
        pushdown(x);
        if(rk <= size[lc]) x = lc;
        else if(rk == size[lc]+1) return x;
        else rk -= size[lc]+1,x = rc;
    }
}

inline int build(int l,int r,int fa){
    if(l > r) return 0;
    int mid = (l + r) >> 1,x;
    x =  ++cnt;
    f[x] = fa;val[x] = a[mid];
    rev[x] = tag[x] = 0;
    lc = build(l,mid-1,x);rc = build(mid+1,r,x);
    pushup(x);return x;
}

inline void insert(int l,int tot){
    int r = l+1;
    l = getkth(r);r = getkth(r+1);
    splay(l,0);splay(r,l);
    FOR(i,1,tot) scanf("%d",a+i);
    ch[r][0] = build(1,tot,r);
    N += tot;pushup(r);pushup(l);
}
inline void del(int l,int r){
    N -= r-l+1;
    l = getkth(l);r = getkth(r+2);
    splay(l,0);splay(r,l);
    ch[r][0] = 0;
    pushup(r);pushup(l);
}

inline void modify(int l,int r,int v){
    l = getkth(l);r = getkth(r+2);
    splay(l,0);splay(r,l);
    int x = ch[r][0];
    val[x] = v;sum[x] = v*size[x];
    if(v <= 0) ls[x] = rs[x] = 0,max[x] = v;
    else ls[x] = rs[x] = max[x] = sum[x];
    tag[x] = 1;
    pushup(r);pushup(l);
}

inline void reverse(int l,int r){
    l = getkth(l);r = getkth(r+2);
    splay(l,0);splay(r,l);
    int x = ch[r][0];
    if(!tag[x]){
        rev[x] ^= 1;std::swap(lc,rc);std::swap(ls[x],rs[x]);
        pushup(r);pushup(l);
    }
}

inline int querysum(int l,int r){
    l = getkth(l);r = getkth(r+2);
    splay(l,0);splay(r,l);
    return sum[ch[r][0]];
}

inline int calc(){
    int l = getkth(1),r = getkth(N+2);
    splay(l,0);splay(r,l);
    return max[ch[r][0]];
}

int main(){
    scanf("%d%d",&N,&M);
    max[0] = a[1] = a[N+2] = INT_MIN;
    FOR(i,1,N) scanf("%d",a+i+1);
    root = build(1,N+2,0);
    while(M--){
        char opt[10];
        int x,y,z;
        scanf("%s",opt);
        if(opt[0] == 'I'){
            scanf("%d%d",&x,&y);
            insert(x,y);
        }
        if(opt[0] == 'D'){
            scanf("%d%d",&x,&y);
            del(x,x+y-1);
        }
        if(opt[0] == 'M' && opt[2] == 'K'){
            scanf("%d%d%d",&x,&y,&z);
            modify(x,x+y-1,z);
        }
        if(opt[0] == 'R'){
            scanf("%d%d",&x,&y);
            reverse(x,x+y-1);
        }
        if(opt[0] == 'G'){
            scanf("%d%d",&x,&y);
            printf("%d\n",querysum(x,x+y-1));
        }
        if(opt[0] == 'M' && opt[2] == 'X'){
            printf("%d\n",calc());
        }
    }
    return 0;
}

C++(clang++11) 解法, 执行用时: 217ms, 内存消耗: 25144K, 提交时间: 2020-11-05 13:31:32

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define lc t[x].ch[0]
#define rc t[x].ch[1]
#define pa t[x].fa
typedef long long ll;
const int N=5e5, INF=1e9;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}

int n, Q, a[N], k, tot;
char s[20];

struct meow{
    int ch[2], fa, size, v, sum, mx, lm, rm, tag, rev;
    meow() {}
    meow(int val) {ch[0]=ch[1]=fa=tag=rev=0; size=1; v=sum=mx=lm=rm=val;}
}t[N];
int root, sz;
inline int wh(int x) {return t[pa].ch[1] == x;}
int st[N], top;
inline int nw() {return top ? st[top--] : ++sz;}

inline void paint(int x,int v) {
    t[x].tag = 1; t[x].v = v;
    t[x].sum = t[x].size*v;
    t[x].mx = t[x].lm = t[x].rm = max(t[x].sum, v);
    t[x].rev = 0;
}
inline void rever(int x) {
    if(t[x].tag) return; //hi
    t[x].rev^=1; 
    swap(lc, rc); swap(t[x].lm, t[x].rm);
}
inline void pushDown(int x) {
    if(t[x].rev) {
        if(lc) rever(lc); 
        if(rc) rever(rc);
        t[x].rev=0;
    }
    if(t[x].tag) {
        if(lc) paint(lc, t[x].v); 
        if(rc) paint(rc, t[x].v);
        t[x].tag=0;
    }
}

inline void update(int x) {
    t[x].size = t[lc].size + t[rc].size + 1;
    t[x].sum = t[lc].sum + t[rc].sum + t[x].v;
    t[x].mx = max(max(t[lc].mx, t[rc].mx), max(0, t[lc].rm) + t[x].v + max(0, t[rc].lm) );
    t[x].lm = max(t[lc].lm, t[lc].sum + t[x].v + max(0, t[rc].lm) );
    t[x].rm = max(t[rc].rm, t[rc].sum + t[x].v + max(0, t[lc].rm) );
}

inline void rotate(int x) {
    int f=t[x].fa, g=t[f].fa, c=wh(x);
    if(g) t[g].ch[wh(f)]=x; t[x].fa=g;
    t[f].ch[c] = t[x].ch[c^1]; t[t[f].ch[c]].fa=f;
    t[x].ch[c^1]=f; t[f].fa=x;
    update(f); update(x);
}
inline void splay(int x,int tar) {
    for(; pa!=tar; rotate(x))
        if(t[pa].fa != tar) rotate(wh(x)==wh(pa) ? pa : x);
    if(tar==0) root=x;
}

void build(int &x,int l,int r,int f) {
    int mid = (l+r)>>1;
    x=nw(); t[x]=meow(a[mid]); t[x].fa=f;
    if(l==r) return;
    if(l<mid) build(lc, l, mid-1, x);
    if(mid<r) build(rc, mid+1, r, x);
    update(x);
}

inline int kth(int k) {
    int x=root, lsize=0;
    while(x) {
        pushDown(x);
        int _ = lsize + t[lc].size;
        if(k<=_) x=lc;
        else if(k<=_+1) return x;
        else lsize=_+1, x=rc;
    }
    return -1;
}

void Ins(int k, int tot) {
    for(int i=1; i<=tot; i++) a[i]=read();
    int f=kth(k+1); splay(f, 0);
    int x=kth(k+2); splay(x, f);
    build(lc, 1, tot, x);
    update(x); update(f);
}

void erase(int x) {
    if(!x) return;
    st[++top]=x;
    erase(lc); erase(rc);
}
void Del(int k, int tot) {
    int f=kth(k); splay(f, 0);
    int x=kth(k+tot+1); splay(x, f);
    erase(lc); lc=0;
    update(x); update(f);
}

void Mak(int k, int tot) {
    int f=kth(k); splay(f, 0);
    int x=kth(k+tot+1); splay(x, f);
    paint(lc, read());
    update(x); update(f);
}

void Rev(int k, int tot) {
    int f=kth(k); splay(f, 0);
    int x=kth(k+tot+1); splay(x, f);
    rever(lc);
    update(x); update(f);
}

int Sum(int k, int tot) {
    int f=kth(k); splay(f, 0);
    int x=kth(k+tot+1); splay(x, f);
    return t[lc].sum;
}

int main() {
    //freopen("in","r",stdin);
    n=read(); Q=read();
    for(int i=2; i<=n+1; i++) a[i]=read(); a[1] = a[n+2] = -INF;
    t[0]=meow(-INF); t[0].sum=t[0].size=0; 
    build(root, 1, n+2, 0);
    for(int i=1; i<=Q; i++) { //printf("Q %d\n",i);
        scanf("%s",s+1); 
        if(s[3]=='X') printf("%d\n", t[root].mx);
        else {
            k=read(); tot=read();
            if(s[1]=='I') Ins(k, tot);
            if(s[1]=='D') Del(k, tot);
            if(s[1]=='M') Mak(k, tot);
            if(s[1]=='R') Rev(k, tot);
            if(s[1]=='G') printf("%d\n", Sum(k, tot));
        }
    }
}

详情