【做题记录】 [JLOI2011]不等式组
超烦人的细节题!(本人调了两天 QAQ )
这里介绍一种只用到一只树状数组的写法(离线)。
树状数组的下标是:所有可能出现的数据进行离散化之后的值。
其含义为:当 \(x\) 离散化后值为 \(i\) 时能满足的不等式个数为 \(query(i)\) 个。
处理数据
首先我们先读入所有数据,并对数据处理:
\(\text{Add} ~a_i~b_i~c_i\) :
若 \(a_i>0\) 将 \(a_ix+b_i>c_i\) 转化成 \(x\ge t_i\) 的形式 。
若 \(a_i<0\) 将 \(a_ix+b_i>c_i\) 转化成 \(x\le t_i\) 的形式 。
并将 \(t_i\) 丢进离散化的序列中。
注意:所有的除法运算都是向 \(0\) 取整,还要注意除法变号问题等等。
\(\text{Del}\) :
在处理 \(\text{Add}\) 时提前记录第 \(x\) 个 \(\text{Add}\) 操作所对应的输入操作编号。
\(\text{Query}\) :
将 \(k_i\) 丢进离散化序列中。
之后将序列中的数离散化,给 \(\text{Add}\) 中的 \(t_i\) 和 \(\text{Query}\) 中的\(k_i\) 都附上一个离散化后的值( \(Instead_i\) ) 。
计算答案
\(\text{Add}\) :
若 \(a_i>0\) 则在 \([t_i,+\infty)\) 区间内的 \(Instead_x\) 都可以使不等式成立。
同理,若 \(a_i<0\) 则在 \((-\infty,t_i]\) 区间内的 \(Instead_x\) 都可以使不等式成立。
在区间内加 \(1\) 即可 。
\(\text{Del}\) 和 \(\text{Add}\) 几乎一致,变为区间减 \(1\) 。
\(\text{Query}~k_i\) 即可直接查询并输出 \(Query(Instead_i)\) 。
最后附上 100pts 代码:
#include<bits/stdc++.h>
using namespace std;
#define Maxn 100005
#define inf 0x7f7f7f7f
typedef long long ll;
inline int rd()
{
int x=0;
char ch,t=0;
while(!isdigit(ch = getchar())) t|=ch=='-';
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x=t?-x:x;
}
int n,tmp,tot,cnt;
map<int,int> mp;
int Ins_val[Maxn],hist[Maxn];
struct Data
{
int opt,t,Ins;
int pre,used;
}a[Maxn];
int tree[Maxn];
inline int lowbit(int x){ return x&(-x); }
void add(int x,int k)
{
while(x<=tot+1) tree[x]+=k,x+=lowbit(x);
}
int query(int x)
{
int ret=0;
while(x) ret+=tree[x],x-=lowbit(x);
return ret;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=rd();
string opt;
for(int i=1,x,y,z,A,B,C;i<=n;i++)
{
cin>>opt;
if(opt=="Add")
{
A=rd(),B=rd(),C=rd(),hist[++cnt]=i;
a[i].opt=2-(A>=0); // 当 a>=0 时 opt=1 ,否则 opt=2
if(A==0) a[i].t=(B>C)?(-inf+1):inf;
else if(A>0) a[i].t=(C-B)/A+(((C-B)>=0)?1:(((C-B)/A*A==(C-B))?1:0));
else a[i].t=(C-B)/A-(((C-B)>=0)?1:(((C-B)/A*A==(C-B))?1:0));
Ins_val[++tmp]=a[i].t;
}
if(opt=="Del")
{
a[i].pre=hist[rd()];
a[i].opt=a[a[i].pre].opt+2; // 当 a>=0 时 opt=3 ,否则 opt=4
a[i].t=a[a[i].pre].t;
}
if(opt=="Query") a[i].opt=5,a[i].t=rd(),Ins_val[++tmp]=a[i].t;
}
sort(Ins_val+1,Ins_val+1+tmp);
Ins_val[0]=-inf;
for(int i=1;i<=tmp;i++) if(Ins_val[i]!=Ins_val[i-1]) mp[Ins_val[i]]=++tot;
for(int i=1;i<=n;i++) a[i].Ins=mp[a[i].t];
for(int i=1;i<=n;i++)
{
if(a[i].t==inf) continue; // a==0 && b<c
if(a[i].opt==1) add(tot+1,-1),add(a[i].Ins,1); // a>0 || (a==0 && b>c)
if(a[i].opt==2) add(a[i].Ins+1,-1),add(1,1); // a<0
if(a[i].opt==3 && !a[a[i].pre].used) add(tot+1,1),add(a[i].Ins,-1),a[a[i].pre].used=1; // a>0 || (a==0 && b>c)
if(a[i].opt==4 && !a[a[i].pre].used) add(a[i].Ins+1,1),add(1,-1),a[a[i].pre].used=1; // a<0
if(a[i].opt==5) printf("%d\n",query(a[i].Ins));
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
最新文章
- 关于Spring中配置LocalSessionFactoryBean来生成SessionFactory
- Windows下安装pip(转自http://www.cnblogs.com/yuanzm/p/4089856.html)
- 基于SURF特征的目标检测
- elasticsearch + hive环境搭建
- Linux下的ip命令,除了ifconfig还有很多
- python添加tab键提示
- GOICE项目初探
- linux应用程序问题
- 数据挖掘R与SQL
- apt-get 安装ubuntu-tweak
- spring注解-@Transactional事务几点注意
- SmartSql 性能评测
- 通过for 来获取数组里面的电话
- vue 版本升级配置修改
- legend2---开发日志6(后端和前端如何相互配合(比如php,js,元素状态和数据改变))
- [转载]CMMI之功能点估算法:EI、EQ和EO
- 51nod 1042数字0-9的数量
- 分析 HTML 代码并提取数据
- (zxing.net)一维码UPC E的简介、实现与解码
- SpringBoot 异步线程简单三种样式
热门文章
- xxl-job <;=2.0.2 反序列化漏洞
- Xamarin UIProgressView自定义
- python工作中总结
- [PhpStorm]解决Cannot find declaration to go to
- 5cms使用sql语句给网站添加内容
- Linux系列(29) - rpm包命名规则(1)
- php 扫描url死链接
- 鸿蒙内核源码分析(汇编基础篇) | CPU在哪里打卡上班? | 百篇博客分析OpenHarmony源码 | v22.01
- 鸿蒙内核源码分析(调度队列篇) | 内核有多少个调度队列 | 百篇博客分析OpenHarmony源码 | v6.05
- Spring动态代理的生成-如何判断是使用JDK动态代理还是CGlib代理