题解
题目的含义可以看做是以权值为下标的一些柱子,每个柱子的高度就是这个权值的出现的次数,然后把这些柱子向左推倒,一个高度为(h)的柱子的影响范围为(i-h+1sim i)
然后答案就是查询(1sim n)的这段区间没有被覆盖的点的个数
这个东西可以用线段树来维护
就是维护区间的最小值以及区间最小值的个数
对于整个序列的操作
就相当于把值域的查询范围左移或者右移
左移右移的时候要加上新的贡献,减去已经不在范围的贡献
然后由于我写的不知道为啥一直74分就直接抄了个题解
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
# define ls (now << 1)
# define rs (now << 1 | 1)
const int M = 600005 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int val[M] , cnt[M] ;
int n , m , lp , rp , upp , Np , dlt ;
struct Node {
int tag , tmi , cnt ;
Node () { } ;
} t[M * 4] ;
inline Node pushup(Node lt , Node rt) {
Node p ; p.tag = 0 ; p.cnt = 0 ;
p.tmi = min( lt.tmi , rt.tmi ) ;
if(lt.tmi == p.tmi) p.cnt += lt.cnt ;
if(rt.tmi == p.tmi) p.cnt += rt.cnt ;
return p ;
}
inline void update(int now , int k) {
t[now].tmi += k ;
t[now].tag += k ;
}
inline void pushdown(int now) {
if(t[now].tag) {
update(ls , t[now].tag) ;
update(rs , t[now].tag) ;
t[now].tag = 0 ;
}
}
void build(int l , int r , int now) {
t[now].tag = t[now].tmi = 0 ; t[now].cnt = r - l + 1 ;
if(l == r) return ; int mid = (l + r) >> 1;
build(l , mid , ls) ; build(mid + 1 , r , rs) ;
}
void Change(int L , int R , int k , int l , int r , int now) {
if(l > R || r < L) return ;
if(l >= L && r <= R) {
update(now , k) ;
return ;
}
pushdown(now) ; int mid = (l + r) >> 1 ;
if(mid >= R) Change(L , R , k , l , mid , ls) ;
else if(mid < L) Change(L , R , k , mid + 1 , r , rs) ;
else Change(L , mid , k , l , mid , ls) , Change(mid + 1 , R , k , mid + 1 , r , rs) ;
t[now] = pushup(t[ls] , t[rs]) ;
}
Node query(int L , int R , int l , int r , int now) {
if(l >= L && r <= R) return t[now] ;
pushdown(now) ; int mid = (l + r) >> 1 ;
if(mid >= R) return query(L , R , l , mid , ls) ;
else if(mid < L) return query(L , R , mid + 1 , r , rs) ;
else return pushup(query(L , mid , l , mid , ls) , query(mid + 1 , R , mid + 1 , r , rs)) ;
}
inline void CP(int x , int w) {
int k = cnt[Np + x] + (w > 0) ; cnt[Np + x] += w ;
if(x <= n) Change(Np + x - k + 1 , Np + x - k + 1 , w , 1 , upp , 1) ;
}
int main() {
n = read() ; m = read() ;
upp = (n + m) * 2 + 1 ; Np = n + m ; build(1 , upp , 1) ;
for(int i = 1 ; i <= n ; i ++) {
val[i] = read() ;
CP(val[i] , 1) ;
}
int pos , x ;
while(m --) {
pos = read() ; x = read() ;
if(pos > 0) {
CP(val[pos] + dlt , -1) ;
val[pos] = x - dlt ;
CP(val[pos] + dlt , 1) ;
}
else {
if(x > 0) {
-- Np ; ++ dlt ;
int posi = Np + n + 1 ;
if(cnt[posi] > 0)
Change(posi - cnt[posi] + 1 , posi , -1 , 1 , upp , 1) ;
}
else {
int posi = Np + n + 1 ;
++ Np ; -- dlt ;
if(cnt[posi] > 0)
Change(posi - cnt[posi] + 1 , posi , 1 , 1 , upp , 1) ;
}
}
Node tmp = query(Np + 1 , Np + n , 1 , upp , 1) ;
printf("%d
",tmp.tmi ? 0 : tmp.cnt) ;
}
return 0 ;
}