bzoj 4358 permu

Posted on | Views:

莫队.

使用莫队,考虑加入一个数 $x$ 造成的影响,发现需要用到 $x-1,x+1$ 的信息.

需要对每个数维护当前它所在的最大连续区间长度,但修改时可能会修改很多数的答案.

简单粗暴的办法是用线段树维护最大子段和,但多一个 $\log$ ,而且常数比较大,跑不过去.

用 $pre_i,nxt_i$ 分别表示 $i$ 在值域上往左/右走最多有几个数, $pre_i+nxt_i-1$ 可以更新答案.

插入数 $i$ 的时候,用 $i-1$ 的 $pre$ 更新 $i$ 的 $pre$ ,用 $i+1$ 的 $nxt$ 更新 $i$ 的 $nxt$ .

然后再更新 $i$ 所在最长连续区间左端点的 $nxt$ 和右端点的 $pre$ .

中间不用管,因为不可能再在中间插入数,也就不可能再用到它们的 $pre,nxt$ 了.

发现删除操作不好维护,我们可以保证右端点不删除,只可能撤销左端点的插入操作,就可以维护了.

对于 $l$ 在同一块内的询问,若 $r​$ 也在这一块内,可以暴力做.

对于 $r$ 在这一块外的,将它们按照 $r$ 从小到大排序.

先将 $L$ 设置为当前块的末尾,右移 $R$ 到询问的 $r$ ,再将 $L$ 左移到询问的 $l$ ,更新答案,再将 $L$ 移回当前块的末尾.

因为插入一个数最多只会影响 $3$ 个数的信息,所以把它们记录下来,移回时撤销,时间复杂度 $O(n\sqrt n)$ .

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=5e4+10;
int n,m,res,Ans[MAXN];
int BlockSize,tot=0,bel[MAXN],a[MAXN];
int lpos[MAXN],rpos[MAXN];
struct Query
{
	int l,r,id,block;
	bool operator < (const Query &rhs) const
	{
		return block==rhs.block?r<rhs.r:block<rhs.block;
	}
}q[MAXN];
int bf_pre[MAXN],bf_nxt[MAXN];
int bf_stk[MAXN],bf_tp;
int bf(int i)
{
	bf_tp=0;
	int ans=0;
	for(int j=q[i].l;j<=q[i].r;++j)
	{
		int x=a[j];
		bf_stk[++bf_tp]=x;
		bf_pre[x]=bf_pre[x-1]+1;
		bf_nxt[x]=bf_nxt[x+1]+1;
		int len=bf_pre[x]+bf_nxt[x]-1;
		ans=max(ans,len);
		bf_nxt[x-bf_pre[x]+1]=len;
		bf_pre[x+bf_nxt[x]-1]=len;
	}
	Ans[q[i].id]=ans;
	for(int j=1;j<=bf_tp;++j)
		bf_pre[bf_stk[j]]=bf_nxt[bf_stk[j]]=0;
}
int nxt[MAXN],pre[MAXN],tp;
struct opt
{
	int x;
	int p1,n1;
	// pre[x]:p1->p2 nxt[x]:n1->n2
	void undo()
	{
		pre[x]=p1;
		nxt[x]=n1;
	}
};
opt stk[MAXN];
void solve()
{
	int lstblock=-1,L,R;
	for(int i=1;i<=m;++i)
	{
		if(q[i].block!=lstblock)
		{
			L=rpos[q[i].block];
			R=L-1;
			res=0;
			memset(pre,0,sizeof pre);
			memset(nxt,0,sizeof nxt);
			tp=0;
			lstblock=q[i].block;
		}
		if(bel[q[i].l]==bel[q[i].r])
		{
			bf(i);
			continue;
		}
		while(R<q[i].r)
		{
			int x=a[++R];
			pre[x]=pre[x-1]+1;
			nxt[x]=nxt[x+1]+1;
			int len=pre[x]+nxt[x]-1;
			res=max(res,len);
			nxt[x-pre[x]+1]=len;
			pre[x+nxt[x]-1]=len;
		}
		int tmp=res;
		while(L>q[i].l)
		{
			int x=a[--L];
			pre[x]=pre[x-1]+1;
			nxt[x]=nxt[x+1]+1;
			stk[++tp]=(opt){x,0,0};
			int len=pre[x]+nxt[x]-1;
			stk[++tp]=(opt){x-pre[x]+1,pre[x-pre[x]+1],nxt[x-pre[x]+1]};
			stk[++tp]=(opt){x+nxt[x]-1,pre[x+nxt[x]-1],nxt[x+nxt[x]-1]};
			nxt[x-pre[x]+1]=len;
			pre[x+nxt[x]-1]=len;
			res=max(res,len);
		}
		Ans[q[i].id]=res;
		while(tp)
		{
			stk[tp].undo();
			--tp;
		}
		L=rpos[q[i].block];
		res=tmp;
	}
}
void init_Block()
{
	BlockSize=sqrt(n);
	for(int i=1;i<=n;++i)
		bel[i]=(i-1)/BlockSize+1;
	tot=bel[n];
	for(int i=1;i<=n;++i)
		rpos[bel[i]]=i;
	for(int i=n;i>=1;--i)
		lpos[bel[i]]=i;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	init_Block();
	for(int i=1;i<=m;++i)
	{
		q[i].l=read();
		q[i].r=read();
		q[i].block=bel[q[i].l];
		q[i].id=i;
	}
	sort(q+1,q+1+m);
	solve();
	for(int i=1;i<=m;++i)
		printf("%d\n",Ans[i]);
	return 0;
}