1 条题解

  • 0
    @ 2025-6-25 15:37:23
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN = 500000;
    const int MAXM = 500000;
    int n, m;
    int ans[MAXM + 5]; // 第i个矩形的答案
    struct OP
    {
        // op==0:加入一个树 (x,y)
        // op>0: 需要查询 (1,1)~(x,y) 有多少树,把答案乘w后加入ans[op]
        int op, x, y, w;
    };
    bool operator<(const OP &a, const OP &b)
    {
        if (a.x != b.x)
            return a.x < b.x;
        if (a.y != b.y)
            return a.y < b.y;
        return a.op < b.op;//优先加树再询问
    }
    vector<OP> o;
    // 离散化y的辅助数组
    vector<int> temp;
    // 树状数组
    int t[MAXN + MAXM * 4 + 5], treeN;
    int lowbit(int x)
    {
        return x & (-x);
    }
    // 第x个数加k
    void update(int x, int k)
    {
        for (int i = x; i <= treeN; i += lowbit(i))
            t[i] += k;
    }
    // 返回前x个数的和
    int query(int x)
    {
        int res = 0;
        for (int i = x; i >= 1; i -= lowbit(i))
            res += t[i];
        return res;
    }
    signed main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            int x, y;
            cin >> x >> y;
            x++, y++;
            o.push_back((OP){0, x, y, 0});
            temp.push_back(y);
        }
        for (int i = 1; i <= m; i++)
        {
            ans[i] = 0;
            int x, y, xx, yy;
            cin >> x >> y >> xx >> yy;
            x++, y++, xx++, yy++;
            o.push_back((OP){i, xx, yy, 1});
            o.push_back((OP){i, x - 1, yy, -1});
            o.push_back((OP){i, xx, y - 1, -1});
            o.push_back((OP){i, x - 1, y - 1, 1});
            temp.push_back(yy);
            temp.push_back(y - 1);
        }
    
        // 对y离散化
        sort(temp.begin(), temp.end());
        treeN = 0;
        for (int i = 0; i < o.size(); i++)
        {
            o[i].y = lower_bound(temp.begin(), temp.end(), o[i].y) - temp.begin();
            // 让y离散化后从1开始
            o[i].y += 1;
            treeN = max(treeN, o[i].y);
        }
        // 按x坐标排序所有操作,然后依次处理
        sort(o.begin(), o.end());
        for (int i = 0; i < o.size(); i++)
        {
            //cout << o[i].op << " " << o[i].x << " " << o[i].y << " " << o[i].w << ": ";
            if (o[i].op == 0)
            {
                update(o[i].y, 1);
                //cout << "add (" << o[i].x << "," << o[i].y << ")\n";
            }
            else
            {
                ans[o[i].op] += o[i].w * (query(o[i].y));
                //cout << "ans[" << o[i].op << "]+=" << o[i].w << "*" << query(o[i].y) << "\n";
            }
        }
        for (int i = 1; i <= m; i++)
            cout << ans[i] << "\n";
        return 0;
    }
    
    

    信息

    ID
    2946
    时间
    1000ms
    内存
    125MiB
    难度
    5
    标签
    递交数
    6
    已通过
    3
    上传者