吉司机线段树求条
查看原帖
吉司机线段树求条
905636
_xguagua_Firefly_楼主2025/1/18 21:01

题目

#include <bits/stdc++.h>
#define int long long
using namespace std;

constexpr int MAXN = 3e5 + 5,inf = 1e17;
int a[MAXN],b[MAXN],n,m,opt,l,r,x;
struct Info
{
    int mx,smx,mxCnt,laz1,laz2;
    void init()
    {laz1 = laz2 = 0;}
};
struct Rukkhadevata
{
    Info tag[2];
    int ans;
}tree[MAXN << 2];
inline void pushup(int rt,bool t)
{
    Info& ls = tree[rt << 1].tag[t],&rs = tree[rt << 1 | 1].tag[t];
    tree[rt].tag[t].mx = max(ls.mx,rs.mx);
    if(ls.mx == rs.mx)
    {
        tree[rt].tag[t].smx = max(ls.smx,rs.smx);
        tree[rt].tag[t].mxCnt = ls.mxCnt + rs.mxCnt;
    }
    else if(ls.mx > rs.mx)
    {
        tree[rt].tag[t].smx = max(ls.smx,rs.mx);
        tree[rt].tag[t].mxCnt = ls.mxCnt;
    }
    else
    {
        tree[rt].tag[t].smx = max(ls.mx,rs.smx);
        tree[rt].tag[t].mxCnt = rs.mxCnt;
    }
}
inline void pushup(int rt)
{
    pushup(rt,0),pushup(rt,1);
    tree[rt].ans = max(tree[rt << 1].ans,tree[rt << 1 | 1].ans);
}
inline void update(int rt,int laz1,int laz2,bool t)
{
    tree[rt].tag[t].mx += laz1,tree[rt].ans += laz1;
    if(tree[rt].tag[t].smx != -inf)
        tree[rt].tag[t].smx += laz2;
    tree[rt].tag[t].laz1 += laz1,tree[rt].tag[t].laz2 += laz2;
}
inline void pushdown(int rt,bool t)
{
    Info &ls = tree[rt << 1].tag[t],&rs = tree[rt << 1 | 1].tag[t];
    int Max = max(ls.mx,rs.mx);
    if(ls.mx == Max)
        update(rt << 1,tree[rt].tag[t].laz1,tree[rt].tag[t].laz2,t);
    else
        update(rt << 1,tree[rt].tag[t].laz2,tree[rt].tag[t].laz2,t);
    if(rs.mx == Max)
        update(rt << 1,tree[rt].tag[t].laz1,tree[rt].tag[t].laz2,t);
    else
        update(rt << 1 | 1,tree[rt].tag[t].laz1,tree[rt].tag[t].laz2,t);
    tree[rt].tag[t].init();
}
inline void pushdown(int rt)
{
    pushdown(rt,0),pushdown(rt,1);
}
inline void build(int l,int r,int rt)
{
    tree[rt].tag[0].init(),tree[rt].tag[1].init();
    if(l == r)
    {
        tree[rt].ans = a[l] + b[l];
        tree[rt].tag[0].mx = a[l],tree[rt].tag[1].mx = b[l];
        tree[rt].tag[0].smx = tree[rt].tag[1].smx = -inf;
        tree[rt].tag[0].mxCnt = tree[rt].tag[1].mxCnt = 1;
        return ;
    }
    int mid = (l + r) >> 1;
    build(l,mid,rt << 1);
    build(mid + 1,r,rt << 1 | 1);
    pushup(rt);
}
inline void modifyMin(int rt,int l,int r,int L,int R,int val,bool t)
{
    if(tree[rt].tag[t].mx <= val)
        return ;
    if(L <= l && R >= r && tree[rt].tag[t].smx < val)
        return update(rt,val - tree[rt].tag[t].mx,0,t);
    pushdown(rt);
    int mid = (l + r) >> 1;
    if(L <= mid)
        modifyMin(rt << 1,l,mid,L,R,val,t);
    if(R > mid)
        modifyMin(rt << 1,mid + 1,r,L,R,val,t);
    pushup(rt);
}
inline void modifySum(int rt,int l,int r,int L,int R,int val,bool t)
{
    if(L <= l && R >= r)
        return update(rt,val,val,t);
    pushdown(rt);
    int mid = (l + r) >> 1;
    if(L <= mid)
        modifySum(rt << 1,l,mid,L,R,val,t);
    if(R > mid)
        modifySum(rt << 1 | 1,mid + 1,r,L,R,val,t);
    pushup(rt);
}
inline int query(int rt,int l,int r,int L,int R)
{
    if(L <= l && R >= r)
        return tree[rt].ans;
    pushdown(rt);
    int mid = (l + r) >> 1,res = -inf;
    if(L <= mid)
        res = max(res,query(rt << 1,l,mid,L,R));
    if(R > mid)
        res = max(res,query(rt << 1 | 1,mid + 1,r,L,R));
    return res;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    for(int i = 1;i <= n;i++)
        cin >> b[i];
    for(int i = 1;i <= m;i++)
    {
        cin >> opt >> l >> r;
        if(opt == 1 || opt == 2)
        {
            cin >> x;
            modifyMin(1,1,n,l,r,x,opt - 1);
        }
        if(opt == 3 || opt == 4)
        {
            cin >> x;
            modifySum(1,1,n,l,r,x,opt - 3);
        }
        if(opt == 5)
            cout << query(1,1,n,l,r) << "\n";
    }
}

RE + WA

2025/1/18 21:01
加载中...