考察一点思维能力的数据结构水题……
如果 \(w_i = [a_i \ge b]\)，其中 \(a_i\) 表示第 \(i\) 块巨石的海拔，\(b\) 表示当前海拔，容易发现答案就是 \(\sum\limits_{i=1}^n w_i - \sum\limits_{i=2}^n \min(w_i,w_{i-1})\)。
为什么呢？每一个连续段的开头的前一个必定是 \(0\)（除了 \(a_1\) 作为开头的），故第二个和式统计所有非开头的 \(1\) 的个数。
每一个开头就能对应一个连续段，于是答案就出来了。
随便用个数据结构维护就行了，平衡树树状数组线段树随便写。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
using namespace std;
const int N = 2e5;
const int C = 1e9;
int n,m,a[N + 5];
struct node
{
int sum;
int ls,rs;
} seg[(N << 6) + 10];
int rt1,rt2;
void insert(int x,int k,int &p,int tl,int tr)
{
static int tot = 0;
!p && (p = ++tot),seg[p].sum += k;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].sum;
int ret = 0;
int mid = tl + tr >> 1;
l <= mid && (ret += query(l,r,seg[p].ls,tl,mid));
r > mid && (ret += query(l,r,seg[p].rs,mid + 1,tr));
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),insert(a[i],1,rt1,1,C),i > 1 && (insert(min(a[i],a[i - 1]),1,rt2,1,C),1);
int op,x,k;
for(;m;--m)
{
scanf("%d%d",&op,&x);
if(op == 1)
printf("%d\n",query(x,C,rt1,1,C) - query(x,C,rt2,1,C));
else
{
scanf("%d",&k);
insert(a[x],-1,rt1,1,C),x > 1 && (insert(min(a[x],a[x - 1]),-1,rt2,1,C),1),x < n && (insert(min(a[x],a[x + 1]),-1,rt2,1,C),1);
a[x] = k;
insert(a[x],1,rt1,1,C),x > 1 && (insert(min(a[x],a[x - 1]),1,rt2,1,C),1),x < n && (insert(min(a[x],a[x + 1]),1,rt2,1,C),1);
}
}
}