CF1517E - Group Photo

Posted on Edited on In

CF1517E - Group Photo

题目大意

对于一个长度为 \(n\) 的序列，每个元素有一个权值 \(a_i\) ，现在为这个序列染色，每个不是C就是P，且满足

\(c_i-c_{i-1}\leq c_{i+1}-c_i\)

\(p_i-p_{i-1}\ge p_{i+1}-p_i\)

\[ \ \]

模型分析

由一个Simple的性质

对于 \(c\) 构成的连续段，只有第一段长度可能>1

对于 \(p\) 构成的连续段，只有最后一段长度可能>1

综合以上容易发现

中间交错段都是一个c一个p，两端可以有一段极长的

比较general的情况可以表示如下

# 1 2 3 4 5 6 7 8 9 10 11
C - - - - - (-)
P (-) - - - -

比较丑哈

side 就是P在C前面且只有一个长段

那么枚举 \(P\) 的长段开头，二分/尺取前面交错部分长度即可

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=2e5+10,P=998244353;

int n,a[N];
ll s[N],t[N];

int Calc(int i,ll d){
	int ans=0;
	int res=-1;
	for(int l=0,r=(i-1)/2,mid;l<=r;) 
		if(mid=(l+r)>>1,d-t[i]+t[i-mid*2]-s[i-mid*2]>0) r=mid-1,res=mid;
		else l=mid+1;
	if(~res) ans+=(i-1)/2-res+1;
	if(i==1) return ans;
	res=-1;
	for(int l=0,r=(i-2)/2,mid;l<=r;) 
		if(mid=(l+r)>>1,d-t[i]+t[i-mid*2]-s[i-mid*2]+2*a[1]>0) r=mid-1,res=mid;
		else l=mid+1;
	if(~res) ans+=(i-2)/2-res+1;
	return ans;
}

int main(){
	rep(_,1,rd()) {
		n=rd();
		rep(i,1,n) a[i]=rd();
		rep(i,1,n) s[i]=s[i-1]+a[i];
		rep(i,1,n) t[i]=a[i]-t[i-1];
		ll ans=0;
		rep(i,1,n-1) {
			ans+=Calc(i,s[n]-s[i]);
			if(i<n-1) ans+=Calc(i,s[n-1]-s[i]-a[n]);
		}
		rep(i,1,n) if(s[i]-(s[n]-s[i])>0) ans++;
		printf("%lld\n",ans%P);
	}
}