#include <iostream>
#include <unordered_map>
#include <string>
#include <set>
using namespace std;
const int N = 1e5 + 5;
unordered_map<double, int> ac;
set<double> pos;
struct node
{
string op;
double a, b, c, x;
int p;
} e[N];
string op;
int m, top, idx;
bool st[N];
double a, b, c, x;
int stk[N];
int get(double x)
{
if (ac.count(x) == 0)
ac[x] = ++idx;
return ac[x];
}
int tr[N], tr1[N];
int lowbit(int x)
{
return x & -x;
}
void add(int tr[], int x, int c)
{
for (int i = x; i <= idx; i += lowbit(i))
tr[i] += c;
}
int sum(int tr[], int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i))
res += tr[i];
return res;
}
int main()
{
int x, c;
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> m;
for (int i = 1; i <= m; i++)
{
cin >> op, e[i].op = op;
if (op == "Add")
{
cin >> e[i].a >> e[i].b >> e[i].c;
c = e[i].c, a = e[i].a, b = e[i].b;
e[i].x = (c - b) / a, stk[++top] = i, pos.insert(e[i].x);
}
else if (op == "Query")
cin >> e[i].x, pos.insert(e[i].x);
else
cin >> e[i].p;
}
for (double t : pos)
if (ac.count(t) == 0)
ac[t] = ++idx;
// for (int i = 1; i <= m; i++)
// {
// cout << "val:" << e[i].x << " pos:" << ac[e[i].x] << endl;
// }
for (int i = 1; i <= m; i++)
{
op = e[i].op;
if (op == "Add")
{
x = ac[e[i].x];
if (e[i].a > 0)
add(tr, x, 1);
else
add(tr1, x, 1);
}
else if (op == "Del")
{
x = e[i].p;
if (st[x])
continue;
if (e[stk[x]].a > 0)
add(tr, ac[e[stk[x]].x], -1);
else
add(tr1, ac[e[stk[x]].x], -1);
}
else
cout << sum(tr, ac[e[i].x] - 1) + (sum(tr1, idx) - sum(tr1, ac[e[i].x])) << "\n";
}
}
萌新刚学五天BIT,并且已经四天没写了(
我的思路是,先读入所有相关x,离散化获得坐标,然后根据x前的系数判断x与(c-b)/a的大于小于关系,以此来建立两个维护两种关系的BIT。 然后,对于大于关系BIT,每次输出小于x的(c-b)/a个数,对于小于关系BIT,每次输出大于x的(c-b)/a个数。
由于我很蒻,所以代码可能漏洞百出,望大佬们看看我的代码哪里有问题,或者思路哪里有问题呢?