为什么我的代码,在 calc 计算当前函数值的时候将 k−1 就全 WA,但是改成一开始将 line.b−line.k 就过了啊。
#include<bits/stdc++.h>
#define ll long long
#define LF putchar('\n')
#define SP putchar(' ')
#define pii pair<int,int>
template <typename T>
void read(T& x) {
x = 0;
char ch = getchar();
long long f = 1;
while (!isdigit(ch)) {
if (ch == '-')
f *= -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
x *= f;
}
template <typename T, typename... Args>
void read(T& first, Args&... args) {
read(first);
read(args...);
}
template <typename T>
void write(T arg) {
T x = arg;
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
template <typename T, typename... Ts>
void write(T arg, Ts... args) {
write(arg);
if (sizeof...(args) != 0) {
putchar(' ');
write(args...);
}
}
const int N = 5e4 + 10;
const int M = 1e5+10;
const int INF = 0x3f3f3f3f;
using namespace std;
const double eps = 1e-8;
#define int long long
int n;
struct node {
double k, b;
} line[M];
int tot;
double calc(int id, double pos) {
if(id == -1) return -1e9;
if (!id) return -1e9;
return line[id].b + (line[id].k)*pos;
}
int tr[N<<3];
//void update(int rt, int l, int r, int id) {
//
// int mid = l + r >> 1;
// if (calc(id, mid) > calc(tr[rt], mid) || (fabs(calc(id, mid) - calc(tr[rt], mid)) < eps && id < tr[rt])) swap(tr[rt], id);
// if (l == r) return;
// update(rt << 1, l, mid, id);
// update(rt << 1 | 1, mid + 1, r, id);
//}
void update(int rt, int l, int r, int L, int R, int id) {
int mid = l + r >> 1;
// cout<<1;
if (L <= l && R >= r) {
if ((calc(id, mid) > calc(tr[rt], mid)) || (fabs(calc(id, mid) - calc(tr[rt], mid)) < eps && id < tr[rt]))
swap(id, tr[rt]);
if (l == r) return;
if(line[id].k<line[tr[rt]].k) update(rt<<1,l,mid,L,R,id);
else update(rt<<1|1,mid+1,r,L,R,id);
return;
}
if(L<=mid) update(rt<<1,l,mid,L,R,id);
if(R>mid) update(rt<<1|1,mid+1,r,L,R,id);
}
int ans;
double query(int rt, int l, int r, int pos) {
// write(1);
// cout<<l<<" "<<r<<endl;
if(l == r){
// cout<<rt<<endl;
return calc(tr[rt],pos);
}
int mid = l+r>>1;
if(pos<=mid) return max(calc(tr[rt],pos),query(rt<<1,l,mid,pos));
else return max(calc(tr[rt],pos),query(rt<<1|1,mid+1,r,pos));
}
signed main() {
read(n);
for (int i = 1; i <= n; i++) {
char op[10];
scanf("%s", op);
if (op[0] == 'P') {
++tot;
scanf("%lf%lf",&line[tot].b,&line[tot].k);
line[tot].b -= line[tot].k;
update(1,1,N,1,N,tot);
} else {
int t;
read(t);
ans = query(1,1,N,t)/100;
write(max(0ll,ans));
LF;
// ans = -1;
// query(1,1,N,t);
// if(ans == -1) write(0);
// else{
// int res = calc(ans,t)/100;
// write(res);
// }
// LF;
}
}
return 0;
}