社区讨论
求调:必关、马蜂良好
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 条回复,欢迎继续交流。
正在加载回复...