萌新求问(玄关
  • 板块灌水区
  • 楼主zyc_bot
  • 当前回复7
  • 已保存回复15
  • 发布时间2024/3/24 13:43
  • 上次更新2024/3/24 15:29:24
查看原帖
萌新求问(玄关
1076445
zyc_bot楼主2024/3/24 13:43

rt,我的代码为什么输入后会卡死,求大佬解答

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<20+5];inline int read(){int x=0,f=1;char c=gc();while(!isdigit(c)){if(c=='-')f=-1;c=gc();}while(isdigit(c)){x=x*10+(c^48);c=gc();}return x*f;}

const int N = 2e5 + 1;

int n, m;
int x;
int f[N][45];
int dp[N], last[4 * N];

inline void init()
{
	for (int i = 1; i <= n; i ++ ) f[i][0] = (i - dp[i] + 1);
	for (int j = 1; (1 << j) <= int(log2(n)); j ++ )
	  for (int i = 1; i + (1 << (j - 1)) <= n; i ++ )
	  	f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

inline int ask(int L, int R)
{
	if (L > R) return 0;
	int k = log2(R - L + 1);
	return max(f[L][k], f[R - (1 << k) + 1][k]);
}

inline void solve()
{
	int x, y;
	x = read() + 1, y = read() + 1;
	int l = x, r = y, mid;
	int res;
	while (l <= r)
	{
		mid = (l + r) >> 1;
		if (dp[mid] >= x) r = mid - 1;
		else res = mid, l = mid + 1;
	}
	int cnt = max(res - x + 1, ask(res + 1, y));
	printf("%d\n", cnt);
}

int main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; i ++ )
	{
		x = read(); 
		x += 1e6;//可能为负数 
		dp[i] = max(dp[i - 1], last[x] + 1);
		last[x] = i;
	} 
    init();
    while (m -- ) solve();
	return 0;
}
2024/3/24 13:43
加载中...