专栏文章

题解:P12013 [Ynoi April Fool's Round 2025] 牢夸

P12013题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipqn2bq
此快照首次捕获于
2025/12/03 16:21
3 个月前
此快照最后确认于
2025/12/03 16:21
3 个月前
查看原文

前言

属于是不能给大样例的题。

思路

先说结论,最有情况下所选区间长度最多是 33
证明一下。
首先我们知道对于一个序列的平均数一定小于等于最大的,那么我们假设我们最有情况下选了 2×k+12\times k+1 个数,那么我们将他们分成 k+1k+1 组前面每两个分一组最后一个单成一组,然后我们发现选两组一定不如选最大的那一组,那么最多选的就是两组,而又因为如果选的大小为 44 不如只选 22 个,那么只有可能长度是 2233

代码

直接线段树维护就行了。
CPP
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
	if(x<0) printf("-"),x=-x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
const int N=1e6+10,inf=1e18;
int f[N];
int a[N],n,m;
struct node{
	int l,r;
	int tag,tag1;
	int Max,Max1;
}tr[N<<2];
void up(int x) {
	tr[x].Max=max(tr[x<<1].Max,tr[x<<1|1].Max);
	tr[x].Max1=max(tr[x<<1].Max1,tr[x<<1|1].Max1);
}
void down(int x) {
	if(tr[x].tag) {
		tr[x<<1].tag+=tr[x].tag;
		tr[x<<1|1].tag+=tr[x].tag;
		tr[x<<1].Max+=tr[x].tag;
		tr[x<<1|1].Max+=tr[x].tag;
		tr[x].tag=false;
	}
	if(tr[x].tag1) {
		tr[x<<1].tag1+=tr[x].tag1;
		tr[x<<1|1].tag1+=tr[x].tag1;
		tr[x<<1].Max1+=tr[x].tag1;
		tr[x<<1|1].Max1+=tr[x].tag1;
		tr[x].tag1=false;
	}
}
void build(int u,int l,int r) {
	tr[u]={l,r,0,0,-inf,-inf};
	if(l==r) {
		if(l+1<=n) tr[u].Max=a[l]+a[l+1];
		if(l+2<=n) tr[u].Max1=a[l]+a[l+1]+a[l+2];
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	up(u);
}
void modify(int u,int l,int r,int k) {
	if(tr[u].l>=l&&tr[u].r<=r) {
		tr[u].tag+=k;
		tr[u].Max+=k;
		return;
	}
	down(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(mid>=l) modify(u<<1,l,r,k);
	if(mid<r) modify(u<<1|1,l,r,k);
	up(u);
}
void modify1(int u,int l,int r,int k) {
	if(tr[u].l>=l&&tr[u].r<=r) {
		tr[u].tag1+=k;
		tr[u].Max1+=k;
		return;
	}
	down(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(mid>=l) modify1(u<<1,l,r,k);
	if(mid<r) modify1(u<<1|1,l,r,k);
	up(u);
}
int Ans(int u,int l,int r) {
	if(l>r) return -1e18;
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].Max;
	int mid=tr[u].l+tr[u].r>>1;
	int res=-1e18;
	down(u);
	if(mid>=l) res=Ans(u<<1,l,r);
	if(mid<r) res=max(res,Ans(u<<1|1,l,r));
	return res;
}
int Ans1(int u,int l,int r) {
	if(l>r) return -1e18;
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].Max1;
	int mid=tr[u].l+tr[u].r>>1;
	int res=-1e18;
	down(u);
	if(mid>=l) res=Ans1(u<<1,l,r);
	if(mid<r) res=max(res,Ans1(u<<1|1,l,r));
	return res;
}
void solve() {
	in(n),in(m);
	rep(i,1,n) in(a[i]);
	build(1,1,n);
	while(m--) {
		int opt;
		in(opt);
		if(opt==1) {
			int l,r,x;
			in(l),in(r),in(x);
			int r1=r-1;
			if(r1>=l) modify(1,l,r1,2*x);
			modify(1,r1+1,r,x);
			int l1=l-1;
			if(l1>=1) modify(1,l1,l-1,x);
			int r2=r-2;
			if(r2>=l) modify1(1,l,r2,3*x);
			r2++;
			if(r2>=l) modify1(1,r2,r2,2*x);
			r2++;
			if(r2>=l) modify1(1,r2,r2,x);
			int l2=l-2;
			if(l2>=1) modify1(1,l2,l2,x);
			l2++;
			if(l2>=1) modify1(1,l2,l2,2*x);
		}else {
			int l,r;
			in(l),in(r);
			int sum=Ans(1,l,r-1);
			int sum1=Ans1(1,l,r-2);
			int g=2,f=3;
			int gg=__gcd(sum,g),ff=__gcd(f,sum1);
			if(sum*3<sum1*2) swap(sum1,sum),swap(gg,ff),swap(f,g);
			if(sum==0) {
				cout<<0<<'/'<<1<<endl;
				continue;
			}
			sum/=gg;
			g/=gg;
			if(g<0) sum=-sum,g=-1*g;
			cout<<sum<<'/'<<g<<endl;
		}
	}
}
fire main() {
	while(T--) {
		solve();
	}
	return false;
}

评论

1 条评论,欢迎与作者交流。

正在加载评论...