文件详细信息

下载本文件

本文件的大小为 3138 字节。

#include<algorithm>
#include<cstdio>
#include<set>
namespace IO{
	const int ARR_SIZE=1<<24;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a<0)pc('-'),a=-a;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
typedef long long ll;
const int maxn=300000;
int n,w;
ll mygcd(ll a,ll b){
	while(b){
		a%=b;
		a^=b^=a^=b;
	}
	return a;
}
struct Frac{
	ll a,b;
	Frac(const ll a=0,const ll b=1):a(a),b(b){}
	void reduce(){
		ll tmp=mygcd(a,b);
		a/=tmp,b/=tmp;
	}
	void print(){
		write(a),pc('/'),write(b);
	}
};
bool operator<=(const Frac x,const Frac y){
	return x.a*y.b<=y.a*x.b;
}
bool operator<(const Frac x,const Frac y){
	return x.a*y.b<y.a*x.b;
}
Frac operator*(const Frac x,const Frac y){
	Frac ans(x.a*y.a,x.b*y.b);
	ans.reduce();
	return ans;
}
Frac operator+(const Frac x,const Frac y){
	ll g=x.b/mygcd(x.b,y.b)*y.b;
	Frac ans(g/x.b*x.a+g/y.b*y.a,g);
	ans.reduce();
	return ans;
}
struct Seg{
	int a,b;
	Frac end;
}s[maxn+1];
Frac getx(const int i,const int j){
	if(!i||!j||s[i].b==s[j].b)return Frac{1,1};
	if((s[i].a<s[j].a)==(s[i].b<s[j].b))return Frac{1,0};
	Frac ans(s[j].a-s[i].a,(s[i].b-s[i].a)-(s[j].b-s[j].a));
	ans.reduce();
	return ans;
}
std::set<std::pair<int,int>>set;
int lg2[maxn+1],dep[maxn+1],fa[maxn+1][19];
int lca(int u,int v){
	if(dep[u]<dep[v])u^=v^=u^=v;
	while(dep[u]>dep[v])u=fa[u][lg2[dep[u]-dep[v]]];
	if(u==v)return u;
	for(int i=lg2[dep[u]];i>=0;i--)
		if(fa[u][i]!=fa[v][i])
			u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int main(){
	read(n),read(w);
	for(int i=2;i<=n;i++)lg2[i]=lg2[i-1]+((i&(i-1))==0);
	set.insert({-1,0});
	set.insert({10000001,0});
	for(int i=1,c,u,v,_lca;i<=n;i++){
		read(s[i].a),read(s[i].b),read(c);
		s[i].end=Frac(1,1);
		u=(--set.lower_bound({s[i].a,i}))->second,v=set.upper_bound({s[i].a,i})->second;
		_lca=lca(u,v);
		for(int j=18;j>=0;j--){
			if(dep[fa[u][j]]>dep[_lca]&&s[fa[u][j]].end<getx(fa[u][j],i))u=fa[fa[u][j]][0];
			if(dep[fa[v][j]]>dep[_lca]&&s[fa[v][j]].end<getx(fa[v][j],i))v=fa[fa[v][j]][0];
		}
		if(u&&s[u].end<getx(u,i))u=fa[u][0];
		if(v&&s[v].end<getx(v,i))v=fa[v][0];
		if(dep[u]<dep[v])u^=v^=u^=v;
		Frac x=getx(u,i);
		Frac y=Frac(s[i].a,1)+x*Frac(s[i].b-s[i].a,1);
		s[i].end=x;
		x=x*Frac(w,1),x.reduce();
		pc('('),x.print(),pc(','),y.print(),pc(')'),pc('\n');
		if(c==1){
			set.insert({s[i].a,i});
			dep[i]=dep[u]+1;
			fa[i][0]=u;
			for(int j=1;j<19;j++)fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	return 0;
}