[数据结构与算法]智乃的直线（李超线段树模板题）

智乃的直线

好久不写题解了，分享下最近学习的数据结构

李超线段树，个人感觉跟普通线段树区别不大，只是维护的信息是线段，重点是每个节点维护的线段为：1.在中点处该线段取值最大。2.线段的定义域大于区间的范围。

题目链接

https://ac.nowcoder.com/acm/contest/19917/A

代码

// Problem: ????μ??±??
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/19917/A
// Memory Limit: 1048576 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int>PII;
int max(int a,int b)
{
	if(a>=b) return a;
	else return b;
}
int min(int a,int b)
{
	if(a>=b) return b;
	else return a;
}
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
int qmi(int a,int b,int c)    
{
	int res=1%c;
	while(b)
	{
		if(b&1) res=res*a%c;
		a=a*a%c;
		b>>=1;
	}
	return res;
}
int gcd(int a,int b)   
{
	return b?gcd(b,a%b):a;
}
const int N=1e6+10;
const int eps=0;
struct node{
	int l;
	int r;
	int jud1,jud2;
	int k1,b1;   //max
	int k2,b2;    //min
}tr[N*4];
int cal(int k1,int b1,int x)
{
	return k1*x+b1;
}
int get_maxst(node a,node b)
{
	
	 return (b.b1-a.b1)/(a.k1-b.k1);
}
int get_minst(node a,node b)
{
	
   (b.b2-a.b2)/(a.k2-b.k2);
}
void build(int u,int l,int r)
{
	tr[u]={l,r,0,0,0,0,0,0};
	if(l!=r)
	{
		int  mid=l+r>>1;
		build(u*2,l,mid);
		build(u*2+1,mid+1,r);
	}
}
void modify_max(int u,int l,int r,int k,int b)
{
	if(tr[u].l>=l && tr[u].r<=r)
	{
		if(!tr[u].jud1)
		{
			tr[u].jud1=1;
			tr[u].k1=k;
			tr[u].b1=b;
		}
		else 
		{
			int l1=tr[u].l,r1=tr[u].r;
			int old1=cal(tr[u].k1,tr[u].b1,l1),old2=cal(tr[u].k1,tr[u].b1,r1);
			int new1=cal(k,b,l1),new2=cal(k,b,r1);
			if(new1-old1>eps && new2-old2>eps)
			{
				tr[u].k1=k;
				tr[u].b1=b;
				return ;
			}
			else  if(new1-old1>eps || new2-old2>eps)
			{
				int mid=tr[u].l+tr[u].r>>1;
				node tmp;
				if(cal(k,b,mid)-cal(tr[u].k1,tr[u].b1,mid)>eps)
				{
					tmp.k1=tr[u].k1;
					tmp.b1=tr[u].b1;
					tr[u].k1=k;
					tr[u].b1=b;
					k=tmp.k1;
					b=tmp.b1;
				}
		        if(get_maxst(tmp,tr[u])-mid<eps) modify_max(u*2,l,r,k,b);
		        else modify_max(u*2+1,l,r,k,b);
			}
			else return ;
		}
	}
	else
	{
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify_max(u*2,l,r,k,b);
		if(r>mid) modify_max(u*2+1,l,r,k,b);
	}
}
void modify_min(int u,int l,int r,int k,int b)
{
	if(tr[u].l>=l && tr[u].r<=r)
	{
		if(!tr[u].jud2)
		{
			tr[u].jud2=1;
			tr[u].k2=k;
			tr[u].b2=b;
		}
		else 
		{
			int l1=tr[u].l,r1=tr[u].r;
			int old1=cal(tr[u].k2,tr[u].b2,l1),old2=cal(tr[u].k2,tr[u].b2,r1);
			int new1=cal(k,b,l1),new2=cal(k,b,r1);
			if(new1-old1<eps && new2-old2<eps)
			{
				tr[u].k2=k;
				tr[u].b2=b;
				return ;
			}
			else if(new1-old1<eps || new2-old2<eps)
			{
				int mid=tr[u].l+tr[u].r>>1;
				node tmp;
				if(cal(k,b,mid)-cal(tr[u].k1,tr[u].b1,mid)<eps)
				{
					tmp.k2=tr[u].k2;
					tmp.b2=tr[u].b2;
					tr[u].k2=k;
					tr[u].b2=b;
					k=tmp.k2;
					b=tmp.b2;
				}
		        if(get_minst(tmp,tr[u])-mid<eps) modify_min(u*2,l,r,k,b);
		        else modify_min(u*2+1,l,r,k,b);
			}
			else return ;
		}
	}
	else
	{
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify_min(u*2,l,r,k,b);
		if(r>mid) modify_min(u*2+1,l,r,k,b);
	}
}
int query_max(int u,int x)
{
	if(tr[u].l==x && tr[u].r==x)
	{
		if(!tr[u].jud1)
		{
			return -INF;
		}
		else
		{
			return cal(tr[u].k1,tr[u].b1,x);
		}
	}
	else
	{
		if(tr[u].jud1==0) return -INF;
		int mid=tr[u].l+tr[u].r>>1;
		int ans=cal(tr[u].k1,tr[u].b1,x);
		if(x<=mid) ans=max(ans,query_max(u*2,x));
		else ans=max(ans,query_max(u*2+1,x));
		return ans; 
	}
}
int query_min(int u,int x)
{
	if(tr[u].l==x && tr[u].r==x)
	{
		if(!tr[u].jud2)
		{
			return INF;
		}
		else
		{
			return cal(tr[u].k2,tr[u].b2,x);
		}
	}
	else
	{
		if(tr[u].jud2==0) return INF;
		int mid=tr[u].l+tr[u].r>>1;
		int ans=cal(tr[u].k2,tr[u].b2,x);
		if(x<=mid) ans=min(ans,query_min(u*2,x));
		else ans=min(ans,query_min(u*2+1,x));
		return ans; 
	}
}
int n,m;
void solve()
{
     cin>>n>>m;
     build(1,1,n);
     while(m--)
     {
     	int op;
     	cin>>op;
     	if(op==1)
     	{
     		int x;
     		cin>>x;
     		cout<<query_max(1,x)<<' '<<query_min(1,x)<<'\n';
     	}
     	else
     	{
     		int k,b;
     		cin>>k>>b;
     		modify_max(1,1,n,k,b);
     		modify_min(1,1,n,k,b);
     	}
     }
}
signed main()
{
         ios_base::sync_with_stdio(false);
         cin.tie(0);
         int t;
         t=1;
         while(t--) 
        {
            solve();
        }
       return 0;
             
}