题解 P5482 【[JLOI2011]不等式组】
Zesty_Fox
2020-10-13 10:24:26
先来分析一下题目。
显然，对于每一个添加的不等式，有3种情况：
1. $a<0$ 。此时可转换为 $x < {{a} \over {c-b}} $ 。
但是，我们发现 $ {a} \over {c-b} $ 这货是实数，容易产生误差，不好处理。
但我们又发现，询问的 $k$ 一定是整数。于是，我们可以把上面不等式转换为整数。
怎么转换？显然对于 $\forall x \in \mathbb{Z} , x < a \iff x< \lceil a \rceil$。
所以，这不就转化成 $x < \lceil {{a} \over {c-b}} \rceil$ 了吗。
2. $a=0$ 。此时直接判断是否有 $b>c$ 。若有，则在树状数组中全部 $+1$ ；反之则不变。
3. $a>0$ 。与第一种情况类似，可以转化成 $x > \lfloor {{a} \over {c-b}} \rfloor$ 。
那么，我们只要把上面提到的 $\lceil {{a} \over {c-b}} \rceil$ 、 $ \lfloor {{a} \over {c-b}} \rfloor $ 和询问提到的所有数放在一起离散化一下，用树状数组统计即可。
最后注意一个坑人的点：一个不等式可能被多次删除，这时候就不要重复统计了。
Code：(236ms)
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=100010;
struct Operation{int typ,a,b,c,val;}p[N];
int n,cnt,id[N<<1],cntd,raw[N<<1],vis[N<<1];
//raw即为离散化数组；id[i]则记第i条添加的不等式序号为多少
struct TA{//树状数组+查分
#define lowbit(x) ((x)&(-(x)))
int c[N<<1];
inline void add(int x,int val){
for(;x<=cnt+1;x+=lowbit(x)) c[x]+=val;
}
inline void modify(int l,int r,int val){ //区间加
add(l,val);add(r+1,-val);
}
int query(int x){//单点查询
int res=0;
for(;x>0;x-=lowbit(x)) res+=c[x];
return res;
}
#undef lowbit
}ta;
int main(){
cin>>n;
for(int i=1;i<=n;i++){ //先把操作存起来
char op[8];int a,b,c;
scanf("%s",op);
if(op[0]=='A'){
scanf("%d%d%d",&a,&b,&c);
p[i]=(Operation){1,a,b,c};
if(a<0) p[i].val=ceil(1.0*(c-b)/a);
else if(a>0) p[i].val=floor(1.0*(c-b)/a);
id[++cntd]=i;
raw[++cnt]=p[i].val;
}
if(op[0]=='Q'){
scanf("%d",&a);
p[i]=Operation{2,a};
raw[++cnt]=a;
}
if(op[0]=='D'){
scanf("%d",&a);
p[i]=Operation{3,a};
}
}
sort(raw+1,raw+cnt+1);cnt=unique(raw+1,raw+cnt+1)-raw-1;
for(int i=1;i<=n;i++){
//把所有的数值改为离散化后的值
if(p[i].typ==1) p[i].val=lower_bound(raw+1,raw+cnt+1,p[i].val)-raw;
if(p[i].typ==2) p[i].a=lower_bound(raw+1,raw+cnt+1,p[i].a)-raw;
}
for(int i=1;i<=n;i++){
if(p[i].typ==1){
//判断+修改
if(p[i].a<0) ta.modify(1,p[i].val-1,1);
else if(p[i].a>0) ta.modify(p[i].val+1,cnt,1);
else ta.modify(1,cnt,p[i].b>p[i].c?1:0);
}
if(p[i].typ==2) printf("%d\n",ta.query(p[i].a));
if(p[i].typ==3){
int x=id[p[i].a];
if(vis[x]) continue;
vis[x]=1;
if(p[x].a<0) ta.modify(1,p[x].val-1,-1);
else if(p[x].a>0) ta.modify(p[x].val+1,cnt,-1);
else ta.modify(1,cnt,p[x].b>p[x].c?-1:0);
}
}
return 0;
}
```