BZOJ-1563-郁闷的出纳员（权值线段树）
2024-09-05 09:04:07
偏移量要考虑清楚。
#include <bits/stdc++.h>
using namespace std;
const int N=4e5+10;
const int BASE=1e5+1;
const int RIGHT=3e5+5e4;
int segtree[N<<2],lazy[N<<2];
void pushdown(int rt)
{
if (lazy[rt]) {
lazy[rt<<1]=lazy[rt<<1|1]=1;
segtree[rt<<1]=segtree[rt<<1|1]=0;
lazy[rt]=0;
}
}
void Update(int val,int l,int r,int rt)
{
if (l==r) {
segtree[rt]++;
return ;
}
pushdown(rt);
int mid=(r+l)>>1;
if (val<=mid) {
Update(val,l,mid,rt<<1);
}
else {
Update(val,mid+1,r,rt<<1|1);
}
segtree[rt]=segtree[rt<<1]+segtree[rt<<1|1];
}
void Delete(int L,int R,int l,int r,int rt)
{
if (L<=l&&r<=R) {
lazy[rt]=1;
segtree[rt]=0;
return ;
}
pushdown(rt);
int mid=(l+r)>>1;
if (L<=mid) {
Delete(L,R,l,mid,rt<<1);
}
if (mid<R) {
Delete(L,R,mid+1,r,rt<<1|1);
}
segtree[rt]=segtree[rt<<1]+segtree[rt<<1|1];
}
int Query(int val,int l,int r,int rt)
{
if (l==r) {
return l;
}
pushdown(rt);
int mid=(l+r)>>1;
if (segtree[rt<<1]>=val) {
return Query(val,l,mid,rt<<1);
}
else {
return Query(val-segtree[rt<<1],mid+1,r,rt<<1|1);
}
}
int main()
{
char op[10];
int n,min_sal,tot=0,num,offset=0;
scanf("%d%d",&n,&min_sal);
for (int i=0;i<n;i++) {
scanf("%s%d",op,&num);
if (!strcmp(op,"I")) {
if (num>=min_sal) {
tot++;
Update(num+BASE+offset,1,RIGHT,1);
}
}
else if (!strcmp(op,"A")) {
offset-=num;
}
else if (!strcmp(op,"S")) {
offset+=num;
Delete(1,BASE+min_sal-1+offset,1,RIGHT,1);
}
else {
Delete(1,BASE+min_sal-1+offset,1,RIGHT,1);
if (num>segtree[1]) {
puts("-1");
}
else {
printf("%d\n",Query(segtree[1]-num+1,1,RIGHT,1)-BASE-offset);
}
}
}
printf("%d\n",tot-segtree[1]);
return 0;
}
最新文章
- fixed数据类型
- pullToRefreshListView的简单使用
- Apache rewrite
- 使用sklearn进行集成学习——理论
- Android开发遇到的坑（1）：Java中List的安全删除问题
- loadrunner备忘
- 【转】Android studio 解决64K超出链接数限制问题
- 我的conky配置
- VC++全局变量初始化
- urlrewrite伪静态 及多参数传递-附正则表达式语法 [轉]
- Where is the ActiveX Project Type for Delphi 10.1 Berlin
- 2014Esri全球用户大会——亮点系列之精彩应用案例
- LeetCode Javascript实现 283. Move Zeroes 349. Intersection of Two Arrays 237. Delete Node in a Linked List
- Pool：小对象缓存or复用
- Navicat 用ssh通道连接时总是报错 （报错信息：SSH:expected key exchange group packet form serve
- gateway + jwt 网关认证
- Kotlin入门
- Spring Security认证配置(三)
- go语言基础之append函数的使用
- backend community-driven web framework