李超树入门略解

李超树入门略解

今天我们讲讲李超树又称LCT(x)，它主要支持2种操作：

• 在平面上插入一条直线
• 求一个横坐标上最高的直线

然后我们可以标记永久化，单点查询就非常简单了，而我们主要讲讲插入直线。对于线段树上一个点，你需要保留在这个区间的中点最高的直线，而插入时，新直线和旧直线进行比较：

• 当新直线在左右端点的值都比旧直线大，那么直接用新直线替代旧直线

• 当新直线在左右端点的值都比旧直线小，那么直接结束，不做任何操作

• 当新直线在区间中点的值比旧直线大，那么替换旧直线，但是要将旧直线插入左区间或右区间：

  • 当新直线斜率更小，那么将旧直线插入到右区间中
  • 当新直线斜率更大，那么将旧直线插入到左区间中

• 当新直线在区间中点的值比旧直线小，那么将新直线插入左区间或右区间：

  • 当新直线斜率更小，将新直线插入到左区间中
  • 当新直线斜率更大，将新直线插入到右区间中

显然，这样插入的复杂度是 O ( l o g n ) O(logn) O(logn)的。

一道板子题

其实就是刚刚的操作。

#include<bits/stdc++.h>
using namespace std;
#define N 50000
//#define eps 1e-10
inline int read(){int a=0;char c=getchar();while(c>'9'||c<'0')c=getchar();while('0'<=c&&c<='9'){a=a*10+c-48;c=getchar();}return a;     
}
#define MN 100005
struct line{double k,b;
}w[MN];
int use[MN<<2],n;
double f(int id,int pos){return w[id].k*pos+w[id].b;
}
#define Ls (x<<1)
#define Rs (x<<1|1)
#define mid (l+r>>1)
void Ins(int x,int l,int r,int id){int v=use[x];if(f(id,l)>f(v,l)&&f(id,r)>f(v,r)){use[x]=id;//	cout<<"INS: "<<l<<" "<<r<<endl;return;}if(f(id,l)<=f(v,l)&&f(id,r)<=f(v,r))return;if(f(id,mid)>f(v,mid)){if(w[id].k>w[v].k) Ins(Ls,l,mid,v);else Ins(Rs,mid+1,r,v);use[x]=id;}else{if(w[id].k>w[v].k)Ins(Rs,mid+1,r,id);else Ins(Ls,l,mid,id);}}
int query(int x,int l,int r,int loc){int v=use[x];if(l==r)return v;int res=(loc<=mid)?query(Ls,l,mid,loc):query(Rs,mid+1,r,loc);if(f(v,loc)>f(res,loc))return v;return res;
}
char ch[11];
int main(){
//	n=read();scanf("%d",&n);for(int i=1;i<=n;++i){
//		char c=getchar();
//		while(c!='Q'&&c!='P')c=getchar();scanf("%s",ch);if(ch[0]=='Q'){
//			int k=read();int k;scanf("%d",&k);//	printf("res: %.3lfn",f(query(1,1,N,k),k));printf("%dn",(int)(f(query(1,1,N,k),k)/100.0));}else {//	x1=(read()+ans-1)%Mod+1;y1=(read()+ans-1)%Mod+1;//	x2=(read()+ans-1)%Mod+1;y2=(read()+ans-1)%Mod+1;scanf("%lf%lf",&w[i].b,&w[i].k);w[i].b-=w[i].k;Ins(1,1,N,i);//w[i].k=1.0*(y2-y1)/(1.0*(x2-x1));}}return 0;
}

又一道板子题

这题变成了线段，怎么办？

暴力找到线段所在的log个区间，再暴力插入，复杂度 O ( l o g 2 n ) O(log^2n) O(log2n)。另外需要特判l=r的情况

#include<bits/stdc++.h>
using namespace std;
#define N 39989
#define INF 1000000000
#define y1 HHAKIOI
//#define eps 1e-10
inline int read(){int a=0;char c=getchar();while(c>'9'||c<'0')c=getchar();while('0'<=c&&c<='9'){a=a*10+c-48;c=getchar();}return a;     
}
#define MN 100005
struct line{double k,b;
}w[MN];
int use[MN<<2],n,cnt;
pair<int,int>MAX[MN];
double f(int id,int pos){return w[id].k*pos+w[id].b;
}
#define Ls (x<<1)
#define Rs (x<<1|1)
#define mid (l+r>>1)
void Ins(int x,int l,int r,int id){int v=use[x];if(f(id,l)>f(v,l)&&f(id,r)>f(v,r)){use[x]=id;//	cout<<"INS: "<<l<<" "<<r<<endl;return;}if(f(id,l)<=f(v,l)&&f(id,r)<=f(v,r))return;if(f(id,mid)>f(v,mid)){if(w[id].k>w[v].k) Ins(Ls,l,mid,v);else Ins(Rs,mid+1,r,v);use[x]=id;}else{if(w[id].k>w[v].k)Ins(Rs,mid+1,r,id);else Ins(Ls,l,mid,id);}}
void upd(int x,int l,int r,int b,int e,int id){if(b<=l&&r<=e) {Ins(x,l,r,id);return;}if(mid>=b) upd(Ls,l,mid,b,e,id);if(mid<e) upd(Rs,mid+1,r,b,e,id);
}
int query(int x,int l,int r,int loc){int v=use[x];if(l==r)return v;int res=(loc<=mid)?query(Ls,l,mid,loc):query(Rs,mid+1,r,loc);if(f(v,loc)>f(res,loc))return v;return res;
}
char ch[11];
int main(){scanf("%d",&n);int ans=0;for(int i=1;i<=n;++i){int op,k,x1,x2,y1,y2;scanf("%d",&op);if(!op){scanf("%d",&k);k=(k+ans-1)%N+1;//	printf("res: %.3lfn",f(query(1,1,N,k),k));ans=query(1,1,50000,k);if(f(ans,k)<MAX[k].first||(f(ans,k)==MAX[k].first&&ans>MAX[k].second))ans=MAX[k].second;printf("%dn",ans);}else {x1=(read()+ans-1)%N+1;y1=(read()+ans-1)%INF+1;x2=(read()+ans-1)%N+1;y2=(read()+ans-1)%INF+1;if(x1>x2)swap(x1,x2),swap(y1,y2);cnt++;if(x1==x2){MAX[x1]=max(MAX[x1],make_pair(max(y1,y2),cnt));continue;}//			scanf("%lf%lf",&w[i].b,&w[i].k);w[cnt].k=1.0*(y2-y1)/(1.0*(x2-x1));w[cnt].b=y1-w[cnt].k*x1;upd(1,1,50000,x1,x2,cnt);}}return 0;
}

最后

李超树有时作用蛮大的，而且常数较小，有时候还有一些骚操作(比如区间查询之类的），以后再讲。图片可能以后会加吧，这样更清晰写咕咕咕