BJOI2019 删数

考虑$p\neq 0$的情况。

使用$a_i$表示数字i出现的次数。

构建一棵线段树，令$a_i$覆盖$[i-a_i+1,a_i]$的区间，最终$[1,n]$内为0的位置的个数即为答案。

很显然一个位置为0，我们必定要调整之后的某个数到这个位置来覆盖它。

带整体加减？

区间平移。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#define debug(x) std::cout << #x << " = " << x << std::endl;

typedef long long int int_t;
using std::cin;
using std::endl;
using std::cout;

const int_t LARGE = 5e5;

struct State {
	int_t val,count;
	State operator+(const State& rhs) const {
		State next=*this;
		if(rhs.val==next.val) next.count+=rhs.count;
		else if(rhs.val<next.val) {
			next=rhs;
		}
		return next;
	}
};
struct Node {
	Node*left,*right;
	State state {0,1};
	int_t mark=0;
	int_t begin,end;
	Node(int_t begin,int_t end) {
		this->begin=begin,this->end=end;
	}
	void add(int_t x) {
//        minval+=x;
		state.val+=x;
		mark+=x;
	}
	void pushDown() {
		if(mark) {
			left->add(mark),right->add(mark);
			mark=0;
		}
	}
	void maintain() {
		if(begin==end) return;
		state=left->state+right->state;
	}
	static Node* build(int_t begin,int_t end) {
		Node* node=new Node(begin,end);
		if(begin!=end) {
			int_t mid=(begin+end)/2;
			node->left=build(begin,mid);
			node->right=build(mid+1,end);
		}
		node->maintain();
		return node;
	}
	void add(int_t begin,int_t end,int_t x) {
		if(end<this->begin||begin>this->end) return;
		if(this->begin>=begin&&this->end<=end) {
			this->add(x);
			return;
		}
		pushDown();
		left->add(begin,end,x);
		right->add(begin,end,x);
		maintain();
	}
	State query(int_t begin,int_t end) {
		if(this->begin>=begin&&this->end<=end) return state;
		int_t mid=(this->begin+this->end)/2;
		pushDown();
		if(end<=mid) return left->query(begin,end);
		else if(begin>mid) return right->query(begin,end);
		return left->query(begin,mid)+right->query(mid+1,end);
	}
};
int_t count[LARGE+1];
int_t seq[LARGE+1];
int_t n,m;
Node* root;
int_t lOff,rOff;
//ÈÃij¸öÊý½øÈë/Í˳ö
void modify(int_t x,int_t opt) {
	if(opt==1) count[x]+=opt;
#ifdef DEBUG
	cout<<"exec pos "<<x-count[x]+1<<" "<<opt<<" number "<<x<<endl;
	cout<<"before exec count = "<<count[x]<<endl;
#endif
	root->add(x-count[x]+1,x-count[x]+1,opt);
	if(opt==-1) count[x]+=opt;
}
int main() {
	scanf("%lld%lld",&n,&m);

	lOff=std::max(n,m)+1;
	rOff=lOff+n-1;
	for(int i=1; i<=n; i++) {
		int_t x;
		scanf("%lld",&x);
		x+=std::max(n,m);
		count[x]++;
		seq[i]=x;
	}
	root=Node::build(1,3*std::max(n,m));
	for(int_t i=lOff; i<=rOff+1; i++) {
#ifdef DEBUG
		cout<<"count "<<i<<" = "<<count[i]<<" cover "<<i-count[i]+1<<" to "<<i<<endl;
#endif
		if(count[i])
			root->add(i-count[i]+1,i,1);
	}
	for(int_t i=1; i<=m; i++) {
		int_t opt,x;
		scanf("%lld%lld",&opt,&x);
		if(opt==0) {
			if(x==1) {
				if(count[rOff]) {
					root->add(rOff-count[rOff]+1,rOff,-1);
				}
				lOff--,rOff--;
			} else {
				lOff++,rOff++;
				if(count[rOff]) {
					root->add(rOff-count[rOff]+1,rOff,1);
				}

			}
#ifdef DEBUG
			cout<<"moved to "<<lOff<<" "<<rOff<<endl;
#endif

		} else {
			if(seq[opt]<=rOff)
				root->add(seq[opt]-count[seq[opt]]+1,seq[opt]-count[seq[opt]]+1,-1);
			count[seq[opt]]-=1;
			seq[opt]=x+lOff-1;
			modify(seq[opt],1);

		}
		auto ret=root->query(lOff,rOff);
		if(ret.val!=0) {
			printf("0\n");
		} else {
			printf("%lld\n",ret.count);
		}
#ifdef DEBUG
		for(int_t i=1; i<=rOff; i++) cout<<i<<" = "<<root->query(i,i).val<<endl;
#endif

	}
	return 0;
}