李超线段树萌新0pts求救
查看原帖
李超线段树萌新0pts求救
250640
stueam楼主2022/8/4 18:14
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct seg
{
    double k,b;
}a[N * 4];
int n,m = 500010;
int tree[N * 2];
double cal(seg t,int x)
{
    return t.k * x + t.b;
}
 void modify(int u,int l,int r,int x)
{
    if(cal(a[x],l) > cal(a[tree[u]],l) && cal(a[x],r) > cal(a[tree[u]],r)) { tree[u] = x; return; }
    if(cal(a[x],l) <= cal(a[tree[u]],l) && cal(a[x],r) <= cal(a[tree[u]],r)) return; 
    int mid = l + r >>1;
    if(a[tree[u]].k < a[x].k)
    {
        if(cal(a[x],mid) > cal(a[tree[u]],mid)) modify(u << 1,l,mid,tree[u]),tree[u] = x; 
        else modify(u << 1 | 1,mid + 1,r,x);

    }
    else
    {
        if(cal(a[x],mid) > cal(a[tree[u]],mid)) modify(u << 1 | 1,mid + 1,r,tree[u]),tree[u] = x;
        else modify(u << 1,l,mid,x);
    }
}
double query(int u,int l,int r,int x)
{
    if(l == r) return cal(a[tree[u]],x);
    int mid = l + r >> 1;
    if(x <= mid) return max(cal(a[tree[u]],x),query(u << 1,l,mid,x));
    else return max(cal(a[tree[u]],x),query(u << 1 | 1,mid + 1,r,x));
}

int main()
{
	int T,x;
    cin >> T;
    char s[10];
    while(T--)
    {
        scanf("%s",s);
        if(s[0]=='P')
        {
            n++;
            cin >> a[n].b >>a[n].k;
            modify(1,1,50010,n);
        }
        else
        {
            cin >> x;
            printf("%d\n",(int)(query(1,1,50010,x)/100)) ;
        }
    }
    return 0;
}
2022/8/4 18:14
加载中...