题解：P14507 缺零分治 mexdnc

思路

先考虑朴素做法，那么先处理出每个 mex 最多有多少个，显然我们只关注一个从

1

至

x

的一段连续的数，从大到小考虑，每个数能取就取，一定最优，细节不是很多。复杂度

O(Tqn)

。

考虑优化，我们可以预处理出

s_i

表示把大于等于

i

的数能选的全选上的和，那么每次只需要二分查找第一个大于等于

m

的

s_i

，这时把若干

i

变成更小的数即可使和为

m

。

复杂度

O(Tq\log n)

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
	int num = 0,f = 1;
	char c = getchar();
	while(!isdigit(c))
	{
		if(c == '-')
		{
			f = -1;
		}
		c = getchar();
	}
	while(isdigit(c))
	{
		num = num * 10 + (c - '0');
		c = getchar();
	}
	return num * f;
}
struct node
{
    int a,b;
} a[110000];
int cnt[110000],sum[110000];
signed main()
{
	int T = read();
	while(T--)
	{
		int n = read(),q = read();
        for(int i = 1;i <= n;i++)
        {
            a[i].a = read();
			a[i].b = read();
        }
        cnt[0] = 2e9;
        int maxn = 0;
        for(int i = 1;i <= n;i++)
        {
            if(a[i].a == i - 1)
            {
                cnt[i] = min(cnt[i - 1],a[i].b);
            }
            else
            {
                cnt[i] = 0;
            }
            if(cnt[i])
            {
                maxn = max(maxn,i);
            }
        }
        cnt[maxn + 1] = 0;
        for(int i = maxn;i >= 1;i--)
        {
			sum[maxn - i + 1] = sum[maxn - i] + (cnt[i] - cnt[i + 1]) * i;
		}
		//cout << maxn << endl;
        while(q--)
        {
            int m = read();
            if(m == 0)
			{
            	if(a[1].a == 0)
            	{
            		cout << -1 << '\n';
				}
				else
				{
					cout << 1 << '\n';
				}
				continue;
			}
			int t = lower_bound(sum + 1,sum + maxn + 1,m) - sum - 1;
			if(t == maxn)
			{
				cout << -1 << '\n';
				continue;
			}
			m -= sum[t];
			int k = maxn - t;
			int cntt = (m - 1) / k;
			//cout << cntt << endl;
			if(m < k && t == 0)
			{
				cout << 2 << '\n';
			}
			else
			{
				cout << cnt[k + 1] + cntt + 1 << '\n';
			}
        }
	}
	return 0;
}

题解：P14507 缺零分治 mexdnc

文章操作

思路

相关推荐

评论

题解：P14507 缺零分治 mexdnc