P5324 [BJOI2019] 删数

思路

先考虑不带修改的

序列答案显然与其顺序无关，注意到等于 \(n\) 的数必定被选到，所以还剩 \(n - cnt_n\) 个，然后 \(n - cnt_n\) 被选，重复循环即可。
那我们如何求要修改的个数呢？
其实很显然，你每一步覆盖不到的部分显然需要别的地方重复覆盖的点去补，所以考虑每个值垒成一根柱子，实际上就是将所有柱子向左推以后的未覆盖的点个数。

然后考虑怎么带修改：

• 对于单点修改，由于只涉及两个值，直接修改掉然后给桶分别加减就行。
• 对于区间修改，考虑到这玩意实际上等价于限定了一个查询的区间范围，然后全体加减就等价于移动这个查询范围（+1左移，-1右移）
  每次只需要在左移右移的时候删除/加入一下右边的的临界区间覆盖区间即可。
  然后我们需要微调一下单点修改，如果当前修改的值在右端点左侧，那就修改，否则改下桶即可，等到后面右端点到这里再修改就行了

具体维护的话，我们的数据结构需要支持区间加，区间查等于0的个数，所以用线段树维护最小值 \(mn\) ,最小值的数量 \(cnt\) ,区间的答案 \(res\) ,以及懒标记 \(lzy\) 即可。

为了方便维护避免负数情况，我们可以把查询范围左端点的初值赋为1.5e5这样就不会炸了。

Code

// By wnn
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/priority_queue.hpp>
//#include<ext/pb_ds/exception.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
//#include<ext/pb_ds/list_update_policy.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/trie_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;#define int long long
namespace OI{namespace Simple_name{#define myfreopen freopen(\".in\", \"r\", stdin),freopen(\".out\", \"w\", stdout)using ll = long long;using db = double;using ull = unsigned long long;using pdd = pair<db, db>;using pii = pair<int, int>;using pll = pair<ll, ll>;#define pq priority_queue#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)#define dep(i,a,b) for(int i=(a),i##_end=(b);i>=i##_end;--i)#define x1 x_1#define y1 y_1#define fir first#define sec second#define pb push_back#define I_love_you ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);}using namespace Simple_name;namespace Val{#define eps 1e-9#define inf32 0x3f3f3f3f#define inf64 0x3f3f3f3f3f3f3f3fll#define mod1 (int)(1e9 + 7)#define mod2 998244353#define PI acos(-1.0)#define db_e (double)(2.71828182845904523536028)}using namespace Val;namespace Function{#define ls(x) (x << 1)#define rs(x) ((x << 1) | 1)#define mid(l, r) ((l + r) >> 1)#define debug(x) cerr<<#x<<\"=\"<<x<<endl#define log(x, y) (log2(y) / log2(x)) // 以x为底y的对数#define WA cerr << \"Wrong Answer\" << endl#define init_inf32(x) memset(x, 0x3f, sizeof(x))#define init_inf64(x) memset(x, 0x3fll, sizeof(x))#define init_0(x) memset(x, 0, sizeof(x))#define Dec(x) fixed << setprecision(x)ll pw(ll x, ll P, ll mod = mod1){ll ret = 1;while(P){if(P & 1) ret = ret * x % mod;x = x * x % mod; P >>= 1;}return ret;}}using namespace Function;
}
using namespace OI;
// Init rnd()
mt19937 rnd(time(0) ^ clock());
// Constants
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const int N = 5e5 + 5, V = 1.5e5, MX = V * 3 + 5;int n, m;
int a[N], cnt[N];
int wdl = V + 1;
#define wdr (wdl + n)
class Segment{private:struct Tree{int mn, cnt;int res, lzy;} t[N << 2];#define mn(x) t[x].mn#define cnt(x) t[x].cnt#define res(x) t[x].res#define lzy(x) t[x].lzyvoid up(int x){mn(x) = min(mn(ls(x)), mn(rs(x)));cnt(x) = (mn(ls(x)) == mn(x)) * cnt(ls(x)) + (mn(rs(x)) == mn(x)) * cnt(rs(x));res(x) = res(ls(x)) + res(rs(x));}void push(int x, int val){mn(x) += val;res(x) = (mn(x) == 0) * cnt(x);lzy(x) += val;}void down(int x){if(lzy(x)){push(ls(x), lzy(x));push(rs(x), lzy(x));lzy(x) = 0;}}public:void build(int x = 1, int l = 1, int r = MX){if(l == r){cnt(x) = 1; res(x) = 1;return ;}int mid = mid(l, r);build(ls(x), l, mid);build(rs(x), mid + 1, r);up(x);}void modify(int ql, int qr, int val, int x = 1, int l = 1, int r = MX){if(ql > r || qr < l) return ;if(ql <= l && qr >= r){push(x, val);return ;}down(x); int mid = mid(l, r);modify(ql, qr, val, ls(x), l, mid);modify(ql, qr, val, rs(x), mid + 1, r);up(x);}int query(int ql, int qr, int x = 1, int l = 1, int r = MX){if(ql <= l && qr >= r){return res(x);} down(x);int mid = mid(l, r);if(qr <= mid) return query(ql, qr, ls(x), l, mid);if(ql > mid) return query(ql, qr, rs(x), mid + 1, r);return query(ql, qr, ls(x), l, mid) + query(ql, qr, rs(x), mid + 1, r);}void add(int x, int fu = 1){int New = x - cnt[x] + 1 - (fu == 1);modify(New, New, fu);cnt[x] += fu;}
} T;
void init(){cin >> n >> m;T.build();rep(i, 1, n){cin >> a[i];a[i] += wdl; T.add(a[i], 1);}while(m--){int p, x; cin >> p >> x;if(p != 0){if(a[p] <= wdr) T.add(a[p], -1);else --cnt[a[p]];a[p] = x + wdl;if(a[p] <= wdr) T.add(a[p], 1);else ++cnt[a[p]];}else{// 右边覆盖去除/加入,左边影响不到不用管if(x == 1){if(cnt[wdr]) T.modify(wdr - cnt[wdr] + 1, wdr, -1);--wdl;}else{++wdl;if(cnt[wdr]) T.modify(wdr - cnt[wdr] + 1, wdr, 1);}}cout << T.query(wdl + 1, wdr) << "\n";}
}
void solve(){}signed main(){
//	myfreopen;I_love_you;init();int T = 1;
//	cin >> T;while(T--){solve();}return 0;
}
/*things to check:
* Will it MLE?
* Is array big enough?
* Do you need long long?
* Is inf big enough?
* max or min?
* Yes,No or YES,NO?
* Is there anything extra to output?
* Did you Countershoot?
* Have you measured the limit data?
* More measurements should be cleared!!!
*/