首页 > 代码库 > NOI模拟(3.3)螺旋序列

NOI模拟(3.3)螺旋序列

2024-09-07 00:24:36   208人阅读

Description

S也想寻求真正的智慧，然而由于“抑制力”的存在，她必须先解决一系列询
问。
有一个长度为n的序列a，一个长度为m序列b被称为螺旋序列当且仅当
b1=bm且对于1<=i<=m有bi<=b1。
S需要回答q个询问，每个询问用l,r两个参数描述，表示询问区间[l,r]的最长
连续子螺旋序列的长度。

Input

第一行两个整数n,q，表示序列长度和询问数。
第二行n个整数ai表示序列a。
以下q行，每行两个整数l,r表示一次询问。

Output

对每次询问输出一行一个整数表示最大连续螺旋序列的长度。

Sample Input

5 3
3 2 1 2 3
1 4
2 5
1 5

Sample Output

3
3
5

Data Constraint

本题采用捆绑测试，只有通过一个子任务的全部数据才能得到该子任务分
数，否则不得分。
子任务1(20分)：n,m<=10
子任务2(20分)：n,m<=1000
子任务3(20分)：n,m<=2*10^5,1<=ai<=10
子任务4(40分)：n,m<=5*10^5;|ai|<=10^9

Solution

30分的裸暴力

离散化相等的数字，做一个链表，st表处理区间最大值，对每个询问都暴力去跳

#include <map>#include <vector>#include <stdio.h>#include <string.h>#include <algorithm>#define rg registertemplate<class T> inline T dma(rg T x,rg T y) {return x>y?x:y;}template<class T> inline void read(rg T &x)	{	rg int c=getchar();rg bool b=0;	for(;c<48||c>57;c=getchar())		if(c==45)b=1;	for(x=0;c>47&&c<58;c=getchar())		x=(x<<1)+(x<<3)+c-48;	if(b)x=-x;	}const int N=500010;std::vector<int>vc;std::map<int,int>hc;int n,q,seq[N],fir[N],nex[N],st[20][N],bin[20],lgg[20],ans;void sequence_table()	{	lgg[0]=-1;for(rg int i=1;i<=n;i++)lgg[i]=lgg[i>>1]+1;	for(rg int i=0;i<20;i++)bin[i]=1<<i;	for(rg int i=1;i<=n;i++)st[0][i]=seq[i];	for(rg int t=1;t<20;t++)		for(rg int i=1;i<=n;i++)			if(i+bin[t]-1<=n)st[t][i]=dma(st[t-1][i],st[t-1][i+bin[t-1]]);	}int sequence_query(rg int x,rg int y)	{	rg int t=lgg[y-x+1];	return dma(st[t][x],st[t][y-bin[t]+1]);	}void jump(rg int x,rg int lim)	{	for(rg int rig=x,lef=nex[x];lef>=lim;lef=nex[lef])		{		while(rig>lef&&sequence_query(lef,rig)>seq[lef])rig=nex[rig];		ans=dma(ans,rig-lef+1);		}	}int main()	{	freopen("sequence.in","r",stdin);	freopen("sequence.out","w",stdout);	read(n),read(q);	for(rg int i=1;i<=n;i++)		{		read(seq[i]);		vc.push_back(seq[i]);		}	std::sort(vc.begin(),vc.end());	vc.erase(std::unique(vc.begin(),vc.end()),vc.end());	for(rg int i=0;i<vc.size();i++)		hc[vc[i]]=i+1;	for(rg int i=1;i<=n;i++)seq[i]=hc[seq[i]];	memset(fir,-1,sizeof fir);	for(rg int i=1;i<=n;i++)		{		nex[i]=fir[seq[i]];		fir[seq[i]]=i;		}	sequence_table();	for(rg int x,y;q;q--)		{		ans=1;		read(x),read(y);		for(rg int i=y;i>=x;i--)			jump(i,x);		printf("%d\n",ans);		}	fclose(stdin);	fclose(stdout);	return 0;	}

　　

NOI模拟(3.3)螺旋序列


联系
我们