全WA求调
查看原帖
全WA求调
741839
arrowpoint楼主2023/7/17 08:15

下载了第一个数据,大概在第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;
} 
2023/7/17 08:15
加载中...