此题题解区似乎少一个离线解法，那我发一篇

思路

特判没有 $0$ $0$ 的情况：
- 当 $m=0$ 答案为 $1$ 。
- 当 $m!=0$ 答案为 $-1$ 。

设全局

mex

为

now

，那么。

当 $m=0$ 答案为 $-1$ 。
当 $m=now$ 答案为 $1$ 。
当 $1 \le m \le now$ 答案为 $2$ 。

以上结论很简单，请自行分析。

预处理

维护 $nxt$ 数组。
我们把样例分成这样：

令

nxt[0]=b[1]

先使

nxt[i]=min(nxt[i-1],b[i+1])

再使

nxt[i]-=nxt[i+1]

此时

nxt[i]

表示以

i-1

为结尾 分割数量 。

(图中

F

表示一开始的

nxt

)

对于 $m >now$

对于每一个询问，我们发现其答案其实就是第一行最大的 $mex$ 依次从长到短加其余能独立的长串，也可以只取其前缀并将未取到的并到第一行。
例如对于样例答案为 $4$ 。
要是我们这么做，显然答案与 $m$ 具有单调性。考虑离线维护。
我们将询问排个序。

$O(n+m)$

我们一个一个并，则可能会有 $\sum bi=1e14$ 个分割，会超时。

$O(n+q \log q)$

考虑很多分割的 $mex$ 是一样的，我 $nxt[i]$ 们已经维护了。
以 $i-1$ 为结尾 分割数量 $nxt[i]$ 。
所以我们每次尝试取尽量多个当前最大的分割，若能达到 $m$ 那就别拿。
伪代码如下：

if xq<=nxt[ed]//如果最大的分割数量够
  nxt[ed]-=xq
  now+=ed*xq
else
  now+=nxt[ed]*ed
  nxt[ed]=0
  ed--

（ed 表示最大的分割的位置，

xq=ceil((m-now)/ed)

）由于分割的结尾最多有

n

个，所以是

O(n+q \log q)

。

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

int n,m;

template<typename T>
inline void read(T &x) {
    x = 0;
    register char c = getchar();
    register short f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    x *= f;
}

template <typename T, typename... Args>

inline void read(T &x, Args &...temps)
{
	read(x), read(temps...);
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10;
		x /= 10;
	} while (x);
	while (top) putchar(sta[--top] + '0');

}

const int N=2e5+5;

struct nod{
	int a,b;
}q[N];
bool cmp(nod x,nod y){
	return x.a<y.a;
}
struct Q{
	int x,id;
}xl[N];
bool cmp1(Q x,Q y){
	return x.x<y.x;
}
int ans[N];
int nxt[N];
void solve()
{
	memset(nxt,0,sizeof nxt);
    memset(ans,0,sizeof ans);
    memset(xl,0,sizeof xl);
    memset(q,0,sizeof q);  
	read(n,m);
	int minn=0;	
	for(int i=1;i<=n;i++){
		read(q[i].a,q[i].b);
		if(q[i].a==0){
			minn=1;
		}
	}
	int maxx=0;
	int gs=0;
	int tot=0;
	sort(q+1,q+1+n,cmp);
	int fl=1;
	if(q[1].a!=0){
		for(int i=1;i<=m;i++){
			int x;
			read(x);
			if(x==0){
				cout<<1;
				puts("");
			}
			else{
				cout<<-1;
				puts("");
			}
		}
		return;
	}
	for(int i=2;i<=n;i++){
		if(q[i].a==q[i-1].a+1){
			fl=max(fl,q[i].a+1);
		}
		else{
			break;
		}
	}
	
	gs=q[1].b;
	maxx+=gs;
	nxt[1]=gs;
	int ed=1;
	for(int i=2;i<=n;i++){
		if(q[i].a!=q[i-1].a+1) break;
		gs=min(gs,q[i].b);
		nxt[i]=gs;
		if(nxt[i]) ed=i;
		maxx+=gs;
	}

	for(int i=1;i<=ed;i++){
		nxt[i]-=nxt[i+1];
	}

	for(int i=1;i<=m;i++){
		read(xl[i].x);
		xl[i].id=i;
	}
	int now=fl;

	sort(xl+1,xl+1+m,cmp1);

	int bb=1;
	nxt[ed]--;
	for(int i=1;i<=m;i++){

		if(xl[i].x>maxx){
			ans[xl[i].id]=-1;
			continue;
		}
		if(xl[i].x<minn){
			ans[xl[i].id]=-1;
			continue;
		}
		if(xl[i].x<fl){
			ans[xl[i].id]=2;
			continue;
		}
		if(xl[i].x==fl){
			ans[xl[i].id]=1;
			continue;
		}

		while(xl[i].x>now&&ed>=0){
			int xq=ceil(1.0*(xl[i].x-now)/(1.0*ed));

			if(xq<nxt[ed]){
				
				now+=xq*ed;
				bb+=xq;	
				nxt[ed]-=xq;		
			}
			else{
				now+=nxt[ed]*ed;
				bb+=nxt[ed];
				ed--;
			}
		}
		if(ed<0&&xl[i].x>now){
			ans[xl[i].id]=-1;
		}
		else ans[xl[i].id]=bb;
		//if((xl[i].x-fl)/ed)
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<'\n';
	}
}
signed main(){
	int T;
	read(T);
	while(T--){
		solve();
	}
	return 0;
}

码风一坨，请批判性鉴赏~

P14507 缺零分治 mexdnc 离线解法

文章操作

思路

预处理

对于 $m >now$

$O(n+m)$

$O(n+q \log q)$

代码

相关推荐

评论

P14507 缺零分治 mexdnc 离线解法

文章操作

思路

预处理

对于 m>nowm >nowm>now

O(n+m)O(n+m)O(n+m)

O(n+qlog⁡q)O(n+q \log q)O(n+qlogq)

代码

相关推荐

评论

对于 $m >now$

$O(n+m)$

$O(n+q \log q)$