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

· · 题解

前言

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

思路

先说结论，最有情况下所选区间长度最多是 3。

证明一下。

首先我们知道对于一个序列的平均数一定小于等于最大的，那么我们假设我们最有情况下选了 2\times k+1 个数，那么我们将他们分成 k+1 组前面每两个分一组最后一个单成一组，然后我们发现选两组一定不如选最大的那一组，那么最多选的就是两组，而又因为如果选的大小为 4 不如只选 2 个，那么只有可能长度是 2 或 3。

代码

直接线段树维护就行了。

#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;
}