样例没过,感觉没问题。
查看原帖
样例没过,感觉没问题。
1273463
Lin_Ziluo楼主2025/1/15 11:54
#include <bits/stdc++.h>
using namespace std;
bool del[100010];
int root1,tot1,a1,b1,c1,val1[100010],siz1[100010],lft1[100010],rgt1[100010],key1[100010];
void up1(int u){
	siz1[u] = siz1[lft1[u]] + siz1[rgt1[u]] + 1;
}
int getnew1(int k){
	tot1++;
	siz1[tot1] = 1;
	val1[tot1] = k;
	key1[tot1] = rand();
	return tot1;
}
void split1(int u,int &x,int &y,int k){
	if (!u)
		x = y = 0;
	else{
		if (val1[u] <= k){
			x = u;
			split1(rgt1[u],rgt1[u],y,k);
		}else{
			y = u;
			split1(lft1[u],x,lft1[u],k);
		}
		up1(u);
	}
}
int merge1(int x,int y){
	if (!x || !y)
		return x + y;
	if (key1[x] < key1[y]){
		rgt1[x] = merge1(rgt1[x],y);
		up1(x);
		return x;	
	}else{
		lft1[y] = merge1(x,lft1[y]);
		up1(y);
		return y;
	}
}
int root2,tot2,a2,b2,c2,val2[100010],siz2[100010],lft2[100010],rgt2[100010],key2[100010];
void up2(int u){
	siz2[u] = siz2[lft2[u]] + siz2[rgt2[u]] + 1;
}
int getnew2(int k){
	tot2++;
	siz2[tot2] = 1;
	val2[tot2] = k;
	key2[tot2] = rand();
	return tot2;
}
void split2(int u,int &x,int &y,int k){
	if (!u)
		x = y = 0;
	else{
		if (val2[u] >= k){
			x = u;
			split2(rgt2[u],rgt2[u],y,k);
		}else{
			y = u;
			split2(lft2[u],x,lft2[u],k);
		}
		up2(u);
	}
}
int merge2(int x,int y){
	if (!x || !y)
		return x + y;
	if (key2[x] < key2[y]){
		rgt2[x] = merge2(rgt2[x],y);
		up2(x);
		return x;	
	}else{
		lft2[y] = merge2(x,lft2[y]);
		up2(y);
		return y;
	}
}
int num,lim[100010],var[100010],cnt;
int main(){
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++){
		string op;
		cin >> op;
		if (op == "Add"){
			cnt++;
			int a,b,c;
			cin >> a >> b >> c;
			c -= b;
			if (a > 0){
				int tmp = floor(1.0 * c / a) + 1;
				split1(root1,tmp,a1,b1);
				root1 = merge1(merge1(a1,getnew1(tmp)),b1);
				var[cnt] = 1;
				lim[cnt] = tmp;
			}else if (a < 0){
				int tmp = ceil(1.0 * c / a) - 1;
				split2(root2,tmp,a2,b2);
				root2 = merge2(merge2(a2,getnew2(tmp)),b2);
				var[cnt] = 2;
				lim[cnt] = tmp;
			}else{
				var[cnt] = 3;
				if (c < 0){
					num++;
					lim[cnt] = 1;
				}else
					lim[cnt] = 0;
			}
		}else if (op == "Del"){
			int i;
			cin >> i;
			if (del[i])
				continue;
			del[i] = true;
			if (var[i] == 1){
				split1(root1,a1,c1,lim[i]);
				split1(a1,a1,b1,lim[i] - 1);
				b1 = merge1(lft1[b1],rgt1[b1]);
				root1 = merge1(merge1(a1,b1),c1);
			}else if (var[i] == 2){
				split2(root2,a2,c2,lim[i]);
				split2(a2,a2,b2,lim[i] + 1);
				b2 = merge2(lft2[b2],rgt2[b2]);
				root2 = merge2(merge2(a2,b2),c2);
			}else
				num -= lim[i];
		}else{
			int k;
			cin >> k;
			split1(root1,a1,b1,k);
			int ret1 = siz1[a1];
			root1 = merge1(a1,b1);
			split2(root2,a2,b2,k);
			int ret2 = siz2[a2];
			root2 = merge2(a2,b2);
			cout << num + ret1 + ret2 << endl;
		}
	}
	return 0;
}

输出了

2
1
0
1
2025/1/15 11:54
加载中...