萌新妹子刚学 OI 3 秒求助:求教思路与代码的正确性 QaQ

本蒟蒻有点 zz ，首先想到的是二分+线段树。因为不能下数据，所以在线下造了 5、6 组随机大样例，且都过了（用第一篇和第二篇题解作为标程），但是在洛谷上全 WA ，求助大佬检查思路和代码的正确性 QwQ 。

按照样例阐述：

CPP

4
2 2 1 1

假设第一个人使用的颜色区间是 $[1,a[1]]$ ，那么就把这段区间覆盖为 1 。如图：

1	2	3	4	5	6	7	8	9	10	11	12
1	1	1	1	0	0	0	0	0	0	0	0

对于第二个人，二分

[1,12]

中的某个位置

pos

，

pos

的位置代表当前第 1 号将军和第 2 号将军共同使用颜色的区间为

[1,pos]

，这个位置应该是能使得

pos-sum(1,pos)>=a(2)

的(

sum(l,r)

为区间

[l,r]

的和)，也就是能同时满足第 1 号将军和第 2 号将军的最靠左边的位置（也就是能满足二者的最少的颜色）。

找到这个位置后，对于第 3 号将军，显然之前被第 1 号将军占用的颜色现在都应该变成 0 （因为应该都可以被使第 3 号将军使用了），而被第 2 号将军占用的颜色第 3 号将军不能使用，所以自然的想到对于

[1,pos]

取反，对于

[pos+1,12]

全部覆盖为 0 。那么现在变为：

1	2	3	4	5	6	7	8	9	10	11	12
0	0	0	0	1	1	1	1	0	0	0	0

重复以上操作直到第

n-1

号将军，因为对于第

n

号将军要排除第

n-1

号将军和第 1 号将军的共同影响。这只需要把最后第

n-1

号将军和第 1 号将军求交就可以了。求交之后同样用二分的方法找对于第

n

号将军的

pos

。

最后答案就是过程中最大的

pos

。

Tips:

把 $[pos+1,12]$ 全部覆盖为 0 的原因

因为有可能之前是这种情况， $(pos=7)$ ：

1 2 3 4 5 6 7 8 9 10 11 12
1 1 1 0 0 0 1 1 0 1 1 0

显然 $[8,9],[10,11]$ 对于下一个将军都应该是 0 。

为什么右区间取 12 ?

~~因为我是 zz 。~~ 右区间最大应该取 $\max(a(i))$ 的 3 倍，因为对于第 $i-1,i,i+1$ 号将军来说最劣不会超过他们需求总数的 3 倍。

1	2	3	4	5	6	7	8	9	10	11	12
1	1	1	0	0	0	1	1	0	1	1	0

The Code:

CPP

//Tips:
//1.线段树部分应该没有问题,是和暴力程序对拍过的.
//2.已经用了多组随机数据(都是卡满了的)和第一,二篇题解对拍,没有问题.求助QwQ.
//3.二分+线段树区间修改(覆盖),区间查询(求和),区间取反(0/1取反).
#include<bits/stdc++.h>
using namespace std;
const int maxN(2e4),maxA(1e5),maxSiz(maxA*3<<2);
int n,a[maxN+5],ans;
struct Segment_Tree{
	int R,sum[maxSiz+5],cvr[maxSiz+5],neg[maxSiz+5];
	void init(){for(int i(1);i<=maxN<<2;++i)cvr[i]=-1;}
	void psh_up(int u){sum[u]=sum[u<<1]+sum[u<<1|1];}
	void psh_cvr(int u,int l,int r,int tcvr){cvr[u]=tcvr,neg[u]=0,sum[u]=(r-l+1)*tcvr;}
	void psh_neg(int u,int l,int r){neg[u]^=1,sum[u]=(r-l+1)-sum[u];}
	void psh_dwn(int u,int l,int r){
		int mid(l+r>>1);
		if(cvr[u]!=-1)psh_cvr(u<<1,l,mid,cvr[u]),psh_cvr(u<<1|1,mid+1,r,cvr[u]);
		if(neg[u])psh_neg(u<<1,l,mid),psh_neg(u<<1|1,mid+1,r);
		cvr[u]=-1,neg[u]=0;
	}
	void updcvr(int u,int l,int r,int x,int y,int v){
		if(x<=l&&r<=y){psh_cvr(u,l,r,v);return;}
		psh_dwn(u,l,r);
		int mid(l+r>>1);
		if(x<=mid)updcvr(u<<1,l,mid,x,y,v);
		if(y>mid)updcvr(u<<1|1,mid+1,r,x,y,v);
		psh_up(u);
	}
	void updneg(int u,int l,int r,int x,int y){
		if(x<=l&&r<=y){psh_neg(u,l,r);return;}
		psh_dwn(u,l,r);
		int mid(l+r>>1);
		if(x<=mid)updneg(u<<1,l,mid,x,y);
		if(y>mid)updneg(u<<1|1,mid+1,r,x,y);
		psh_up(u);
	}
	int qry(int u,int l,int r,int x,int y){
		if(x<=l&&r<=y)return sum[u];
		psh_dwn(u,l,r);
		int mid(l+r>>1),tsum(0);
		if(x<=mid)tsum+=qry(u<<1,l,mid,x,y);
		if(y>mid)tsum+=qry(u<<1|1,mid+1,r,x,y);
		return tsum;
	}
}sgt;
int main(){
	//freopen("input.txt","r",stdin),
	//freopen("myans.out","w",stdout);
	scanf("%d",&n),sgt.R=maxA*3;
	for(int i(1);i<=n;++i)scanf("%d",&a[i]);
	sgt.updcvr(1,1,sgt.R,1,a[1],1);
	for(int i(2);i<=n-1;++i){//n要排除n-1和1的共同影响,单独处理.
		int l(1),r(maxA*3);
		while(l<r){
			int mid(l+r>>1);
			if(mid-sgt.qry(1,1,sgt.R,1,mid)>=a[i])r=mid;
			else l=mid+1;
		}
		ans=max(ans,l);
		sgt.updcvr(1,1,sgt.R,l+1,maxA*3,0),//l右边的都是0.
		sgt.updneg(1,1,sgt.R,1,l);//[1,l]都取反.
	}
	sgt.updcvr(1,1,sgt.R,1,a[1],1);//n-1与1求交.
	int l(1),r(maxA*3);
	while(l<r){
		int mid(l+r>>1);
		if(mid-sgt.qry(1,1,sgt.R,1,mid)>=a[n])r=mid;
		else l=mid+1;
	}
	printf("%d",max(ans,l));
	return 0;
}

萌新妹子刚学 OI 3 秒求助:求教思路与代码的正确性 QaQ

讨论操作

回复

相关推荐

萌新妹子刚学 OI 3 秒求助:求教思路与代码的正确性 QaQ