[CF1132G]Greedy Subsequences

题目大意：

定义一个序列的最长贪心严格上升子序列为：任意选择第一个元素后，每次选择右侧第一个大于它的元素，直到不能选为止。

给定一个长度为\(n(n\le10^6)\)的序列\(A\)，同时给定一个常数\(k\)，求该序列的所有长度为\(k\)的子区间的最长贪心严格上升子序列的长度。

思路：

不难发现，若将每个点和右侧第一个大于它的元素相连，可以得到一个森林，其中每个结点对应的父结点为序列中右侧第一个大于它的元素。若没有区间长度为\(k\)的限制，答案就是深度最大结点的深度。

有\(k\)的限制时，可以将DFS序弄出来，用线段树维护。每次加入右端点时，将子树所有结点对应权值\(+1\)。此时权值代表的就是其在森林中的深度。

而删除左结点时，不妨将对应子树的权值重置为\(0\)，而就算它后面又被\(+1\)，也不会超过目前的根结点的权值，因此不会对结果产生影响。

时间复杂度\(\mathcal O(n\log n)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<vector>

#include<functional>

#include<ext/pb_ds/priority_queue.hpp>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=1e6+1;

std::vector<int> e[N];

inline void add_edge(const int &x,const int &y) {

	e[x].push_back(y);

}

int a[N],in[N],out[N],tot;

__gnu_pbds::priority_queue<std::pair<int,int>,std::greater<std::pair<int,int>>> q;

void dfs(const int &x) {

	in[x]=++tot;

	for(int y:e[x]) {

		dfs(y);

	}

	out[x]=tot;

}

class SegmentTree {

	#define _left <<1

	#define _right <<1|1

	#define mid ((b+e)>>1)

	private:

		int max[N<<2],tag[N<<2];

		void push_down(const int &p) {

			if(!tag[p]) return;

			if(tag[p _left]!=-1) {

				max[p _left]+=tag[p];

				tag[p _left]+=tag[p];

			}

			if(tag[p _right]!=-1) {

				max[p _right]+=tag[p];

				tag[p _right]+=tag[p];

			}

			tag[p]=0;

		}

		void push_up(const int &p) {

			max[p]=std::max(max[p _left],max[p _right]);

		}

	public:

		void add(const int &p,const int &b,const int &e,const int &l,const int &r) {

			if(tag[p]==-1) return;

			if(b==l&&e==r) {

				max[p]++;

				tag[p]++;

				return;

			}

			push_down(p);

			if(l<=mid) add(p _left,b,mid,l,std::min(mid,r));

			if(r>mid) add(p _right,mid+1,e,std::max(mid+1,l),r);

			push_up(p);

		}

		void clear(const int &p,const int &b,const int &e,const int &l,const int &r) {

			if(tag[p]==-1) return;

			if(b==l&&e==r) {

				max[p]=0;

				tag[p]=-1;

				return;

			}

			push_down(p);

			if(l<=mid) clear(p _left,b,mid,l,std::min(mid,r));

			if(r>mid) clear(p _right,mid+1,e,std::max(mid+1,l),r);

			push_up(p);

		}

		int query() const {

			return max[1];

		}

	#undef _left

	#undef _right

	#undef mid

};

SegmentTree t;

int main() {

	const int n=getint(),k=getint();

	for(register int i=1;i<=n;i++) {

		a[i]=getint();

		while(!q.empty()&&q.top().first<a[i]) {

			add_edge(i,q.top().second);

			q.pop();

		}

		q.push({a[i],i});

	}

	while(!q.empty()) {

		dfs(q.top().second);

		q.pop();

	}

	for(register int i=1;i<k;i++) {

		t.add(1,1,n,in[i],out[i]);

	}

	for(register int i=k;i<=n;i++) {

		t.add(1,1,n,in[i],out[i]);

		if(i>k) t.clear(1,1,n,in[i-k],out[i-k]);

		printf("%d%c",t.query()," \n"[i==n]);

	}

	return 0;

}

巴特西

[CF1132G]Greedy Subsequences

[CF1132G]Greedy Subsequences

题目大意：

思路：

源代码：

最新文章

热门文章