[BJOI2019] 删数

题解

题目的含义可以看做是以权值为下标的一些柱子,每个柱子的高度就是这个权值的出现的次数,然后把这些柱子向左推倒,一个高度为(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 ;
}