首页 > 其他分享 >HDU 4614 ——线段树+二分

HDU 4614 ——线段树+二分

时间:2022-12-15 22:13:18浏览次数:41  
标签:HDU qr int 线段 ql mid id seg 4614

//题意:茜茜学姐的情人节到了!众所周知,茜茜学姐喜欢帅气的学弟,所以她当然有很多学弟送的花瓶,据不完全统计,茜茜学姐有N个花瓶(标号为0~ N-1)。当然茜茜学姐也是个魅力四射的男孩子,所以他也自然会在这天收到很多的花花,当他在情人节这天收到花花时时,他会随机的选择一个瓶子A,
//从它开始遍历A,A+1, A+2, ..., N-1号瓶子,遇到空瓶子的话就放一朵花进去,直到花放完或没有瓶子,剩下的花将被残忍的丢弃。有时,他也会清理标号从a到b的花瓶(a <= b).花瓶里的花会被丢弃。任性又帅气的茜茜学姐!

//思路:就是二分维护边界点,然后用线段树维护就行(我这里拆开写了,这样思路感觉清晰一点,只是这样复杂度是O(loglog n))
#include<bits/stdc++.h>
using namespace std;
const int N = 50010;
struct bt {
int num;//区间装满花的瓶子数
int tag;//清空花标记,装满花标记
}seg[4 * N];
int T, n, m;
void update(int id) {
seg[id].num = seg[id * 2].num + seg[id * 2 + 1].num;
}
void build(int id, int l, int r) {
if (l == r) {
seg[id].num = 0;
seg[id].tag = -1;
return;
}
int mid = (l + r) / 2;
build(2 * id, l, mid); build(2 * id + 1, mid + 1, r);
update(id);
}
void pushdown(int id, int l, int r) {
int mid = (l + r) / 2;
if (seg[id].tag == -1) return;
seg[2 * id].tag = seg[2 * id + 1].tag = seg[id].tag;
seg[2 * id].num = (mid - l + 1) * seg[id].tag;
seg[2 * id + 1].num = (r - (mid + 1) + 1) * seg[id].tag;
seg[id].tag = -1;
return;
}
int sum(int id, int l, int r, int ql, int qr) {
if (l == ql && r == qr) {
return seg[id].num;
}
pushdown(id, l, r);
int mid = (l + r) / 2;
int ans = 0;
if (ql <= mid) return sum(2 * id, l, mid, ql, qr);
else if (qr > mid) return sum(2 * id + 1, mid + 1, r, ql, qr);
else {
return sum(2 * id, l, mid, ql, mid) + sum(2 * id + 1, mid + 1, r, mid + 1, qr);
}
}
void modify(int id, int l, int r, int ql, int qr, int d) {
if (l == ql && r == qr) {
seg[id].num = ((r - l) + 1) * d;
seg[id].tag = d;
return;
}
pushdown(id, l, r);
int mid = (l + r) / 2;
if (qr <= mid) modify(2 * id, l, mid, ql, qr, d);
else if (ql > mid) modify(2 * id + 1, mid + 1, r, ql, qr, d);
else {
modify(2 * id, l, mid, ql, mid, d);
modify(2 * id + 1, mid + 1, r, mid + 1, qr, d);
}
update(id);
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
build(1, 1, n);
int od, a, b;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &od, &a, &b);
a++;
if (od == 1) {
int emtbt = sum(1, 1, n, a, n);//花数
emtbt = n - a + 1 - emtbt;//空瓶数
//cout << emtbt << endl;
if (emtbt == 0)
{
puts("Can not put any one.\n");
continue;
}
if (emtbt < b) b = emtbt;
int l = a, r = n, pl = 0, pr = n;
while (l <= r) {
int mid = (l + r) / 2;
int w = sum(1, 1, n, a, mid);
w = mid - a + 1 - w;//空瓶数
if (w >= 1) {
pl = mid;
r = mid - 1;
}
else l = mid + 1;
}
l = pl, r = n;
while (l <= r) {
int mid = (l + r) / 2;
int w = sum(1, 1, n, pl, mid);
w = mid - pl + 1 - w;//空瓶数
if (w >= b) {
pr = mid;
r = mid - 1;
}
else l = mid + 1;
}
//cout << pl << " " << pr << endl;
modify(1, 1, n, pl, pr, 1);
printf("%d %d\n", pl - 1, pr - 1);
}
else {
b++;
int w = sum(1, 1, n, a, b);
modify(1, 1, n, a, b, 0);
printf("%d\n", w);
}
}
puts("");
}
return 0;
}

标签:HDU,qr,int,线段,ql,mid,id,seg,4614
From: https://www.cnblogs.com/Aacaod/p/16986117.html

相关文章

  • hdu:继续畅通工程(kruskal的MST并查集实现)
    ProblemDescription省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表......
  • hdu:小希的迷宫(并查集)
    ProblemDescription上次Gardon的迷宫城堡小希玩了很久,现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说......
  • HDU4801——思维,生成树(口糊)
    //题意:有坐标图上有N个点,每个点有一个收益,要求修n-1条路联通所有点。现在有一个免单机会,即免除一条路的花费,求max(免除花费的路的两端点的收益和/n-1条路的总花费)//思路:......
  • ICPC2020 南京J 吉司机线段树
    题目是一个序列。两个操作1对L,R里的所有数字对输入x取max。2询问L,R里某一位二进制位的1的个数。n是正常的200000用线段树来维护两个操作。先考虑第一个操作用吉司机......
  • AcWing 261. 旅馆 【线段树】
    [NOIP2015普及组]推销员题目背景NOIP2015普及组T4题目描述阿明是一名推销员,他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同,出口与入口是同一个,街道的一侧......
  • codeforces 1354D - Multiset (线段树或者2分)
    题目大意:已知一个数列an,我们每次可以添加一个数k,或者把第k大的数字去掉。问我们经过k次操作后,数列中任意1个剩余的数字。n,q<=1e6解题思路:首先最简单的思路是线段树。线段......
  • 线段树专题
    线段树专题线段树与树状数组的视频教程,非常清晰,强烈推荐一、线段树基础1.线段树简介线段树是算法竞赛中常用的用来维护区间信息的数据结构。线段树可以在很小的时间......
  • 线段简化的几种算法
    翻译自:https://www.codeproject.com/Articles/114797/Polyline-Simplification#headingDPN参考:https://www.codeproject.com/Articles/114797/Polyline-Simplification......
  • hdu:解方程(二分查找)
    ProblemDescription给定方程8x^4+7x^3+2x^2+3x+6==Y,请计算x在[0,100]范围内的解。Input输入数据首先是一个正整数T(1<=T<=100),表示有T组测试数据。接下来T......
  • hdu:人见人爱A^B(快速幂)
    ProblemDescription求A^B的最后三位数表示的整数。说明:A^B的含义是“A的B次方”Input输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A......