转化为ds类 + 移轴不移图：P5324

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135237445

https://www.luogu.com.cn/problem/P5324

首先相当于一堆柱子，放倒后覆盖 [1,n][1,n]

对于平移操作，我们移起来非常麻烦，我们可以移轴不移图，移动区间 [1,n][1,n] 即可。

然而，对于一个柱子大于 nn ，就不能拿它来覆盖，我们要动态维护，因此ds需要支持区间修改。我们维护区间min，区间min个数，区间0个数即可。

1
2
3
4
5
pre coding at 7:54
st coding at 7:56
st bugging at 8:05
passing at 8:45
fn blogging at 9:42
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 800010
//#define M
//#define mo
int n, m, i, j, k, T;
int a[N], bin[N], p, x, st, q; 

struct Segment_tree {
	#define ls (k<<1)
	#define rs (k<<1|1)
	#define mid (l+r>>1)
	int c[N<<2], mn[N<<2], cnt[N<<2], tag[N<<2]; 
	void push_up(int k) {
		c[k]=c[ls]+c[rs]; 
		mn[k]=min(mn[ls], mn[rs]); 
		if(mn[ls] < mn[rs]) cnt[k]=cnt[ls]; 
		else if(mn[rs] < mn[ls]) cnt[k]=cnt[rs]; 
		else cnt[k]=cnt[ls]+cnt[rs]; 
	}
	void Add(int k, int z) {
		tag[k]+=z; mn[k]+=z; 
		if(mn[k]==0) c[k]=cnt[k]; else c[k]=0; 
	}
	void push_down(int k) {
		Add(ls, tag[k]); Add(rs, tag[k]); tag[k]=0; 
	}
	void build(int k, int l, int r) {
		if(l==r) return c[k]=cnt[k]=1, mn[k]=0, void(); 
		build(ls, l, mid); build(rs, mid+1, r); 
		push_up(k); 
	}
	void add(int k, int l, int r, int x, int y) {
		if(l==r) return mn[k]+=y, cnt[k]=1, c[k]=(mn[k]==0), void(); 
		push_down(k); 
		if(x <= mid) add(ls, l, mid, x, y); 
		else add(rs, mid+1, r, x, y); 
		push_up(k); 
	}
	void modify(int k, int l, int r, int x, int y, int z) {
		if(l>=x && r<=y) return Add(k, z), void(); 
		push_down(k); 
		if(x <= mid) modify(ls, l, mid, x, y, z); 
		if(y >= mid+1) modify(rs, mid+1, r, x, y, z); 
		push_up(k); 
	}
	int que(int k, int l, int r, int x, int y) {
		if(l>=x && r<=y) return c[k]; 
		int sum=0; push_down(k); 
		if(x<=mid) sum+=que(ls, l, mid, x, y); 
		if(y>=mid+1) sum+=que(rs, mid+1, r, x, y); 
		return sum; 
	}
	#undef ls
	#undef rs
	#undef mid
}Seg;

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	Seg.build(1, 1, 8e5);
	n=read(); q=read(); st=4e5; 
	for(i=1; i<=n; ++i) {
		k=read(); bin[a[i]=k+st]++; 
		if(a[i]<=st+n) Seg.add(1, 1, 8e5, a[i]-bin[a[i]]+1, 1); 
//		debug("Add : ")
	}
	debug("》[%d %d] %d\n", st+1, st+n+1, Seg.que(1, 1, 8e5, st+1, st+n)); 
	while(q--) {
		p=read(); x=read(); 
		if(p > 0) {
			if(a[p]<=st+n) Seg.add(1, 1, 8e5, a[p]-bin[a[p]]+1, -1); --bin[a[p]]; 
			bin[a[p]=x+st]++; if(a[p]<=st+n) Seg.add(1, 1, 8e5, a[p]-bin[a[p]]+1, 1); 
		}
		else {
			x*=-1; 
			if(x==1) {
				debug("> [%d %d]\n", st+n-bin[st+n]+1, st+n); 
				++st; 
				if(bin[st+n]) Seg.modify(1, 1, 8e5, st+n-bin[st+n]+1, st+n, 1); 
			}
			else {
				debug("> [%d %d]\n", st+n-bin[st+n]+1, st+n); 
				if(bin[st+n]) Seg.modify(1, 1, 8e5, st+n-bin[st+n]+1, st+n, -1); --st; 
			}
		}
		printf("%d\n", Seg.que(1, 1, 8e5, st+1, st+n)); 
	}
	return 0;
}