scau 1144 数星星 bit + 扫描线的思想

这题如果用二维树状数组，则会直接爆内存。

那么可以运用扫描线的思路。

就是，它同时被x和y限制了，那么可以在查询的时候，确保x先满足了，（把x按小到大排序）

然后就相当于是关于y的一个一维bit了，

注意同一个点它询问两次。

8
2 2
1 1
1 2
1 3
1 4
1 5
2 1
0 1
2
1 1

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e6 + 22;
struct node {
    int x, y, id;
    bool operator < (const struct node & rhs) const {
        if (x != rhs.x) return x < rhs.x;
        else return y < rhs.y;
    }
}a[maxn];
int c[maxn];
int lowbit(int x) {
    return x & (-x);
}
void upDate(int pos, int val) {
    while (pos <= maxn - 2) {
        c[pos] += val;
        pos += lowbit(pos);
    }
}
int sum(int pos) {
    int ans = 0;
    while (pos > 0) {
        ans += c[pos];
        pos -= lowbit(pos);
    }
    return ans;
}
int ser[maxn];
int ans[maxn];
int n;
vector<int>want;
void work() {
    memset(c, 0, sizeof c);
//    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].x++;
        a[i].y++;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n);
//    for (int i = 1; i <= n; ++i) {
//        printf("%d %d %d
", a[i].x, a[i].y, a[i].id);
//    }
    int m;
    scanf("%d", &m);
    memset(ser, 0, sizeof ser);
    for (int i = 1; i <= m; ++i) {
        int id;
        scanf("%d", &id);
        ser[id] = i;
        want.push_back(id);
    }
    for (int i = 1; i <= n; ++i) {
        if (ser[a[i].id]) {
            ans[a[i].id] = sum(a[i].y);
        }
        upDate(a[i].y, 1);
    }
    for (int i = 0; i < want.size(); ++i) {
        printf("%d
", ans[want[i]]);
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    while (scanf("%d", &n) != EOF) work();
    return 0;
}

View Code

scau 1144 数星星 bit + 扫描线的思想

相关推荐