- 本蒟蒻有点 zz ,首先想到的是二分+线段树。因为不能下数据,所以在线下造了 5、6 组随机大样例,且都过了(用第一篇和第二篇题解作为标程),但是在洛谷上全 WA ,求助大佬检查思路和代码的正确性 QwQ 。
4
2 2 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 倍。
//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;
}