社区讨论

求调:必关、马蜂良好

P5482[JLOI2011] 不等式组参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mkqx29sb
此快照首次捕获于
2026/01/23 21:28
4 周前
此快照最后确认于
2026/01/24 08:22
4 周前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int M = 1e6 + 100;
const int N = 1e5 + 100;
const int P = 1e6+1;
int c[2*M+100];
struct Node{
	int l;
	int r;
	int valid;
}A[N];
int cnt, n;

/// 树状数组模板 
int lowbit(int x){
    return x & (-x);
}
void add(int x, int y){
    for (int i = x; i <= 2*M; i += lowbit(i)) c[i] += y;
}
long long sum(int x){
    long long res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}

/// 映射函数,把我们真实的数字映射为树状数组的下标 
int T(int p){
	return p + P;
} 

/// 反映射函数
int R(int p){
	return p - P;
} 

/// 增加函数
void insert(int l, int r){
	add(l, 1);
	add(r+1, -1);
} 

/// 细节实现

//D函数
void D(){
	A[cnt].l = T(1);
	A[cnt].r = T(1e6+1);
	insert(A[cnt].l, A[cnt].r);
} 

//DN函数
void DN(){
	A[cnt].l = T(1e6+1);
	A[cnt].r = T(1e6+1);
	insert(A[cnt].l, A[cnt].r);
} 

//PN函数
void PN(int a, int b, int c){
	int p = (c - b) / a + 1; // 如果(c-b)/a是整除,则应当+1;如果有小数,按照c++,会向下取整,同样也要+1,故合并 
	if (p > P) DN(); // 如果x需要大于的这个数都已经超过了1e6,那么就没有比的必要了,直接当做恒不成立处理
	else if (p < -P) D(); // 如果x需要大于的这个数都小于-1e6,那在这个背景之下,我们可以认为他就是恒成立的 
	else{ // 其余是普通情况 
		A[cnt].l = T(p);
		A[cnt].r = T(1e6+1);
		insert(A[cnt].l, A[cnt].r);
	}
} 

//NN函数
void NN(int a, int b, int c){
	int p;
	// 这里需要分类讨论:
	// 1.如果(c-b)/a余0,且x要小于这个数,那么x的最大值为(c-b)/a-1;
	// 2.如果有余数的话,(c-b)/a有一个点几,但是c++回向下取整,正好就是我们想得到的
	if ((c - b) % a == 0) p = (c - b) / a + 1;
	else p = (c - b) / a;
	// 与PN函数同理,都需要根据p的大小判断一步
	if (p > P) D(); // 一个数必须小于另一个数,而另一个数都大于了1e6了,必须恒成立!!!
	else if (p < -p) DN();
	else{
		A[cnt].l = T(-1e6);
		A[cnt].r = T(p);
		insert(A[cnt].l, A[cnt].r);
	}
} 

//Add函数
void Add(){
	A[cnt].valid = true;
	int a, b, c;
	cin >> a >> b >> c;
	if (b > c and a >= 0){ // 恒成立 
		D(); 
	}
	else if (a == 0){ // 说明 b < c,恒不成立 
		DN();
	}
	else if (a > 0){ // 说明 x > (c-b)/a 
		PN(a, b, c);
	}
	else{ // 说明 x < (c-b)/a 
		NN(a, b, c);
	}
} 

// Del函数 
void Del(){
	int i; cin >> i;
	if (A[i].valid == false) return ;
	A[i].valid = false;
	add(A[i].l, -1);
	add(A[i].r+1, 1);
} 

// Query函数
void Query(){
	int k; cin >> k;
	cout << sum(T(k)) << endl;
} 

/// 大框架 
void solve(){
	string s;
	cin >> s;
	if (s == "Add"){
		cnt ++;
		Add();
	}
	if (s == "Del"){
		Del();
	}
	if (s == "Query"){
		Query();
	}
}
int main(){
	cin >> n;
	while (n --){
		solve();
	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...