方法

线段树+堆

思路

维护序列和

维护了一个大顶堆heap，这个堆保存当前所有的连续子序列的和的值。比如封印了 $2$ 个数字，那么原来的序列被拆分成 $3$ 个连续子序列，此时heap分别保存这些序列的和，长度为 $3$。

拆分连续序列

手搓堆倒是很简单，或者 C++ 也有 priority_queue 这样的模版直接拿来用。关键是给出一个 $b_i$：

• 这个 $b_i$ 位于哪个连续子序列？（给出左端点和右端点）
• 这个连续子序列的在heap的哪个地方？

也都很好解决，使用线段树。第一次写线段树，不知道写的是不是真正意义上的线段树，反正时间复杂度正确就是了。每个区间是一个node结构体，一个node结构体中包含两个node*成员lchild,rchild分别指向它左右儿子，即下属的两条线段。[lbound,rbound]是该线段的范围，当valid == 1时，这条线段上所有的点所属的最长连续序列，左端点和右端点分别为left,right。

维护这个线段树，目的就是给出一个位置idx，在 $O(\log n)$ 的复杂度内判断该位置位于线段的左端点是谁。

时间复杂度

$O(n\log n)$

C++ 代码

屎山警告

# include<iostream>
# define ll long long
# define N 100005
using namespace std;
ll a[N],s[N],heap[N];
int b[N],pos[N],repos[N],heap_len = 1,n;

inline ll sm(int begin,int end){
    return s[end + 1] - s[begin];
}

typedef struct node_t {
    int lbound,rbound,left,right,valid;
    struct node_t *lchild,*rchild; 
    node_t(int lbound,int rbound,struct node_t *lchild,struct node_t *rchild,int left,int right,int valid){
        this->lbound = lbound;
        this->rbound = rbound;
        this->lchild = lchild;
        this->rchild = rchild;
        this->left = left;
        this->right = right;
        this->valid = valid;
    }

    struct node_t* seek_left(int idx){
        if(valid)
            return this;
        else if(lchild->rbound >= idx)
            return lchild->seek_left(idx);
        else
            return rchild->seek_left(idx);
    }

    void assign_left(int lbound,int rbound,int left){
        if(rbound < lbound)
            return;
        if(lbound == this->lbound && rbound == this->rbound){
            this->valid = 1;
            this->left = left;
            return;
        }
        if(this->valid){
            if(this->left != left){
                this->valid = 0;
                if(lbound >= this->rchild->lbound){
                    this->lchild->assign_lr(this->lchild->lbound,this->lchild->rbound,this->left,this->right);
                    this->rchild->assign_lr(this->rchild->lbound,lbound - 1,this->left,this->right);
                    this->rchild->assign_lr(lbound,rbound,left,this->right);
                    this->rchild->assign_lr(rbound + 1,this->rchild->rbound,this->left,this->right);
                }
                else if(rbound <= this->lchild->rbound){
                    this->lchild->assign_lr(this->lchild->lbound,lbound - 1,this->left,this->right);
                    this->lchild->assign_lr(lbound,rbound,left,this->right);
                    this->lchild->assign_lr(rbound + 1,this->lchild->rbound,this->left,this->right);
                    this->rchild->assign_lr(this->rchild->lbound,this->rchild->rbound,this->left,this->right);
                }
                else{
                    this->lchild->assign_lr(this->lchild->lbound,lbound - 1,this->left,this->right);
                    this->lchild->assign_lr(lbound,this->lchild->rbound,left,this->right);
                    this->rchild->assign_lr(this->rchild->lbound,rbound,left,this->right);
                    this->rchild->assign_lr(rbound + 1,this->rchild->rbound,this->left,this->right);
                }
            }
        }
        else{
            if(lbound >= this->rchild->lbound)
                this->rchild->assign_left(lbound,rbound,left);
            else if(rbound <= this->lchild->rbound)
                this->lchild->assign_left(lbound,rbound,left);
            else{
                this->lchild->assign_left(lbound,this->lchild->rbound,left);
                this->rchild->assign_left(this->rchild->lbound,rbound,left);
            }
        }
    }


    void assign_right(int lbound,int rbound,int right){
        if(rbound < lbound)
            return;
        if(lbound == this->lbound and rbound == this->rbound){
            this->valid = 1;
            this->right = right;
            return;
        }
        if(this->valid){
            if(this->right != right){
                this->valid = 0;
                if(lbound >= this->rchild->lbound){
                    this->lchild->assign_lr(this->lchild->lbound,this->lchild->rbound,this->left,this->right);
                    this->rchild->assign_lr(this->rchild->lbound,lbound - 1,this->left,this->right);
                    this->rchild->assign_lr(lbound,rbound,this->left,right);
                    this->rchild->assign_lr(rbound + 1,this->rchild->rbound,this->left,this->right);

                }
                else if(rbound <= this->lchild->rbound){
                    this->lchild->assign_lr(this->lchild->lbound,lbound - 1,this->left,this->right);
                    this->lchild->assign_lr(lbound,rbound,this->left,right);
                    this->lchild->assign_lr(rbound + 1,this->lchild->rbound,this->left,this->right);
                    this->rchild->assign_lr(this->rchild->lbound,this->rchild->rbound,this->left,this->right);

                }
                else{
                    this->lchild->assign_lr(this->lchild->lbound,lbound - 1,this->left,this->right);
                    this->lchild->assign_lr(lbound,this->lchild->rbound,this->left,right);
                    this->rchild->assign_lr(this->rchild->lbound,rbound,this->left,right);
                    this->rchild->assign_lr(rbound + 1,this->rchild->rbound,this->left,this->right);
                }
            }
        } 
        else{
            if(lbound >= this->rchild->lbound)
                this->rchild->assign_right(lbound,rbound,right);
            else if(rbound <= this->lchild->rbound)
                this->lchild->assign_right(lbound,rbound,right);
            else{
                this->lchild->assign_right(lbound,this->lchild->rbound,right);
                this->rchild->assign_right(this->rchild->lbound,rbound,right);
            }
        }
    }

    void assign_lr(int lbound,int rbound,int left,int right){
        this->assign_left(lbound,rbound,left);
        this->assign_right(lbound,rbound,right);
    }
} node;

node* tree;

node* build_tree(int left,int right){
    int mid = (left + right) >> 1;
    node* ret = NULL;
    if(left == right)
        ret = new node(left,right,NULL,NULL,0,0,0);
    else
        ret = new node(left,right,build_tree(left,mid),build_tree(mid + 1,right),0,0,0);
    return ret;
}

void heap_swap(int idx1,int idx2){
    pos[repos[idx1]] = idx2;
    pos[repos[idx2]] = idx1;
    ll temp = repos[idx1];
    repos[idx1] = repos[idx2];
    repos[idx2] = temp;
    temp = heap[idx1];
    heap[idx1] = heap[idx2];
    heap[idx2] = temp;
}

void heap_down(int idx){
    if(2 * idx + 1 >= heap_len)
        return;
    if(2 * idx + 2 == heap_len){
        if(heap[idx] < heap[2 * idx + 1])
            heap_swap(idx,2 * idx + 1);
    }
    else{
        if(heap[idx] >= heap[2 * idx + 1] && heap[idx] >= heap[2 * idx + 2])
            return;
        if(heap[2 * idx + 1] > heap[2 * idx + 2]){
            heap_swap(idx,2 * idx + 1);
            heap_down(2 * idx + 1);
        }
        else{
            heap_swap(idx,2 * idx + 2);
            heap_down(2 * idx + 2);
        }
    }
}


void heap_up(int idx){
    if(idx == 0)
        return;
    int parent = (idx - 1) >> 1;
    if(heap[parent] < heap[idx]){
        heap_swap(parent,idx);
        heap_up(parent);
    }
}

void block(int idx){
    node *subtree = tree->seek_left(idx);
    int lbound = subtree->left;
    int rbound = subtree->right;
    heap[pos[lbound]] = sm(lbound,idx - 1);
    heap_down(pos[lbound]);
    if(idx < n - 1){
        heap[heap_len++] = sm(idx + 1,rbound);
        pos[idx + 1] = heap_len - 1;
        repos[heap_len - 1] = idx + 1;
        heap_up(heap_len - 1);
    }
    tree->assign_left(idx + 1,rbound,idx + 1);
    tree->assign_right(lbound,idx - 1,idx - 1);
}

int main(){
    cin >> n;
    for(int i = 0;i < n;i++)
        scanf("%lld",&a[i]);
    for(int i = 0;i < n;i++)
        scanf("%d",&b[i]);
    for(int i = 0;i < n;i++)
        s[i + 1] = s[i] + a[i];
    heap[0] = sm(0,n - 1);
    tree = build_tree(0,n - 1);
    tree->left = 0;
    tree->right = n - 1;
    tree->valid = 1;
    for(int i = 0;i < n;i++){
        block(b[i] - 1);
        printf("%lld\n",heap[0]);
    }
}

Python 代码

哥们做这题一开始用的 Python，为蓝桥杯做准备，写完发现 acwing 对所有语言都是一样的时间限制，py 直接狠狠的 TLE。熬夜把 Python 代码转成了上面的 C++ 代码。原来的 Python 代码也附上（同样是屎山）：

import os
import sys

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

s = [0]
for i in range(n):
    s.append(s[-1] + a[i])
def sm(begin,end):
    return s[end + 1] - s[begin]

pos = [0] * n
repos = [0] * n
heap = []
heap.append(sm(0,n - 1))

# init:
class node:
    def __init__(self,lbound,rbound,lchild,rchild,left,right,valid):
        self.lbound = lbound
        self.rbound = rbound
        self.lchild = lchild
        self.rchild = rchild
        self.left = left
        self.right = right
        self.valid = valid

    def seek_left(self,idx):
        if(self.lbound == self.rbound):
            assert(self.valid)
        if(self.valid):
            return self
        elif self.lchild.rbound >= idx:
            return self.lchild.seek_left(idx)
        else:
            return self.rchild.seek_left(idx)

    def assign_left(self,lbound,rbound,left):
        if(rbound < lbound):
            return
        if(lbound == self.lbound and rbound == self.rbound):
            self.valid = True
            self.left = left
            return
        if(self.valid):
            if(self.left != left):
                self.valid = False
                if(lbound >= self.rchild.lbound):
                    self.lchild.assign_lr(self.lchild.lbound,self.lchild.rbound,self.left,self.right)
                    self.rchild.assign_lr(self.rchild.lbound,lbound - 1,self.left,self.right)
                    self.rchild.assign_lr(lbound,rbound,left,self.right)
                    self.rchild.assign_lr(rbound + 1,self.rchild.rbound,self.left,self.right)
                elif(rbound <= self.lchild.rbound):
                    self.lchild.assign_lr(self.lchild.lbound,lbound - 1,self.left,self.right)
                    self.lchild.assign_lr(lbound,rbound,left,self.right)
                    self.lchild.assign_lr(rbound + 1,self.lchild.rbound,self.left,self.right)
                    self.rchild.assign_lr(self.rchild.lbound,self.rchild.rbound,self.left,self.right)
                else:
                    self.lchild.assign_lr(self.lchild.lbound,lbound - 1,self.left,self.right)
                    self.lchild.assign_lr(lbound,self.lchild.rbound,left,self.right)
                    self.rchild.assign_lr(self.rchild.lbound,rbound,left,self.right)
                    self.rchild.assign_lr(rbound + 1,self.rchild.rbound,self.left,self.right)
        else:
            if(lbound >= self.rchild.lbound):
                self.rchild.assign_left(lbound,rbound,left)
            elif(rbound <= self.lchild.rbound):
                self.lchild.assign_left(lbound,rbound,left)
            else:
                self.lchild.assign_left(lbound,self.lchild.rbound,left)
                self.rchild.assign_left(self.rchild.lbound,rbound,left)

    def assign_right(self,lbound,rbound,right):
        if(rbound < lbound):
            return
        if(lbound == self.lbound and rbound == self.rbound):
            self.valid = True
            self.right = right
            return
        if(self.valid):
            if(self.right != right):
                self.valid = False
                if(lbound >= self.rchild.lbound):
                    self.lchild.assign_lr(self.lchild.lbound,self.lchild.rbound,self.left,self.right)
                    self.rchild.assign_lr(self.rchild.lbound,lbound - 1,self.left,self.right)
                    self.rchild.assign_lr(lbound,rbound,self.left,right)
                    self.rchild.assign_lr(rbound + 1,self.rchild.rbound,self.left,self.right)
                elif(rbound <= self.lchild.rbound):
                    self.lchild.assign_lr(self.lchild.lbound,lbound - 1,self.left,self.right)
                    self.lchild.assign_lr(lbound,rbound,self.left,right)
                    self.lchild.assign_lr(rbound + 1,self.lchild.rbound,self.left,self.right)
                    self.rchild.assign_lr(self.rchild.lbound,self.rchild.rbound,self.left,self.right)
                else:
                    self.lchild.assign_lr(self.lchild.lbound,lbound - 1,self.left,self.right)
                    self.lchild.assign_lr(lbound,self.lchild.rbound,self.left,right)
                    self.rchild.assign_lr(self.rchild.lbound,rbound,self.left,right)
                    self.rchild.assign_lr(rbound + 1,self.rchild.rbound,self.left,self.right)
        else:
            if(lbound >= self.rchild.lbound):
                self.rchild.assign_right(lbound,rbound,right)
            elif(rbound <= self.lchild.rbound):
                self.lchild.assign_right(lbound,rbound,right)
            else:
                self.lchild.assign_right(lbound,self.lchild.rbound,right)
                self.rchild.assign_right(self.rchild.lbound,rbound,right)

    def assign_lr(self,lbound,rbound,left,right):
        self.assign_left(lbound,rbound,left)
        self.assign_right(lbound,rbound,right)

def build_tree(left,right):
    mid = (left + right) // 2
    if(left == right):
        ret = node(left,right,None,None,0,0,False)
    else:
        ret = node(left,right,build_tree(left,mid),build_tree(mid + 1,right),0,0,False)
    return ret

tree = build_tree(0,n - 1)
tree.left = 0
tree.right = n - 1
tree.valid = True

# util:

def heap_swap(idx1,idx2):
    # print(heap)
    # print(repos)
    pos[repos[idx1]] = idx2
    pos[repos[idx2]] = idx1
    repos[idx1],repos[idx2] = repos[idx2],repos[idx1]
    heap[idx1],heap[idx2] = heap[idx2],heap[idx1]
    # print(heap)
    # print(repos)
    # exit()

def heap_down(idx):
    if(2 * idx + 1 >= len(heap)):
        return
    if(2 * idx + 2 == len(heap)):
        if(heap[idx] < heap[2 * idx + 1]):
            heap_swap(idx,2 * idx + 1)
    else:
        if(heap[idx] >= heap[2 * idx + 1] and heap[idx] >= heap[2 * idx + 2]):
            return
        if(heap[2 * idx + 1] > heap[2 * idx + 2]):
            heap_swap(idx,2 * idx + 1)
            heap_down(2 * idx + 1)
        else:
            heap_swap(idx,2 * idx + 2)
            heap_down(2 * idx + 2)

def heap_up(idx):
    if(idx == 0):
        return
    parent = (idx - 1) // 2
    if(heap[parent] < heap[idx]):
        heap_swap(parent,idx)
        heap_up(parent)

def block(idx):
    # 引发线段树 tree，索引数组 pos 和堆 heap 的改变
    subtree = tree.seek_left(idx)
    lbound,rbound = subtree.left,subtree.right
    heap[pos[lbound]] = sm(lbound,idx - 1)
    heap_down(pos[lbound])
    if(idx < n - 1):
        heap.append(sm(idx + 1,rbound))
        pos[idx + 1] = len(heap) - 1
        repos[len(heap) - 1] = idx + 1
        heap_up(len(heap) - 1)
    tree.assign_left(idx + 1,rbound,idx + 1)
    tree.assign_right(lbound,idx - 1,idx - 1)

# main:
for i in range(n):
    block(b[i] - 1)
    # print(heap)
    # print(repos)
    print(heap[0])