菜菜把李超线段树的模板写挂了,求调
查看原帖
菜菜把李超线段树的模板写挂了,求调
546830
XSean楼主2023/8/31 21:40
#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define pre(i, a, b) for(int i = (a); i >= (b); i--)
#define Ede(i, u) for(int i = h[u]; i; i = ne[i])
#define go(i, a) for(auto i : a)

//#define int long long
#define uint unsigned int
#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>
#define PIL pair<int, LL>
#define PLI pair<LL, int>
#define PLL pair<LL, LL>
#define mkp make_pair
#define eb emplace_back
#define opb pop_back
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sf scanf
#define prf printf
#define el putchar('\n')
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define mmc(arr1, arr2) memcpy(arr1, arr2, sizeof(arr2))
#define debug(x) cerr << #x << ": " << x << endl
#define Db(x) cerr << x << ": " << endl
const int inf = 0x3f3f3f3f;

template <typename T> inline void rd(T &x){
	x = 0; bool f = true; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = false; ch = getchar();}
	while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
	if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}
#define ls(x) x << 1
#define rs(x) x << 1 | 1
using namespace std;
//bool stt;
const int N = 5e5 + 10, M = 1e5 + 10;
int n;
int tag[N << 2];
double k[M], b[M];
double calc(int i, int pos){
	return k[i] * (pos - 1) + b[i]; 
} //原点为1,所以x-1 
void modify(int p, int l, int r, int pos){
	if(l == r){
		if(calc(tag[p], l) < calc(pos, l)) tag[p] = pos;
		return;
	}
	if(!tag[p]){
		tag[p] = pos;
		return;
	}else{
		int mid = (l + r) >> 1;
		double y1 = calc(tag[p], mid), y2 = calc(pos, mid);
		if(k[tag[p]] < k[pos]){
			if(y1 <= y2){ modify(ls(p), l, mid, tag[p]); tag[p] = pos;}
			else modify(rs(p), mid + 1, r, pos);
		}else if(k[tag[p]] > k[pos]){
			if(y1 <= y2){ modify(rs(p), mid + 1, r, tag[p]); tag[p] = pos;}
			else modify(ls(p), l, mid, pos);
		}else if(b[tag[p]] < b[pos]) tag[p] = pos;
	} 
}
double query(int p, int l, int r, int pos){
	if(l == r) return calc(tag[p], pos);
	double res = calc(tag[p], pos);
	int mid = (l + r) >> 1;
	if(pos <= mid) res = max(res, query(ls(p), l, mid, pos));
	else res = max(res, query(rs(p), mid + 1, r, pos));
	return res;
}
//bool edd;
int main(){
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
//	cerr << (&edd - &stt) / 1024.0 / 1024.0 << endl;
	rd(n);
	int tot = 0;
	rep(i, 1, n){
		char ins[15]; sf("%s", ins);
		if(ins[0] == 'Q'){
			int t; rd(t); 
			if(!tot) puts("0");
			else prf("%d\n", (int)query(1, 1, N, t) / 100);
		}else{
			++tot;
			sf("%llf%llf", &b[tot], &k[tot]);
			modify(1, 1, N, tot);
		}
	}
	return 0;
}
2023/8/31 21:40
加载中...