沉没林地

题目

题目描述

Ori复活了
沉没林地，这是他旅途的起点
沉没林地可以用一条长度为$n$序列表示，存在两种东西，一个是树木，一个是小山丘，这些分别有一个高度
有$m$天，每一天，沉没林地从左至右有水涌入，每次水涌入都由一个参数$t_i$表示，从左至右高度第一个$\geqslant t_i$的山丘挡住（树木不会挡住水），否则，林地将会被淹没直到水的高度到达$t_i$为止。在第二天开始时，第一天的水又会瞬间消失
Ori想要知道每天没有被淹没的树的个数是多少

输入格式

第一行：$n,m$
第二行：$n$个整数，每个$h_i$表示这个林地，假如$h_i>0$，那么此地为树木，如果$h_i<0$，那么此地为山丘
高度为$|h_i|$
第三行：$m$个整数，分别表示一天水涌入的参数$t_i$
此外此题强制在线，输入的真实的$t_i$为$t_i\land lastans$，$lastans$表示上次询问的答案，一开始$lastans=0$

输出格式

有$m$行，对于每一个$t_i$输出答案

样例

样例输入

4 3
-2 4 -4 3
2
1
7

样例输出

2
2
0

数据范围与提示

真实的$t_i$分别为$2$、$3$、$5$
第一天：水越不过第一个山丘，树木没有被淹没，答案为$2$
第二天：水越过第一个小山丘，没有把树木淹没，答案为$2$
第三天：水越过第二个小山丘，把所有树木淹没，答案为$0$
对于$30%$的数据，$n,m\leqslant 3000$
对于另外$20%$的数据，$h_i>0$
对于前$80%$的数据，内存限制为128MB
对于$100%$的数据，$n,m\leq 5*10^5 ,h_i\leq 10^9$

题解

对于每个$h_i$有两种情况：

1. 山丘：更新前面所有山丘的高度的最大值$maxs$
2. 树：更新$t_{++len}$，表示这棵树的前面的所有山丘的高度的最大值（就是上面记录的$maxs$）和$h_i$这两个数中的最大值

将$t$数组排序，二分查找（可以手写，也可以直接upper_bound）出每次水被淹没的树是排序后的第几棵树，用总数减一下就可以了
附上代码：

#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,s,ans,maxs,a[500010],t[500010];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]<0){maxs=max(maxs,-a[i]+1);continue;}
        t[++s]=max(maxs,a[i]);
    }
    sort(t+1,t+s+1);
    for(int i=1,x;i<=m;i++) scanf("%d",&x),x^=ans,ans=upper_bound(t+1,t+s+1,x)-t,ans=s-ans+1,printf("%d\n",ans);
}

喜欢的话，给博主赏一杯冰阔乐吧~