专栏文章
题解: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 个月前
前言
属于是不能给大样例的题。
思路
先说结论,最有情况下所选区间长度最多是 。
证明一下。
首先我们知道对于一个序列的平均数一定小于等于最大的,那么我们假设我们最有情况下选了 个数,那么我们将他们分成 组前面每两个分一组最后一个单成一组,然后我们发现选两组一定不如选最大的那一组,那么最多选的就是两组,而又因为如果选的大小为 不如只选 个,那么只有可能长度是 或 。
代码
直接线段树维护就行了。
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 条评论,欢迎与作者交流。
正在加载评论...