HDU 4614 Vases and Flowers (2013多校第二场线段树) (二)
e(int l,int r,int num,int k) {
if(l == edge[num].l && r == edge[num].r) {
edge[num].lazy = k;
edge[num].sum = (edge[num].r - edge[num].l + 1) * k;
return ;
}
down(num);
if(r <= edge[num].mid) {
update(l,r,L(num),k);
} else if(l > edge[num].mid) {
update(l,r,R(num),k);
} else {
update(l,edge[num].mid,L(num),k);
update(edge[num].mid + 1,r,R(num),k);
}
up(num);
}
int query(int l,int r,int num) {
if(l == edge[num].l && r == edge[num].r) {
return edge[num].sum;
}
down(num);
if(r <= edge[num].mid) {
return query(l,r,L(num));
} else if(l > edge[num].mid) {
return query(l,r,R(num));
} else {
return query(l,edge[num].mid,L(num)) + query(edge[num].mid + 1,r,R(num));
}
}
void test(int n) {
for(int i=1; i<=3*n; i++) {
printf("l:%d r:%d sum:%d lazy:%d\n",edge[i].l,edge[i].r,edge[i].sum,edge[i].lazy);
}
}
int main() {
int n,m,i,t;
cin >> t;
while(t --) {
scanf("%d%d",&n,&m);
int a,b,c;
build(1,n,1);
for(i=0; i> 1;
if(mid - (b + 1) + 1- query(b+1,mid,1) >= 1) {
minn = min(minn,mid);
high = mid - 1;
} else {
low = mid + 1;
}
}
int tmp = n - minn + 1 - query(minn,n,1) ;
if(c >= tmp) c = tmp; ·
low = minn,high = n;
int maxx = INF;
while(low <= high) {
mid = (low + high) >> 1;
tmp = mid - minn + 1 - query(minn,mid,1) ;
if(tmp == c) {
maxx = min(maxx,mid);
high = mid - 1;
} else if(tmp > c) {
high = mid - 1;
} else {
low = mid + 1;
}
}
printf("%d %d\n",minn-1,maxx-1);
update(minn,maxx,1,1);
} else {
printf("%d\n",query(b+1,c+1,1));
update(b+1,c+1,1,0);
}
}
puts("");
}
return 0;
}
| 评论 |
|
|