爆0求助qwq(FHQTREAP)
查看原帖
爆0求助qwq(FHQTREAP)
390770
S0CRiA楼主2021/12/10 22:28
//P5482
//ax + b > c
//a > 0   x > (c-b)/a    x >= floor((c-b)/a)+1
//a = 0   b > c
//a < 0   x < (c-b)/a    x <= ceil((c-b)/a)-1   -x >= -ceil((c-b)/a)+1
#include <bits/stdc++.h>
using namespace std;
#define ql(x) memset(x, 0, sizeof(x))

const int N = 1e5 + 10;
struct fhqtreap{
	int ch[N][2], val[N], pri[N], siz[N], tot, rt, x, y, z;
	fhqtreap(){ ql(ch), ql(val), ql(pri), ql(siz); tot=rt=x=y=z=0; }
	void update(int x){ siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1; }
	int newnode(int v){ siz[++tot] = 1, val[tot] = v, pri[tot] = rand(); return tot; }
	int merge(int x, int y){
		if(!x || !y) return x + y;
		if(pri[x] < pri[y]){ ch[x][1] = merge(ch[x][1], y); update(x); return x; }
		else{ ch[x][0] = merge(ch[x][0], y); update(y); return y; }
	}
	void split(int now, int k, int &x, int &y){
		if(!now){ x = y = 0; return; }
		if(val[now] <= k) x = now, split(ch[now][1], k, ch[now][1], y); 
		else y = now, split(ch[now][0], k, x, ch[now][0]);
		update(now);
	}
	int kth(int now, int k){
		while(true){
			if(k <= siz[ch[now][0]]) now = ch[now][0];
			else if(k == siz[ch[now][0]] + 1) return now;
			else k -= siz[ch[now][0]] + 1, now = ch[now][1];
		}
	}
	void insert(int k){
		split(rt, k, x, y);
		rt = merge(merge(x, newnode(k)), y);
	}
	void remove(int k){
		split(rt, k, x, z); split(x, k-1, x, y);
		y = merge(ch[y][0], ch[y][1]); rt = merge(merge(x, y), z);
	}
	int query(int k){
		split(rt, k, x, y); int ans = siz[x];
		rt = merge(x, y); return ans;
	}
} t1, t2;

int n, a, b, c, ans, cnt;
pair<int, int> t[N]; 
char op[10];

int main(){
	srand(time(NULL));
	scanf("%d", &n);
	while(n--){
		scanf("%s", op);
		if(op[0] == 'A'){
			scanf("%d%d%d", &a, &b, &c);
			if(a > 0){
				t1.insert((int)floor((c-b)*1.0/a) + 1);
				t[++cnt] = make_pair(1, (int)floor((c-b)*1.0/a) + 1);
//				printf("-----add t1 %d\n", (int)floor((c-b)*1.0/a) + 1);
			} else if(a == 0){
				if(b > c) ++ ans;
			} else if(a < 0){
				t2.insert(-(int)ceil((c-b)*1.0/a) + 1);
				t[++cnt] = make_pair(2, -(int)ceil((c-b)*1.0/a) + 1);
//				printf("-----add t2 %d\n", -(int)ceil((c-b)*1.0/a) + 1);
			}
		} else if(op[0] == 'D'){
			scanf("%d", &a);
			if(t[a].first == 1) t1.remove(t[a].second), t[a].first = 0;
			if(t[a].first == 2) t2.remove(t[a].second), t[a].first = 0;
		} else if(op[0] == 'Q'){
			scanf("%d", &a);
//			printf("-----query %d %d %d\n", ans, t1.query(a), t2.query(-a));
			printf("%d\n", ans + t1.query(a) + t2.query(-a));
		}
	}
	return 0;
}
2021/12/10 22:28
加载中...