• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

[CF809D] Hitchhiking in the Baltic States

开发技术 开发技术 1周前 (04-30) 4次浏览

(text{Problem}:)Hitchhiking in the Baltic States

(text{Solution}:)

(f_{i}) 表示长度为 (i) 的严格上升子序列中第 (i) 个数的最小值,有转移:

  • (f_{j-1}< l_{i})(f_{j}=min{f_{j},l_{i}})
  • (l_{i}leq f_{j-1}<r_{i})(f_{j}=min{f_{j},f_{j-1}+1})
  • (f_{j-1}geq r_{i})(f_{j}) 无法从 (f_{j-1}) 转移。

不难发现,(f_{i}) 是严格上升的。故可以二分求出三类转移的边界。设 (p) 为最大的 (f_{p}) 满足 (f_{p}<l_{i})(q) 为最大的 (f_{q}) 满足 (f_{q}<l_{i}),有:

  • (f_{p+1}=l_{i})
  • ([p+1,q]) 区间加 (1),并向右平移至 ([p+2,q+1])

可以用平衡树维护上面的操作。具体的,每次插入 (l_{i}),查询 (x) 为最小的 (f_{x}) 满足 (f_{x}geq r_{i}) 并删去。发现这么操作已经相当于把区间 ([p+1,q]) 整体向右转移一位。总时间复杂度 (O(nlog n))

(text{Code}:)

#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=300010;
inline int read()
{
	int s=0, w=1; ri char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
	return s*w;
}
int n,root,ch[N][2],siz[N],rnd[N],val[N],tag[N],cnt;
inline void Push_Up(int x) { siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1; }
inline int New_Node(int x) { val[++cnt]=x, siz[cnt]=1, rnd[cnt]=rand(); return cnt; }
inline void Push_Down(int x)
{
	if(!tag[x]) return;
	if(ch[x][0]) tag[ch[x][0]]+=tag[x], val[ch[x][0]]+=tag[x];
	if(ch[x][1]) tag[ch[x][1]]+=tag[x], val[ch[x][1]]+=tag[x];
	tag[x]=0;
}
void Split(int root,int k,int &x,int &y)
{
	if(!root) { x=y=0; return; }
	Push_Down(root);
	if(val[root]<=k) x=root, Split(ch[root][1],k,ch[root][1],y);
	else y=root, Split(ch[root][0],k,x,ch[root][0]);
	Push_Up(root);
}
int Merge(int x,int y)
{
	if(!x||!y) return x|y;
	Push_Down(x), Push_Down(y);
	if(rnd[x]<rnd[y]) { ch[x][1]=Merge(ch[x][1],y), Push_Up(x); return x; }
	else { ch[y][0]=Merge(x,ch[y][0]), Push_Up(y); return y; }
}
inline void Insert(int k)
{
	int x,y;
	Split(root,k,x,y);
	root=Merge(Merge(x,New_Node(k)),y);
}
inline void Delete(int k)
{
	int x,y,z;
	Split(root,k,x,y);
	Split(x,k-1,x,z);
	z=Merge(ch[z][0],ch[z][1]);
	root=Merge(Merge(x,z),y);
}
inline int Kth(int x,int k)
{
	if(!x||!k) return 0;
	while(1)
	{
		if(siz[ch[x][0]]>=k) x=ch[x][0];
		else if(siz[ch[x][0]]==k-1) return x;
		else k-=siz[ch[x][0]]+1, x=ch[x][1];
	}
}
inline int GetNxt(int k)
{
	int x,y;
	Split(root,k,x,y);
	int bk=val[Kth(y,1)];
	root=Merge(x,y);
	return bk;
}
inline void UpDate(int l,int r)
{
	int x,y,z;
	Split(root,l-1,x,y);
	Split(y,r,y,z);
	if(y) val[y]++, tag[y]++;
	root=Merge(x,Merge(y,z));
}
signed main()
{
	srand(time(NULL));
	n=read();
	for(ri int i=1;i<=n;i++)
	{
		int l,r;
		l=read(), r=read();
		int g=GetNxt(r-1);
		UpDate(l,r-1);
		Insert(l);
		if(g) Delete(g);
	}
	printf("%dn",siz[root]);
	return 0;
}

程序员灯塔
转载请注明原文链接:[CF809D] Hitchhiking in the Baltic States
喜欢 (0)