树状数组一眼题求助,0分
查看原帖
树状数组一眼题求助,0分
833124
BIOS楼主2023/8/4 22:03
#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个数。

由于我很蒻,所以代码可能漏洞百出,望大佬们看看我的代码哪里有问题,或者思路哪里有问题呢?

2023/8/4 22:03
加载中...