CF2231B Another Sorting Problem

思路

思维好题。
首先题目允许最多一次操作，选择一个正整数 $k$ 和一个子序列，将该子序列的所有元素加上 $k$。问能否使数组变为非递减序列。
如果开始的序列就满足条件，则直接特判掉。
由于只能加不能减，且只能操作一次，这意味着如果某个位置 $i$ 需要增加（因为 $a_i>a_{i+1}$），那么 $i$ 及其之后的某些元素一定被选中。
这就相当于把整个数组划分为两个互补的子序列，且两个子序列内都是有序的（若无序，同时加 $k$ 还是无序）。
那么我们首先找出所有逆序对位置，这些逆序对的前一个数一定被选中，后一个数一定不选中，不然就会导致无序。
如果存在连续的逆序对（如位置 $i$ 和 $i+1$ 都是某逆序对的前一个数），则不可能，因为同一个位置不可能既被选中又未被选中。

在这一步中，我们可以计算出 $k$ 的最小上界 $L$。
再按照选中和未选中划分数组，找到从每个选中段到未选中段的最大差值，这决定了 $k$ 的最大下界 $K$。
然后判断 $K\le L$ 是否成立即可得出有没有合法 $k$。

代码

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
146
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pii pair<int,int>
#define double long double
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	inline void read(char &c){
		c=getchar();
		while(isspace(c))c=getchar();
	}
	inline void read(std::string &s){
		s.clear();char c=getchar();
		for(;isspace(c);c=getchar());
		for(;!isspace(c)&&c!=EOF;c=getchar())s+=c;
	}
	template<typename T,typename...Args>
	void read(T &x,Args&...args){
		read(x);read(args...);
	}
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
	inline void print(char c){
		putchar(c);
	}
	inline void print(std::string s){
		fep(i,0,s.size())putchar(s[i]);
	}
	inline void print(const char*s){
		while(*s)putchar(*s++);
	}
	template<typename T,typename...Args>
	void print(const T &x,const Args&...args){
		print(x);print(args...);
	}
}
using namespace std;
using namespace FastIO;
const int N=2e5+47;
const int inf=1e18;
int T,n,a[N];
int solve(){
	read(n);
	rep(i,1,n)read(a[i]);
	int srt=1;
	rep(i,1,n-1){
		if(a[i]>a[i+1]){
			srt=0;
			break;
		}
	}
	if(srt)return 1;
	vector<int>pl;
	rep(i,1,n-1){
		if(a[i]>a[i+1])pl.push_back(i);
	}
	fep(i,0,(int)pl.size()-1){
		if(pl[i+1]==pl[i]+1)return 0;
	}
	vector<int>x(n+1,-1);
	int L=1;
	for(int i:pl){
		if(x[i]==1||x[i+1]==0)return 0;
		x[i]=0;
		x[i+1]=1;
		L=max(L,a[i]-a[i+1]);
	}
	queue<int>q;
	vector<int>inq(n+1,0);
	rep(i,1,n){
		if(x[i]!=-1){
			q.push(i);
			inq[i]=1;
		}
	}
	while(!q.empty()){
		int i=q.front();q.pop();
		inq[i]=0;
		if(x[i]==1){
			if(i+1<=n&&a[i]==a[i+1]){
				if(x[i+1]==0)return 0;
				if(x[i+1]==-1){
					x[i+1]=1;
					if(!inq[i+1]){
						q.push(i+1);
						inq[i+1]=1;
					}
				}
			}
		}
		else if(x[i]==0){
			if(i-1>=1&&a[i-1]==a[i]){
				if(x[i-1]==1)return 0;
				if(x[i-1]==-1){
					x[i-1]=0;
					if(!inq[i-1]){
						q.push(i-1);
						inq[i-1]=1;
					}
				}
			}
		}
	}
	rep(i,1,n-1){
		if(x[i]!=-1&&x[i+1]!=-1){
			if(x[i]==x[i+1]&&a[i]>a[i+1])return 0;
			if(x[i]==1&&x[i+1]==0&&a[i]>=a[i+1])return 0;
		}
	}
	int U=inf;
	int val=-1,pos=-1;
	rep(i,1,n){
		if(x[i]!=-1){
			if(val==1&&x[i]==0){
				int mx=0;
				rep(j,pos,i-1){
					int dif=a[j+1]-a[j];
					if(dif>mx)mx=dif;
				}
				if(mx<U)U=mx;
			}
			val=x[i];
			pos=i;
		}
	}
	return L<=U;
}
signed main(){
	read(T);
	while(T--){
		if(solve())puts("Yes");
		else puts("No");
	}
}