LOJ#3094. 「BJOI2019」删数

之前做atcoder做到过这个结论结果我忘了。。。

em，就是\([1,n]\)之间每个数\(i\)，然后\([i - cnt[i] + 1,i]\)可以放一条线段，没被线段放的地方就是需要改的数的总和

之后我们线段树维护区间最小值以及个数

我们要注意如果+1后使得一个本来在\([1,N]\)的点越出了范围，那么就要把这个区间给删掉，-1同理，要加进来

值域开成\(N + 2M\)也就是\(4.5*10^{5}\)即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 500005

#define ba 47

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MAXV = 150000,LEN = 450000;

int N,M;

int a[MAXN],d;

int cnt[LEN + 5];

int getpos(int x) {

    return x - d + MAXV;

}

struct node {

    int l,r,val,cnt,lz;

}tr[LEN * 4 + 5];

void update(int u) {

    tr[u].val = min(tr[u << 1].val,tr[u << 1 | 1].val);

    tr[u].cnt = 0;

    if(tr[u].val == tr[u << 1].val) tr[u].cnt += tr[u << 1].cnt;

    if(tr[u].val == tr[u << 1 | 1].val) tr[u].cnt += tr[u << 1 | 1].cnt;

}

void build(int u,int l,int r) {

    tr[u].l = l;tr[u].r = r;

    if(l == r) {tr[u].cnt = 1;return;}

    int mid = (l + r) >> 1;

    build(u << 1,l,mid);

    build(u << 1 | 1,mid + 1,r);

    update(u);

}

void addlz(int u,int v) {

    tr[u].val += v;tr[u].lz += v;

}

void pushdown(int u) {

    if(tr[u].lz) {

	addlz(u << 1,tr[u].lz);

	addlz(u << 1 | 1,tr[u].lz);

	tr[u].lz = 0;

    }

}

void add(int u,int l,int r,int v) {

    if(tr[u].l == l && tr[u].r == r) {

	addlz(u,v);

	return;

    }

    pushdown(u);

    int mid = (tr[u].l + tr[u].r) >> 1;

    if(r <= mid) add(u << 1,l,r,v);

    else if(l > mid) add(u << 1 | 1,l,r,v);

    else {add(u << 1,l,mid,v);add(u << 1 | 1,mid + 1,r,v);}

    update(u);

}

pii Query(int u,int l,int r) {

    if(tr[u].l == l && tr[u].r == r) return mp(tr[u].val,tr[u].cnt);

    pushdown(u);

    int mid = (tr[u].l + tr[u].r) >> 1;

    if(r <= mid) return Query(u << 1,l,r);

    else if(l > mid) return Query(u << 1 | 1,l,r);

    else {

	pii a = Query(u << 1,l,mid),b = Query(u << 1 | 1,mid + 1,r);

	if(a.fi > b.fi) swap(a,b);

	if(a.fi == b.fi) a.se += b.se;

	return a;

    }

}

void Solve() {

    read(N);read(M);

    build(1,1,LEN);

    for(int i = 1 ; i <= N ; ++i) {

	read(a[i]);

	a[i] += MAXV;

	add(1,a[i] - cnt[a[i]],a[i] - cnt[a[i]],1);

	cnt[a[i]]++;

    }

    int p,x;

    for(int i = 1 ; i <= M ; ++i) {

	read(p);read(x);

	if(p == 0) {

	    if(x == 1) {

		if(cnt[getpos(N)]) {add(1,getpos(N) - cnt[getpos(N)] + 1,getpos(N),-1);}

	    }

	    else {

		if(cnt[getpos(N + 1)]) {add(1,getpos(N + 1) - cnt[getpos(N + 1)] + 1,getpos(N + 1),1);}

	    }

	    d += x;

	}

	else {

	    if(a[p] <= getpos(N)) {

		add(1,a[p] - cnt[a[p]] + 1,a[p] - cnt[a[p]] + 1,-1);

	    }

	    cnt[a[p]]--;

	    a[p] = x - d + MAXV;

	    if(a[p] <= getpos(N)) {

		add(1,a[p] - cnt[a[p]],a[p] - cnt[a[p]],1);

	    }

	    cnt[a[p]]++;

	}

	pii res = Query(1,getpos(1),getpos(N));

	int ans = 0;

	if(res.fi == 0) ans = res.se;

	out(ans);enter;

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

巴特西

【LOJ】#3094. 「BJOI2019」删数

LOJ#3094. 「BJOI2019」删数

最新文章

热门文章