题面

有一个长度为 n \tt n n 的序列 a \tt a a ，对于每一个位置 i ∈ [ 1 , n ] \tt i\in[1,n] i∈[1,n]：

• 选择一个区间 [ l , r ] \tt[l,r] [l,r] 满足 1 ≤ l ≤ i ≤ r ≤ n \tt1\leq l\leq i\leq r\leq n 1≤l≤i≤r≤n 。
• 把区间 [ l , r ] \tt[l,r] [l,r] 中的数拿出来(很明显包括 a i \tt a_i ai​) ，从小到大排序，值相同的可以随意排。
• 中间位置定义为： { l e n g t h + 1 2 , ( l e n g t h   %   2 = 1 ) l e n g t h 2 + 1 , ( l e n g t h   %   2 = 0 ) \left\{\begin{array}{cc}\frac{\tt length+1}{2}, & (\tt length\,\%\,2=1)\\\frac{\tt length}{2}+1, & (\tt length\,\%\,2=0)\end{array}\right. {2length+1​,2length​+1,​(length%2=1)(length%2=0)​，即 ⌈ l e n g t h + 1 2 ⌉ \tt\left\lceil\frac{length+1}{2}\right\rceil ⌈2length+1​⌉ 。
• 位置 i \tt i i 的奇怪度就是 ∣ a i 排 序 后 的 位 置 − 中 间 位 置 ∣ \tt|a_i排序后的位置-中间位置| ∣ai​排序后的位置−中间位置∣ 。

给出 n \tt n n 和序列 a \tt a a ，每个位置 i \tt i i 的所选区间 [ l i , r i ] \tt[l_i,r_i] [li​,ri​] 随意，但是你得输出位置 i \tt i i 的最大奇怪度。

1 ≤ n ≤ 200   000   ,   1 ≤ a i ≤ n \tt1\leq n\leq 200\,000~,~1\leq a_i\leq n 1≤n≤200000 , 1≤ai​≤n 。

题解

定义 S 1 \tt S_1 S1​ 为区间 [ l , r ] \tt[l,r] [l,r] 中严格小于 a i \tt a_i ai​ 的元素个数， S 2 \tt S_2 S2​ 为区间 [ l , r ] \tt[l,r] [l,r] 中等于 a i \tt a_i ai​ 的元素个数(包括它自己)， S 3 \tt S_3 S3​ 为区间 [ l , r ] \tt[l,r] [l,r] 中严格大于 a i \tt a_i ai​ 的元素个数，那么位置 i \tt i i 的奇怪度就是
max ⁡ { ( S 1 + S 2 ) − ⌈ ( S 1 + S 2 ) + S 3 + 1 2 ⌉ ⌈ S 1 + ( S 2 + S 3 ) + 1 2 ⌉ − ( S 1 + 1 ) \max\left\{\begin{matrix} \tt (S_1+S_2)-\left\lceil \frac{(S_1+S_2)+S_3+1}{2} \right\rceil\\ \tt \left\lceil \frac{S_1+(S_2+S_3)+1}{2} \right\rceil-(S_1+1) \end{matrix}\right. max⎩⎨⎧​(S1​+S2​)−⌈2(S1​+S2​)+S3​+1​⌉⌈2S1​+(S2​+S3​)+1​⌉−(S1​+1)​

这里我都是忽略了绝对值符号的，因为第一行就是假设的 a i \tt a_i ai​ 在中间位置后面，第二行假设的在前面。这两种情况对于与自己相同的元素利用不同，假设 a i \tt a_i ai​ 在后面时，相同的尽量放前面(认为它们比 a i \tt a_i ai​ 小)，否则尽量放后面(认为它们比 a i \tt a_i ai​ 大)。于是就有了上面的式子。

然后我们可以发现一个性质：同时在比 a i \tt a_i ai​ 大的和比 a i \tt a_i ai​ 小的数中各减去相同数量的元素后，答案不变。相当于把排序后的序列前后各掐掉等长的一段(不去掉 a i \tt a_i ai​)，此时中间位置和 a i \tt a_i ai​ 的相对位置不变，奇怪度也不变，这个性质不难理解，看上面的式子也明白了。

那么说，对我们有用的信息就只有两者的差了！只要知道了差，然后假设较小者为 0 \tt0 0 ，再带入上述式子，得到的结果是一样的。

不妨认为与 a i \tt a_i ai​ 相等的都小于它，接下来：

先考虑只求一个位置 i \tt i i 怎么做。我们把小于 a i \tt a_i ai​ 的位置赋为 1 \tt1 1 ，大于它的位置赋为 − 1 \tt-1 −1 ，处理前缀和数组 s u m \tt sum sum ，那么就是求 ∣ s u m r − s u m l − 1 ∣ \tt|sum_r-sum_{l-1}| ∣sumr​−suml−1​∣ 的最大值。此时，由于限定了 1 ≤ l ≤ i ≤ r ≤ n \tt1\leq l\leq i\leq r\leq n 1≤l≤i≤r≤n，我们在两者的范围内分别找最大或最小的 s u m r \tt sum_r sumr​ 以及 s u m l − 1 \tt sum_{l-1} suml−1​ 的值，就可以解决问题了。

如果是多个位置 i \tt i i 呢？按照值排序，建立主席树是一个办法，但是没有必要，这道题可是离线的。我们只需要从小到大计算，每次在一个线段树上维护 s u m \tt sum sum 数组和查询就行了。需要注意，值相同的位置要先全部修改，再挨个查询。

假设与 a i \tt a_i ai​ 相等的大于它也一样，就是值相同的位置要查询后再修改罢了。

时间复杂度 Θ ( n log ⁡ n ) \tt \Theta(n\log n) Θ(nlogn) 。

CODE

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define DB double
#define LL long long
#define ENDL putchar('\n')
#define lowbit(x) ((-x) & (x))
LL read() {
	LL f=1,x=0;char s = getchar();
	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
	return f * x;
}
int n,m,i,j,s,o,k;
int a[MAXN];
vector<int> bu[MAXN];
int tre[MAXN<<2],tre2[MAXN<<2],lz[MAXN<<2],M;
void maketree(int n) {
	M=1;while(M<n+2)M<<=1;
}
void addtree(int l,int r,int y) {
	if(l > r) return ;
	int s=M+l-1,t=M+r+1;
	while(s || t) {
		if(s<M) {
			tre[s] = max(tre[s<<1],tre[s<<1|1])+lz[s];
			tre2[s] = min(tre2[s<<1],tre2[s<<1|1])+lz[s];
		}
		if(t<M) {
			tre[t] = max(tre[t<<1],tre[t<<1|1])+lz[t];
			tre2[t] = min(tre2[t<<1],tre2[t<<1|1])+lz[t];
		}
		if((s>>1) ^ (t>>1)) {
			if(!(s & 1)) tre[s^1] += y,tre2[s^1] += y,lz[s^1] += y;
			if(t & 1) tre[t^1] += y,tre2[t^1] += y,lz[t^1] += y;
		}
		s >>= 1;t >>= 1;
	}
	return ;
}
int findmax(int l,int r) {
	if(l > r) return -0x3f3f3f3f;
	int s=M+l-1,t=M+r+1;
	int ls = -0x3f3f3f3f,rs = -0x3f3f3f3f;
	while(s || t) {
		if(s<M) ls += lz[s];
		if(t<M) rs += lz[t];
		if((s>>1) ^ (t>>1)) {
			if(!(s & 1)) ls = max(tre[s^1],ls);
			if(t & 1) rs = max(tre[t^1],rs);
		}
		s >>= 1;t >>= 1;
	}
	return max(ls,rs);
}
int findmin(int l,int r) {
	if(l > r) return 0x3f3f3f3f;
	int s=M+l-1,t=M+r+1;
	int ls = 0x3f3f3f3f,rs = 0x3f3f3f3f;
	while(s || t) {
		if(s<M) ls += lz[s];
		if(t<M) rs += lz[t];
		if((s>>1) ^ (t>>1)) {
			if(!(s & 1)) ls = min(tre2[s^1],ls);
			if(t & 1) rs = min(tre2[t^1],rs);
		}
		s >>= 1;t >>= 1;
	}
	return min(ls,rs);
}
int as[MAXN];
int main() {
	n = read();
	maketree(n);
	for(int i = 1;i <= n;i ++) {
		a[i] = read();
		bu[a[i]].push_back(i);
		addtree(i,n,-1);
	}
	for(int i = 1;i <= n;i ++) {
		for(int j = 0;j <(int)bu[i].size();j ++) { // -1 -> 1
			int y = bu[i][j];
			int ll = max(0,findmax(1,y-1)),rr = findmin(y,n);
			int mx = ll-rr;
			as[y] = max(as[y],(mx+2)/2-1);
		}
		for(int j = 0;j <(int)bu[i].size();j ++) {
			int y = bu[i][j];
			addtree(y,n,2);
		}
		for(int j = 0;j <(int)bu[i].size();j ++) {
			int y = bu[i][j];
			int ll = min(0,findmin(1,y-1)),rr = findmax(y,n);
			int mi = rr-ll;
			as[y] = max(as[y],mi-(mi+2)/2);
		}
	}
	for(int i = 1;i <= n;i ++) {
		printf("%d ",as[i]);
	}ENDL;
	return 0;
}