悬赏 8 关注,板子 TLE #4 求卡
查看原帖
悬赏 8 关注,板子 TLE #4 求卡
540363
AKPC楼主2024/8/3 16:19
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=3e5+5;
int n,a[N],Dx[N],Dn[N],L[N],Q[N],cnt,rnk[N];
struct Sort_Node{
	int x,i;
	friend bool operator<(Sort_Node o,Sort_Node p){
		return o.x<p.x;
	}
}vp[N];
struct Dot{
	int l,r,tl,tr;
	bool tmp;
	vector<int>son,rank;
}dot[N<<1];
struct Stack_Int{
	int tip,Stk[N];
	void push(int x) {Stk[++tip]=x;}
	int top() {return Stk[tip];}
	void pop() {tip--;}
	int size() {return tip;}
	bool empty() {return !tip;}
	int get(int x) {return Stk[x];}
	void clear() {tip=0;}
}stk,s;
struct ST{
	int fax[N][22],fin[N][22];
	void build(){
		for (int i=1;i<=n;i++) fax[i][0]=fin[i][0]=a[i];
		for (int j=1;j<=21;j++)
			for (int i=1;i+(1<<j)-1<=n;i++){
				fax[i][j]=max(fax[i][j-1],fax[i+(1<<(j-1))][j-1]);
				fin[i][j]=min(fin[i][j-1],fin[i+(1<<(j-1))][j-1]);
			}
	}
	int qmx(int l,int r){
	    int k=log2(r-l+1);
	    return max(fax[l][k],fax[r-(1<<k)+1][k]);
	}
	int qmn(int l,int r){
	    int k=log2(r-l+1);
	    return min(fin[l][k],fin[r-(1<<k)+1][k]);
	}
}st;
struct sgm{
	#define mid ((l+r)>>1)
	#define lc (x<<1)
	#define rc (x<<1|1)
	int tag[N<<2],mn[N<<2];
	void push_up(int x){
		mn[x]=min(mn[lc],mn[rc]);
	}
	void push_down(int x){
		if (tag[x]){
			tag[lc]+=tag[x],tag[rc]+=tag[x];
			mn[lc]+=tag[x],mn[rc]+=tag[x];
			tag[x]=0;
		}
	}
	void update(int x,int l,int r,int ql,int qr,int d){
		if (ql>qr) return;
		if (ql<=l&&qr>=r) tag[x]+=d,mn[x]+=d;
		else{
			push_down(x);
			if (ql<=mid) update(lc,l,mid,ql,qr,d);
			if (qr>mid) update(rc,mid+1,r,ql,qr,d);
			push_up(x);
		}
	}
	int query(int x,int l,int r){
		if (l==r) return l;
		else{
			push_down(x);
			if (!mn[lc]) return query(lc,l,mid);
			else return query(rc,mid+1,r);
		}
	}
	#undef mid
	#undef lc
	#undef rc
}book;
void Init_D(){
	for (int i=n;i>=1;i--){
		while (!stk.empty()&&a[stk.top()]<a[i]) Dx[stk.top()]=i,stk.pop();
		stk.push(i);
	}
	stk.clear();
	for (int i=n;i>=1;i--){
		while (!stk.empty()&&a[stk.top()]>a[i]) Dn[stk.top()]=i,stk.pop();
		stk.push(i);
	}
}
void Init_L(){
	for (int i=1;i<=n;i++){
		int tx=Dx[i],tn=Dn[i],d=i-1;
		while (d>tx&&d>0){
			int ld=Dx[d]+1;
			book.update(1,1,n,ld,d,a[i]-a[d]);
			d=ld-1;
		}
		d=i-1;
		while (d>tn&&d>0){
			int ld=Dn[d]+1;
			book.update(1,1,n,ld,d,a[d]-a[i]);
			d=ld-1;
		}
		book.update(1,1,n,1,i-1,-1);
//		for (int j=1;j<=i;j++) cout<<Q[j]+book.tag[book.block[j]]<<' ';cout<<'\n'; 
		L[i]=book.query(1,1,i);
	}
//	for (int i=1;i<=n;i++) cout<<L[i]<<' ';
//	cout<<'\n';
}
void Build_Tree(){
	for (int _=1;_<=n;_++){
		Dot now={a[_],a[_],_,_,0,vector<int>{},vector<int>{}};
		int bs=0,bb=0;
		while (1){
//			cout<<now.l<<' '<<now.r<<' '<<s.size()<<' '<<"werh\n";
			if (s.empty()){
				if (!bs) dot[++cnt]=now;
				s.push(bb!=0?bb:cnt);
				break;
			}
			int x=s.top();
			if (!bs) dot[++cnt]=now;
			bs=1;
			Dot ths=dot[x];
			if (ths.r==now.l-1||ths.l==now.r+1){
				if (ths.tmp&&ths.rank[0]<ths.rank[ths.rank.size()-1]&&dot[ths.son[ths.rank.size()-1]].r<now.l){
					dot[x].l=min(dot[x].l,now.l),dot[x].r=max(dot[x].r,now.r);
					dot[x].tl=min(dot[x].tl,now.tl),dot[x].tr=max(dot[x].tr,now.tr);
					dot[x].son.push_back(cnt),dot[x].rank.push_back(dot[x].rank[dot[x].rank.size()-1]+1);
					s.pop(),now=ths,bb=x;
				}
				else if (ths.tmp&&ths.rank[0]>ths.rank[ths.rank.size()-1]&&dot[ths.son[ths.rank.size()-1]].r>now.l){
					dot[x].l=min(dot[x].l,now.l),dot[x].r=max(dot[x].r,now.r);
					dot[x].tl=min(dot[x].tl,now.tl),dot[x].tr=max(dot[x].tr,now.tr);
					dot[x].son.push_back(cnt),dot[x].rank.push_back(dot[x].rank[dot[x].rank.size()-1]+1);
					s.pop(),now=ths,bb=x;
				}
				else{
					dot[cnt+1]={min(ths.l,now.l),max(ths.r,now.r),min(ths.tl,now.tl),max(ths.tr,now.tr),1,vector<int>{x,cnt},vector<int>{}};
					if (dot[x].l<dot[cnt].l) dot[cnt+1].rank=vector<int>{1,2};
					else dot[cnt+1].rank=vector<int>{2,1};
					cnt++,s.pop(),now=dot[cnt],bb=cnt;
				}
			}
			else{
				bool sb=0;
				for (int i=s.size();i>=1;i--){
					Dot ths=dot[s.get(i)];
					if (st.qmx(min(ths.tl,now.tl),max(now.tr,ths.tr))-st.qmn(min(ths.tl,now.tl),max(now.tr,ths.tr))==max(now.tr,ths.tr)-min(ths.tl,now.tl)){
//						cout<<st.qmx(min(ths.tl,now.tl),max(now.tr,ths.tr))<<' '<<st.qmn(min(ths.tl,now.tl),max(now.tr,ths.tr))<<'\n';
						dot[cnt+1]={st.qmn(min(ths.tl,now.tl),max(now.tr,ths.tr)),st.qmx(min(ths.tl,now.tl),max(now.tr,ths.tr)),min(ths.tl,now.tl),max(now.tr,ths.tr),0,vector<int>{},vector<int>{}};
						for (int j=i;j<=s.size();j++) dot[cnt+1].son.push_back(s.get(j)),vp[j]={dot[s.get(j)].l,j};
						sort(vp+i,vp+s.size()+1);
						for (int j=i;j<=s.size();j++) rnk[vp[j].i]=j;
						for (int j=i;j<=s.size();j++) dot[cnt+1].rank.push_back(rnk[j]);
						int xsz=s.size();
						for (int j=i;j<=xsz;j++) s.pop();
						sb=1,cnt++,now=dot[cnt],bb=cnt;
						break;
					}
					if (ths.tl<L[_]) break;
				}
				if (!sb){
					s.push(cnt);
					break;
				}
			}
		}
//		cout<<dot[s.top()].l<<' '<<dot[s.top()].r<<'\n';
	}
}
signed main(){
	n=read();
	for (int i=1;i<=n;i++){
		int __=read();
		a[__]=read();
	}
	Q[0]=1e18;
	Init_D(),Init_L(),st.build();
	Build_Tree();
	int ans=0;
	for (int i=1;i<=cnt;i++){
//		cout<<dot[i].tl<<' '<<dot[i].tr<<'\n';
		if (dot[i].tmp) ans+=(dot[i].son.size())*(dot[i].son.size()-1)/2;
		else ans++;
	}
	cout<<ans;
	return 0;
}
2024/8/3 16:19
加载中...