下载了第一个数据,大概在第223个输出中差了1(样例53,我52),然后结果就差了几十
这题我调了几个小时,真的完全调不出来啊。。。
以下是我的代码
#include<bits/stdc++.h>
#define lowbit(x) x & -x
using namespace std;
const int N = 3e6+10;
const int LIM = 2e6+10;
int n,m,a[N],c1[N],c2[N];
int q1,q2,q3,q4,q5; // q1,q2,q3为a,b,c q4为i q5为k
string op; // 操作字符,即Add,Del和Query
struct node{ // 存储规则的结构体,id为编号,val为不等式化简后的数值,mode为大于/小于情况(mode=1为x>val,mode=2为x<val,mode=3是特殊规则(a=0))
// de是判断是否已被删除
int id,val,mode;
bool de;
}bds[N];
inline void add(int c[],int x,int val){
while(x<=LIM){
c[x] += val;
x += lowbit(x);
}
}
inline int find(int c[],int x){
int res = 0;
while(x){
res += c[x];
x -= lowbit(x);
}
return res;
}
int main(){
//freopen("P5482_1.in","r",stdin);
//freopen("fjs.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int rest,adnum,idx; //rest为恒成立不等式数量:对于ax+b>c,有a=0,b>c
int p;
cin>>n;
for(int i=1;i<=n;i++){
cin>>op;
if(op=="Add"){
cin>>q1>>q2>>q3;
if(q1==0){ // 不等式恒成立,则bds[i].val = 1。不等式恒不成立,则bds[i].val = 0
bds[++idx].id = idx;
bds[idx].mode = 3;
if(q2>q3){
rest++;
bds[idx].val = 1;
}
}
else if(q1>0){
adnum = (q3-q2)/q1;
if(adnum<0 && (q2-q3)%q1) adnum--;
if(adnum<-1e6) adnum = -1e6-1; //边界条件:如果abs(化简结果)>1e6,则改为1e6+1
else if(adnum>1e6) adnum = 1e6+1;
adnum += 1e6+3; // 对于a>0的情况,全部+1e6+3,防止出现负数
add(c1,adnum,1);
bds[++idx].val = adnum;
bds[idx].id = idx;
bds[idx].mode = 1;
}
else{
adnum = (q3-q2)/q1;
if(adnum>=0 && (q3-q2)%q1) adnum++;
if(adnum<-1e6) adnum = -1e6-1;
else if(adnum>1e6) adnum = 1e6+1;
adnum = 1e6+3-adnum; // 由于a<0时均为x<val,但是树状数组只会判断val<x的数量,因此对每一项都按1e6+3取反,此时大于k的会转换成小于k的
add(c2,adnum,1);
bds[++idx].val = adnum;
bds[idx].id = idx;
bds[idx].mode = 2;
}
}
else if(op=="Del"){
cin>>q4;
p = q4;
if(bds[p].de) continue;
if(bds[p].mode==3){
rest -= bds[p].val;
//printf("%d",rest);
continue;
}
bds[p].de = true;
if(bds[p].mode==1) add(c1,bds[p].val,-1);
else add(c2,bds[p].val,-1);
}
else{
cin>>q5;
printf("%d\n",find(c1,q5+1e6+2)+find(c2,1e6+2-q5)+rest); //由于a<0的情况有取反,故查询a<0情况数量时也取反
}
}
return 0;
}