P5482 不等式组求条
  • 板块灌水区
  • 楼主Guoguo2013
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/24 17:02
  • 上次更新2025/1/24 20:48:45
查看原帖
P5482 不等式组求条
1070982
Guoguo2013楼主2025/1/24 17:02

题目 一直 0 pts,测了第一组数据的前一百行,没有问题。

#include<bits/stdc++.h>
#define int long long
#define PII pair< int, int >

using namespace std;

const int N = 2e5 + 5, mod = 998244353;
int n, tot, rt[5], a, b, c, cnt;
struct bds{
	int fuhao, val;
} bdshi[N];
struct node{
	int val, key, siz;
	int lson, rson;
} t[N];
struct {
	int New(int x){
		t[++tot].val = x;
		t[tot].key = 1ll * rand() * rand() % mod;
		t[tot].siz = 1;
		t[tot].lson = t[tot].rson = 0;
		return tot;
	}
	void update(int x){
		if (x == 0) return ;
		t[x].siz = t[t[x].lson].siz + t[t[x].rson].siz + 1;
	}
	void split(int now, int &a, int &b, int k){
		if (now == 0){
			a = b = 0;
			return ;
		}
		if (t[now].val <= k){
			a = now;
			split(t[now].rson, t[a].rson, b, k);
		}
		else {
			b = now;
			split(t[now].lson, a, t[b].lson, k);
		}
		update(now);
	}
	void merge(int &now, int a, int b){
		if (a == 0 || b == 0){
			now = a + b;
			return ;
		}
		if (t[a].key >= t[b].key){
			now = a;
			merge(t[now].rson, t[a].rson, b);
		}
		else {
			now = b;
			merge(t[now].lson, a, t[b].lson);
		}
		update(now);
	}
	int query(int rt, int k){
		int now = rt;
		while(true){
			if (k <= t[t[now].lson].siz) now = t[now].lson;
			else if (k > t[t[now].lson].siz + 1){
				k -= t[t[now].lson].siz + 1;
				now = t[now].rson;
			}
			else return t[now].val;
		}
	}
} FHQ_treap[5];

template< typename T >inline void read(T &x){bool f=1;x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x=(f?x:-x);return;}
template< typename T, typename ... L > void read(T &a , L && ... b) { read(a); read(b ...); }
int ksm(int a, int b, int p){int ans = 1;while(b){if(b & 1)ans =(ans*a)%p;b >>= 1;a = (a*a) % p;}return ans;}
signed main(){
//	freopen("a.in", "r", stdin);
//	freopen("a.out","w",stdout);
	srand(time(0));
	read(n);
	while (n--){
		string op;
		cin >> op;
		if (op == "Add"){
			int x, y, z;
			read(x, y, z);
			z -= y;
			if (x == 0){
				if (y == z){
					bdshi[++cnt].val = -200000001;
					bdshi[cnt].fuhao = 2;
				}
				else {
					bdshi[++cnt].val = 200000001;
					bdshi[cnt].fuhao = 2;
				}
				continue;
			}
			else if (x > 0){
				bdshi[++cnt].val = ceil((double)z / x) - 1;
				bdshi[cnt].fuhao = 2;
//				printf("%lld\n", bdshi[cnt].val);
//				cout << "---------------2---------------" << '\n';
			}
			else {
				bdshi[++cnt].val = floor((double)z / x) + 1;
				bdshi[cnt].fuhao = 1;
//				printf("%lld\n", bdshi[cnt].val);
//				cout << "---------------1---------------" << '\n';
			}
			int now = FHQ_treap[bdshi[cnt].fuhao].New(bdshi[cnt].val);
			FHQ_treap[bdshi[cnt].fuhao].split(rt[bdshi[cnt].fuhao], a, b, bdshi[cnt].val);
			FHQ_treap[bdshi[cnt].fuhao].merge(a, a, now);
			FHQ_treap[bdshi[cnt].fuhao].merge(rt[bdshi[cnt].fuhao], a, b);
		}
		if (op == "Del"){
			int i;
			read(i);
			if (bdshi[i].val == 200000001 && bdshi[i].fuhao == 2) continue;
			FHQ_treap[bdshi[i].fuhao].split(rt[bdshi[i].fuhao], a, b, bdshi[i].val);
			FHQ_treap[bdshi[i].fuhao].split(a, a, c, bdshi[i].val - 1);
			FHQ_treap[bdshi[i].fuhao].merge(c, t[c].lson, t[c].rson);
			FHQ_treap[bdshi[i].fuhao].merge(rt[bdshi[i].fuhao], a, c);
			FHQ_treap[bdshi[i].fuhao].merge(rt[bdshi[i].fuhao], rt[bdshi[i].fuhao], b);
			bdshi[i].val = 200000001;
			bdshi[i].fuhao = 2;
//			printf("%lld %lld\n", i, bdshi[i].val);
		}
		if (op == "Query"){
			int k;
			read(k);
			int dan = 0;
			FHQ_treap[1].split(rt[1], a, b, k);
			dan += t[b].siz;
//			printf("%lld %lld\n", t[b].siz, t[b].val);
			FHQ_treap[1].merge(rt[1], a, b);
			FHQ_treap[2].split(rt[2], a, b, k - 1);
			dan += t[a].siz;
			FHQ_treap[2].merge(rt[2], a, b);
			printf("%lld\n", dan);
		}
	}
	return 0;
}
2025/1/24 17:02
加载中...