「ZJOI模拟赛」Bug级的存在

发表于 | 分类于 | | 浏览量： 次

什么毒瘤题目QwQ。

传送门

原题链接：

CF407E

洛谷

题解

首先一个区间满足条件，必须要有整个区间内的$A_i$模$d​$同余，并且没有相同元素，暂时先不考虑需要补上的数的个数。

考虑从左往右枚举右端点$head$，再用一个指针$tail$来控制合法的左端点所在区间，如果$[head,tail]$这个区间不合法，那么就让$tail++$，此时如果左端点$L$在$[head,tail]$区间内构成的所有区间$[L,head]$都合法。而且很显然当$head$变大时，$tail$单调不将。

然后对于左端点$L (L\in[tail,head])$，考虑需要补上的元素个数是否会超过$k$，推一下式子，移一下项，发现当满足以下式子时的左端点$L​$就是合法的：

此时当右端点确定时，式子的右边也是确定的。也就是说，我们要找一个满足上式的且最靠左的左端点$L$。可以通过一些办法维护每个左端点$L$到当前枚举到的右端点区间内的最大值和最小值。

当右端点向右移动的时候，考虑维护两个单调栈，一个单调增，一个单调降，就拿单调增的来举例。由单调栈的性质可以得出，区间$[stack[top-1]+1,stack[top]]$内的每一个元素的值都大于$stack[top]$的值，所以当栈顶要被弹出时，将区间$[stack[top-1]+1,stack[top]]$内的每一个左端点的最小值都减去当前值与栈顶的差值。最大值同理。可以用线段树来维护。

然后就可以在线段树上二分来找满足条件的最靠左的左端点，如果当前遍历到的节点的左节点所管辖的区间内中有满足条件的节点就往左走，否则就往右走。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200005;const LL inf=0x3F3F3F3F3F3F3F3Fll;
int n,k,d,A[maxn],Area[maxn],num,hed,til,top1,stk1[maxn],top2,stk2[maxn],ans,ansL,ansR;map<int,int> H;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct SegmentTree
{
	struct Node{LL Mi,Ma,TagMi,TagMa,Val;}Tree[maxn*4];
	void PushUp(int rt)
	{
		Tree[rt].Mi=min(Tree[rt*2].Mi,Tree[rt*2+1].Mi);
		Tree[rt].Ma=max(Tree[rt*2].Ma,Tree[rt*2+1].Ma);
		Tree[rt].Val=min(Tree[rt*2].Val,Tree[rt*2+1].Val);
	}
	void PushDown(int rt)
	{
		Tree[rt*2].Mi+=Tree[rt].TagMi;Tree[rt*2].TagMi+=Tree[rt].TagMi;Tree[rt*2].Val-=Tree[rt].TagMi;
		Tree[rt*2].Ma+=Tree[rt].TagMa;Tree[rt*2].TagMa+=Tree[rt].TagMa;Tree[rt*2].Val+=Tree[rt].TagMa;
		Tree[rt*2+1].Mi+=Tree[rt].TagMi;Tree[rt*2+1].TagMi+=Tree[rt].TagMi;Tree[rt*2+1].Val-=Tree[rt].TagMi;
		Tree[rt*2+1].Ma+=Tree[rt].TagMa;Tree[rt*2+1].TagMa+=Tree[rt].TagMa;Tree[rt*2+1].Val+=Tree[rt].TagMa;
		Tree[rt].TagMi=Tree[rt].TagMa=0;
	}
	void RangeUpdateMin(int LL,int RR,int delta,int L=1,int R=n,int rt=1)
	{
		if(LL<=L&&R<=RR){Tree[rt].Mi+=delta;Tree[rt].TagMi+=delta;Tree[rt].Val-=delta;return;}
		PushDown(rt);
		int M=(L+R)/2;
		if(LL<=M) RangeUpdateMin(LL,RR,delta,L,M,rt*2);
		if(M<RR) RangeUpdateMin(LL,RR,delta,M+1,R,rt*2+1);
		PushUp(rt);
	}
	void RangeUpdateMax(int LL,int RR,int delta,int L=1,int R=n,int rt=1)
	{
		if(LL<=L&&R<=RR){Tree[rt].Ma+=delta;Tree[rt].TagMa+=delta;Tree[rt].Val+=delta;return;}
		PushDown(rt);
		int M=(L+R)/2;
		if(LL<=M) RangeUpdateMax(LL,RR,delta,L,M,rt*2);
		if(M<RR) RangeUpdateMax(LL,RR,delta,M+1,R,rt*2+1);
		PushUp(rt);
	}
	void Delete(int P,int L=1,int R=n,int rt=1)
	{
		if(L==P&&R==P){Tree[rt].Val=inf;return;}
		PushDown(rt);
		int M=(L+R)/2;
		if(P<=M) Delete(P,L,M,rt*2);
		if(M<P) Delete(P,M+1,R,rt*2+1);
		PushUp(rt);
	}
	void Build(int L=1,int R=n,int rt=1)
	{
		if(L==R){Tree[rt].Val=L;Tree[rt].Mi=Tree[rt].Ma=A[L];return;}
		int M=(L+R)/2;
		Build(L,M,rt*2);
		Build(M+1,R,rt*2+1);
		PushUp(rt);
	}
	LL Query(int num,int L=1,int R=n,int rt=1)
	{
		if(L==R) return L;
		int M=(L+R)/2;
		PushDown(rt);
		if(Tree[rt*2].Val<=num) return Query(num,L,M,rt*2);
		else return Query(num,M+1,R,rt*2+1);
	}
}T;
int main()
{
	n=read();k=read();d=read();
	for(int i=1;i<=n;i++) A[i]=read()+1000000000;
	if(!d)
	{
		for(int i=1,j;i<=n;)
		{
			j=i;
			while(j<n&&A[j+1]==A[i]) j++;
			if(j-i+1>ans){ans=j-i+1;ansL=i;ansR=j;}
			i=j+1;
		}
		printf("%d %d\n",ansL,ansR);
		return 0;
	}
	for(int i=1;i<=n;)
	{
		int j=i;Area[i]=i;
		while(j<n&&A[j+1]%d==A[i]%d){j++;Area[j]=i;}
		i=j+1;
	}
	til=1;T.Build();
	while(hed<n)
	{
		hed++;H[A[hed]]++;
		while(H[A[hed]]>1||Area[hed]!=Area[til]){T.Delete(til);H[A[til]]--;til++;}
		while(top1>0&&A[hed]<=A[stk1[top1]])
		{
			T.RangeUpdateMin(stk1[top1-1]+1,stk1[top1],A[hed]/d-A[stk1[top1]]/d);
			top1--;
		}
		stk1[++top1]=hed;
		while(top2>0&&A[hed]>=A[stk2[top2]])
		{
			T.RangeUpdateMax(stk2[top2-1]+1,stk2[top2],A[hed]/d-A[stk2[top2]]/d);
			top2--;
		}
		stk2[++top2]=hed;
		LL L=T.Query(hed+k);
		if(L>=til&&hed-L+1>ans){ans=hed-L+1;ansL=L;ansR=hed;}
	}
	printf("%d %d\n",ansL,ansR);
	return 0;
}