【NOIP2017提高A组集训10.28】序列操作

时间:2022-12-16 23:38:52

Description:

一开始有n个非负整数hi,接下来会进行m次操作,第i次操作给出一个数c[i],要求你选出c[i]个大于零的数并将它们减去1。
问最多可以进行多少轮操作后无法操作(即没有c[i]个大于零的数)
1<=n,m<=1000000

题解:

对于一个数据结构学傻的人来说,一上来就会上什么平衡树之类的东西。

每次去c个,显然取当前最大的c个会优。
但是你发现如果对最大的c个数-1,也许相对顺序会变,那怎么做呢?
假设现在是[2,2,3,3,4,4],c=3,对前三大的减1,会变成:
[2,2,3,2,4,4]顺序就变了,然而你发现会改变的一定是和第c大的值一样的,对右边减1,可以转成对左边减1,至于确定区间可以用平衡树。

当然10^6平衡树怎么说也很难过,可以差分后用单点修改线段树维护,实际上数据水爆了。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;

const int N = 1e6 + 50;

int n, m, c[N], h;
int t[N * 8], st[N * 8], en[N * 8];

void Build(int i, int x, int y) {
if(x == y) {
t[i] = c[x] - c[x - 1];
st[i] = en[i] = (t[i] == 0);
return;
}
int m = x + y >> 1;
Build(i + i, x, m); Build(i + i + 1, m + 1, y);
t[i] = t[i + i] + t[i + i + 1];
st[i] = st[i + i] == m - x + 1 ? st[i + i] + st[i + i + 1] : st[i] = st[i + i];
en[i] = en[i + i + 1] == y - m ? en[i + i + 1] + en[i + i] : en[i] = en[i + i + 1];
}

int find(int i, int x, int y, int r) {
if(y == r) return t[i];
int m = x + y >> 1;
if(r <= m) return find(i + i, x, m, r);
return t[i + i] + find(i + i + 1, m + 1, y, r);
}

int findst(int i, int x, int y, int l) {
if(x == l) return st[i];
int m = x + y >> 1;
if(l > m) return findst(i + i + 1, m + 1, y, l);
int v = findst(i + i, x, m, l);
return v == m - l + 1 ? st[i + i + 1] + v : v;
}

int finden(int i, int x, int y, int r) {
if(y == r) return en[i];
int m = x + y >> 1;
if(r <= m) return finden(i + i, x, m, r);
int v = finden(i + i + 1, m + 1, y, r);
return v == r - m ? en[i + i] + v : v;
}

void change(int i, int x, int y, int l, int c) {
if(x == y) {
t[i] += c;
st[i] = en[i] = (t[i] == 0);
return;
}
int m = x + y >> 1;
if(l <= m) change(i + i, x, m, l, c); else change(i + i + 1, m + 1, y, l, c);
t[i] = t[i + i] + t[i + i + 1];
st[i] = st[i + i] == m - x + 1 ? st[i + i] + st[i + i + 1] : st[i] = st[i + i];
en[i] = en[i + i + 1] == y - m ? en[i + i + 1] + en[i + i] : en[i] = en[i + i + 1];
}

void read(int &x) {
char c = ' '; for(; c < '0' || c > '9'; c= getchar());
x = 0; for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
}

int main() {
freopen("sequence.in", "r", stdin);
freopen("sequence.out", "w", stdout);
scanf("%d %d", &n, &m);
fo(i, 1, n) read(c[i]);
sort(c + 1, c + n + 1);
Build(1, 1, n);
fo(i, 1, m) {
read(h);
int sum = find(1, 1, n, n - h + 1);
if(sum <= 0) {
printf("%d\n", i - 1);
return 0;
}
int en0 = h == 1 ? 0 : findst(1, 1, n, n - h + 2);
int st0 = h == n ? 0 : finden(1, 1, n, n - h + 1);
change(1, 1, n, n - h + 1 - st0, -1);
if(n - h + 1 - st0 + en0 + 1 <= n) change(1, 1, n, n - h + 1 - st0 + en0 + 1, 1);
if(n - h + en0 + 2 <= n) change(1, 1, n, n - h + en0 + 2, -1);
}
printf("%d\n", m);
}