树状数组 60pts 求调
查看原帖
树状数组 60pts 求调
675466
zzx0102楼主2023/4/21 21:05

WA 了

#include<bits/stdc++.h>
using namespace std;
#define I inline
#define W while
#define gc getchar
#define pc putchar
namespace SlowIO {
	I int read() {
		int x = 0, f = 1; char ch = gc();
		W(ch < '0' || ch > '9') {if(ch == '-') f = -f; ch = gc();}
		W(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
		return x * f;
	}
	I void Read(int &x) {x = read();}
	I void Read(int &x, int &y) {Read(x), Read(y);}
	I void write(int x) {
		if(x < 0) pc('-'), x = -x;
		if(x > 9) write(x / 10);
		pc(x % 10 + '0');
	}
	I void writeln(int x) {write(x); pc('\n');}
	I void Write(int x) {write(x); pc(' ');}
} using namespace SlowIO;
const int N = 20000010; int tr[N];
I int lbt(int x) {return x & (-x);}
I void add(int x, int k) {for(; x < N; x += lbt(x)) tr[x] += k;}
I int query(int x) {int sum = 0; for(; x; x -= lbt(x)) sum += tr[x]; return sum;}
int main() {
	int q; Read(q);
	W(q--) {
		int op, x; Read(op, x);
		if(op == 1) add(x + 10000000, 1);
		if(op == 2) add(x + 10000000, -1);
		if(op == 3) writeln(query(x + 10000000 - 1) + 1);
		if(op == 4) {
			int l = 1, r = 20000000, ans = 1;
			W(l <= r) {
				int mid = l + r >> 1;
				if(query(mid) >= x) ans = mid, r = mid - 1;
				else l = mid + 1;
			}
			writeln(ans - 10000000);
		}
		if(op == 5) {
			x += 10000000;
			int l = 0, r = x - 1, ans = 1; int k = query(x);
			W(l <= r) {
				int mid = l + r >> 1;
//				cout << l << ' ' << r << ' ' << mid << ' ' << query(mid) << endl; 

				if(k == query(mid)) r = mid - 1;
				else l = mid + 1, ans = mid;
			}
			writeln(ans - 10000000 + 1);
		}
		if(op == 6) {
			x += 10000000;
			int l = x + 1, r = 20000000, ans = 1; int k = query(x);
			W(l <= r) {
				int mid = l + r >> 1;
				if(k == query(mid)) ans = mid, l = mid + 1;
				else r = mid - 1;
			}
			writeln(ans - 10000000 + 1);
		}
	}
	return 0;
}
/*
5
1 114514
1 114514
3 1919810
2 114514
3 1919810

*/
2023/4/21 21:05
加载中...