8.16.NOIP模拟赛（线段树求连续区间长度 | 前缀和单调栈）——2019暑假篇

这次又考栽了

一.题目

1.Hotel

1.1.题目描述

传送门

1.2.题解

这道题目就是裸的线段树求最长连续区间长度，修改+查询的题目。

对于每个区间要定义：最长连续区间，左起最长连续区间，右起最长连续区间，懒标记，左右端点

下面一个一个的来说细节:

1.修改

找到被要修改区间覆盖的区间，修改它，修改时要注意如何更新区间的状态：

//修改区间
void Insert (int flag, int Index, int l, int r){
    push_down (Index);//懒标记下方
    if (tre[Index].L >= l && tre[Index].R <= r){
        if (flag == 1)//表示入住酒店
            tre[Index].lazy = 1, tre[Index].Max = tre[Index].Maxr = tre[Index].Maxl = 0;
        if (flag == -1)//表示退房
            tre[Index].lazy = -1, tre[Index].Max = tre[Index].Maxr = tre[Index].Maxl = tre[Index].R - tre[Index].L + 1;
        return ;
    }
    if (tre[Index].L > r || tre[Index].R < l)
        return ;
    Insert (flag, Index * 2, l, r);
    Insert (flag, Index * 2 + 1, l, r);
    renew (Index);//更新区间状态
}

void renew (int Index){
    if (tre[Index * 2].Max == tre[Index * 2].R - tre[Index * 2].L + 1)//最长左区间
        tre[Index].Maxl = tre[Index * 2].Max + tre[Index * 2 + 1].Maxl;
//如果左区间全为空，最长左区间就为左区间长度+右区间的最长左区间
    else
        tre[Index].Maxl = tre[Index * 2].Maxl;
    if (tre[Index * 2 + 1].Max == tre[Index * 2 + 1].R - tre[Index * 2 + 1].L + 1)//最长右区间同理
        tre[Index].Maxr = tre[Index * 2 + 1].Max + tre[Index * 2].Maxr;
    else
        tre[Index].Maxr = tre[Index * 2 + 1].Maxr;
    tre[Index].Max = max (tre[Index * 2].Max, tre[Index * 2 + 1].Max);//最长区间
    tre[Index].Max = max (tre[Index].Max, tre[Index * 2].Maxr + tre[Index * 2 + 1].Maxl);
}

2.查询

很简单，从左区间开始，看它是否有这么多的空房，再看中间的交界，再看右区间

int Query (int Index, int d){
    push_down (Index);
    if (tre[Index].L == tre[Index].R)//说明找到了
        return tre[Index].L;
    if (tre[Index * 2].Max >= d)//看左区间
        return Query (Index * 2, d);
    if (tre[Index * 2].Maxr + tre[Index * 2 + 1].Maxl >= d)//看中间
        return tre[Index * 2].R - tre[Index * 2].Maxr + 1;
    if (tre[Index * 2 + 1].Max >= d)//看右区间
        return Query (Index * 2 + 1, d);
    return -1;
}

1.3.Code

//hotel
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
 
#define M 50005
 
int n, m, ans;
struct node {
    int L, R, lazy, Max, Maxl, Maxr;
}tre[M * 40];
 
void build (int Index, int l, int r){
    tre[Index].L = l;
    tre[Index].R = r;
    tre[Index].Max = tre[Index].Maxl = tre[Index].Maxr = r - l + 1;
    if (l != r){
        int mid = (l + r) / 2;
        build (Index * 2, l, mid);
        build (Index * 2 + 1, mid + 1, r);
    }
}
void push_down (int Index){
    if (tre[Index].lazy == 1){
        tre[Index * 2].Max = tre[Index * 2].Maxl = tre[Index * 2].Maxr = 0;
        tre[Index * 2 + 1].Max = tre[Index * 2 + 1].Maxl = tre[Index * 2 + 1].Maxr = 0;
        tre[Index * 2].lazy = tre[Index * 2 + 1].lazy = 1;
    }
    if (tre[Index].lazy == -1){
        tre[Index * 2].Max = tre[Index * 2].Maxl = tre[Index * 2].Maxr = tre[Index * 2].R - tre[Index * 2].L + 1;
        tre[Index * 2 + 1].Max = tre[Index * 2 + 1].Maxl = tre[Index * 2 + 1].Maxr = tre[Index * 2 + 1].R - tre[Index * 2 + 1].L + 1;
        tre[Index * 2].lazy = tre[Index * 2 + 1].lazy = -1;
    }
    tre[Index].lazy = 0;
}
int Query (int Index, int d){
    push_down (Index);
    if (tre[Index].L == tre[Index].R)
        return tre[Index].L;
    if (tre[Index * 2].Max >= d)
        return Query (Index * 2, d);
    if (tre[Index * 2].Maxr + tre[Index * 2 + 1].Maxl >= d)
        return tre[Index * 2].R - tre[Index * 2].Maxr + 1;
    if (tre[Index * 2 + 1].Max >= d)
        return Query (Index * 2 + 1, d);
    return -1;
}
void renew (int Index){
    if (tre[Index * 2].Max == tre[Index * 2].R - tre[Index * 2].L + 1)
        tre[Index].Maxl = tre[Index * 2].Max + tre[Index * 2 + 1].Maxl;
    else
        tre[Index].Maxl = tre[Index * 2].Maxl;
    if (tre[Index * 2 + 1].Max == tre[Index * 2 + 1].R - tre[Index * 2 + 1].L + 1)
        tre[Index].Maxr = tre[Index * 2 + 1].Max + tre[Index * 2].Maxr;
    else
        tre[Index].Maxr = tre[Index * 2 + 1].Maxr;
    tre[Index].Max = max (tre[Index * 2].Max, tre[Index * 2 + 1].Max);
    tre[Index].Max = max (tre[Index].Max, tre[Index * 2].Maxr + tre[Index * 2 + 1].Maxl);
}
void Insert (int flag, int Index, int l, int r){
    push_down (Index);
    if (tre[Index].L >= l && tre[Index].R <= r){
        if (flag == 1)
            tre[Index].lazy = 1, tre[Index].Max = tre[Index].Maxr = tre[Index].Maxl = 0;
        if (flag == -1)
            tre[Index].lazy = -1, tre[Index].Max = tre[Index].Maxr = tre[Index].Maxl = tre[Index].R - tre[Index].L + 1;
        return ;
    }
    if (tre[Index].L > r || tre[Index].R < l)
        return ;
    Insert (flag, Index * 2, l, r);
    Insert (flag, Index * 2 + 1, l, r);
    renew (Index);
}
int main (){
    freopen ("hotel.in", "r", stdin);
	freopen ("hotel.out", "w", stdout);
    int f, x, d;
    scanf ("%d %d", &n, &m);
    build (1, 1, n);
    while (m --){
        scanf ("%d", &f);
        if (f == 1){
            scanf ("%d", &d);
            ans = Query (1, d);
            if (ans == -1){
                printf ("0\n");
                continue;
            }
            printf ("%d\n", ans);
            Insert (1, 1, ans, ans + d - 1);
        }
        if (f == 2){
            scanf ("%d %d", &x, &d);
            Insert (-1, 1, x, x + d - 1);
        }
    }
    return 0;
}

2.sequence

2.1.题目

题目描述

给定n个正整数的序列a1,a2,a3…an，对该序列可执行下面的操作： 选择一个大于k的正整数ai，将ai的值减去1；选择ai-1或ai+1中的一个值加上1。 共给出m个正整数k，对于每次给定的正整数k，经过以上操作一定次数后，求出最长的一个连续子序列，使得这个子序列的每个数都不小于给定的k

输入格式

第一行两个正整数n和m。 第二行n个正整数，第i个正整数表示ai ； 第三行m个正整数，第i个正整数表示第i次给定的k。

输出格式

共一行，输出m个正整数，第i个数表示对于第i次给定的k，经过一定次数操作后，最长连续子序列的长度。

样例输入

5 6
1 2 1 1 5
1 2 3 4 5 6

输出样例

5 5 2 1 1 0

数据范围与提示

对于 30%的数据，n<30 对于 50%的数据，n<=2000 对于 100%的数据，n<=1,000,000 ,m<= 50, k <= 10^9, ai <= 10^9

2.2.题解

这道题目要注意关键词语：最长连续区间。

所以朴素的$O\left ( n^{2} \right )$算法就来了：求前缀和，前后枚举前缀和相减求最长区间

---

优化一点的，枚举后面的前缀和，发现前面的前缀和具有单调性

对于前面的前缀和：越前面的前缀和必须必后面一点的前缀和要大，那么后面一点的前缀和才有意义。

所以维护一个单调递减的单调栈：每遇到比栈顶小的就加入

然后每枚举到一个后面的前缀和，就二分查找单调栈里第一个比它小的前缀和，在统计答案即可。

但这样会被卡

---

再优一点，先处理出单调栈，如果我们从最后开始枚举后面的那一个前缀和，找到单调栈里第一个比它小的前缀和，把单调栈里后面的前缀和去掉，每次就这样操作就行了。

为什么呢？你想对于后面的那一个前缀和：越前面一点的前缀和在单调栈里对应的第一个比它小的前缀和的位置要比后面一点的前缀和对应的位置靠前才行，要不然要要亏！

好，挺简单，是吧。

2.3.Code

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
 
#define M 1000005
#define LL long long
 
int n, m, a[M], Stack[M], top;
bool flag;
LL k, b[M], sum[M];
 
void print (int ans){
    if (! flag){printf ("%d", ans); flag = 1;}
    else printf (" %d", ans);
}
int main (){
    //freopen ("sequence.in", "r", stdin);
	//freopen ("sequence.out", "w", stdout);
    scanf ("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++){
        scanf ("%d", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    while (m --){
        int ans = 0;
        top = 0;
        scanf ("%lld", &k);
        Stack[++ top] = 0;
        for (int i = 1; i <= n; i ++){
            b[i] = sum[i] - i * k;
            if (b[i] < b[Stack[top]])
                Stack[++ top] = i;
        }
        for (int i = n; i >= 1; i --){
            int wei = i;
            if (b[Stack[1]] <= b[i]){
                ans = max (ans, i - Stack[1]);
                wei = Stack[1];
                top = 1;
            }
            else if (b[Stack[top]] <= b[i]){
                while (b[Stack[top]] <= b[i] && top)
                    top --;
                top ++;
                ans = max (ans, i - Stack[top]);
            }
        }
        print (ans);
    }
    return 0;
}

3.run

尽情期待。

二.总结

尽情期待.