萌新刚学 OI, 求助离散化
查看原帖
萌新刚学 OI, 求助离散化
189351
wheneveright楼主2021/8/17 21:00

RT

这个代码应该是离散化锅了,但是我不太清楚为什么会出错

# include <bits/stdc++.h>
using namespace std;

const int maxn = 500005;

struct reader {
    template <typename Type>
    reader & operator >> (Type & ret) {
        int f = 1; ret = 0; char ch = getchar ();
        for (;!isdigit (ch); ch = getchar ()) if (ch == '-') f = -f;
        for (; isdigit (ch); ch = getchar ()) ret = (ret * 10) + ch - '0';
        ret *= f; return *this;
    }
} fin;

int n, m, totx, toty, tot;
int x[maxn], y[maxn], now;
int a[maxn], b[maxn], c[maxn], d[maxn];
set < int > Sx, Sy;
map < int, int > mpx, mpy;
struct WER {
	int d, u, pos, bel;
	bool operator < (WER p) const {
		return pos < p.pos;
	}
} A[maxn << 1];
pair < int, int > pot[maxn];
int T[maxn << 1];
void update (int id) {
	for (; id <= totx; id += id & -id) T[id]++;
	return ;
}
int query (int id) {
	int ret = 0;
	for (; id >= 1; id -= id & -id) ret += T[id];
	return ret;
}
int res[maxn];

int main () {
	fin >> n >> m;
	for (int i = 1; i <= n; i++) {
		fin >> x[i] >> y[i];
		Sx.insert (x[i]);
		Sy.insert (y[i]);
	}
	for (int i = 1; i <= m; i++) {
		fin >> a[i] >> b[i] >> c[i] >> d[i];
		Sx.insert (--a[i]); Sx.insert (c[i]);
		Sy.insert (--b[i]); Sy.insert (d[i]);
	}
	for (set < int > :: iterator i = Sx.begin (); i != Sx.end (); i++) mpx[*i] = ++totx;
	for (set < int > :: iterator i = Sy.begin (); i != Sy.end (); i++) mpy[*i] = ++toty;
	for (int i = 1; i <= n; i++) {
		x[i] = mpx[x[i]]; y[i] = mpy[y[i]];
		pot[i] = make_pair (x[i], y[i]);
	}	sort (pot + 1, pot + 1 + n);
	for (int i = 1; i <= m; i++) {
		a[i] = mpx[a[i]]; b[i] = mpy[b[i]];
		c[i] = mpx[c[i]]; d[i] = mpy[d[i]];
		A[++tot] = (WER) { b[i], d[i], a[i], -i };
		A[++tot] = (WER) { b[i], d[i], c[i],  i };
	}
	sort (A + 1, A + 1 + tot);
	for (int i = 1; i <= tot; i++) {
		while (now + 1 <= n && pot[now + 1].first <= A[i].pos) update (pot[++now].second);
		int val = 1; if (A[i].bel < 0) val = -1, A[i].bel = - A[i].bel;
		res[A[i].bel] += val * (query (A[i].u) - query (A[i].d));
	}
	for (int i = 1; i <= m; i++) printf ("%d\n", res[i]);
	return 0;
}

input

10 6
4 5
6 8
4 2
4 8
0 0
6 2
4 7
0 1
3 1
1 8
3 5 4 9
0 2 1 6
1 0 1 0
1 2 4 4
0 1 5 9
3 7 3 10

stdoutput

3
0
0
1
7
0

myoutput

2
0
0
1
5
0

有空闲的大佬帮蒟蒻看看吗

2021/8/17 21:00
加载中...