这道题题目简洁新颖，吸引读者阅读兴趣...

题目

原题目

点这里

简要题目

需要你维护长度为n的序列并支持下列操作：

区间加法；
区间赋值；
区间每个 \(a_i\) 变成 \(\max⁡(a_i-t,0)\)；
单点询问值
单点询问历史最大值

\(n,m≤500000\)，其中 \(m\) 为操作数。

正解

首先考虑，如果这道题没有历史版本我们该怎么做？

其实很简单，这里我就不赘述了其实是我懒得说。

那么我们考虑，对于这个 \(5\) 操作，我们应该怎么做？

首先，分析 \(3\) 操作，这是一个很特殊的操作。

对于每个 \(a_i\) ，将 \(a_i\) 修改为 \(\max(a_i-t,0)\)，我们把它写成函数，即

\[f(x)=\max(x-t,0)
\]

写成一般形式，即

\[f(x)=\max(x+a,b)
\]

那么，我们可以轻松地画出这个函数的图像：

考虑能否将两个函数 \(f_1(x),f_2(x)\) 的最大值全部合并，成为 \(g(x)\)，即如下图

显然是可行的，具体如何实现请自行思考，如果实在不行，看看代码也好啊。

现在，我们来看这样的函数能不能叠加，即对于 \(f(x)=\max(x+a,b)\)，能不能给 \(a+\Delta\) 或者 \(b+\Delta\)。

显然这也是可行的，即新的 \(f'(x)=\max(x+a+\Delta,b)\) 或者是 \(f'(x)=\max(x+a,b+\Delta)\)。

发现这个函数有叠加性以及能够维护函数最大，发现似乎可以用这样的函数来做这道题，但是，需要对我们的操作进行一些变换：

设标记 \((a,b)\) 表示将 \(x\) 变成 \(\max⁡(a+x,b)\) 。

区间加上 \(a\)：\((a,-\infty)\)；
区间赋值为 \(a\)：\((-\infty,a)\)；
区间每个 \(x\) 变成 \(\max⁡(x-a,0):(-a,0)\)；
合并 \((a,b)\) 与 \((c,d)\)：\((a+c,\max⁡(b+c,d))\)；

假设对一个位置作用的标记对应函数依次为 \(f_1 (x),f_2 (x)\ldots,f_k (x)\)

历史最大值对应函数为 \(\max\{x,f_1 (x),f_2(f_1(x)),……,f_k (f_{k-1}(……f_1(x)))\}\)

如若能维护出该函数，历史最大值即可维护出。

可以发现将两个这样函数取 \(\max\) 后仍然是一个形式一样的函数(见上面的图)。于是历史最大值的函数即可维护。用线段树在每个区间维护当前标记的函数和历史最大值的函数即可，这两个都支持 \(\mathcal O(1)\) 合并。于是复杂度为 \(\mathcal O(n\log⁡n)\)。

#include<cstdio>

#define rep(i,__l,__r) for(signed i=__l,i##_end_=__r;i<=i##_end_;++i)

#define fep(i,__l,__r) for(signed i=__l,i##_end_=__r;i>=i##_end_;--i)

#define writc(a,b) fwrit(a),putchar(b)

#define mp(a,b) make_pair(a,b)

#define ft first

#define sd second

#define LL long long

#define ull unsigned long long

#define uint unsigned int

#define pii pair< int,int >

#define Endl putchar('\n')

// #define FILEOI

#define int long long

// #define int unsigned

#ifdef FILEOI

# define MAXBUFFERSIZE 500000

    inline char fgetc(){

        static char buf[MAXBUFFERSIZE+5],*p1=buf,*p2=buf;

        return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXBUFFERSIZE,stdin),p1==p2)?EOF:*p1++;

    }

# undef MAXBUFFERSIZE

# define cg (c=fgetc())

#else

# define cg (c=getchar())

#endif

template<class T>inline void qread(T& x){

    char c;bool f=0;

    while(cg<'0'||'9'<c)f|=(c=='-');

    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));

    if(f)x=-x;

}

inline int qread(){

    int x=0;char c;bool f=0;

    while(cg<'0'||'9'<c)f|=(c=='-');

    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));

    return f?-x:x;

}

template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}

template<class T>inline T Max(const T x,const T y){return x>y?x:y;}

template<class T>inline T Min(const T x,const T y){return x<y?x:y;}

template<class T>inline T fab(const T x){return x>0?x:-x;}

inline int gcd(const int a,const int b){return b?gcd(b,a%b):a;}

inline void getInv(int inv[],const int lim,const int MOD){

    inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;

}

template<class T>void fwrit(const T x){

    if(x<0)return (void)(putchar('-'),fwrit(-x));

    if(x>9)fwrit(x/10);

    putchar(x%10^48);

}

inline LL mulMod(const LL a,const LL b,const LL mod){//long long multiplie_mod

    return ((a*b-(LL)((long double)a/mod*b+1e-8)*mod)%mod+mod)%mod;

}

const int MAXN=5e5;

const int INF=0x3f3f3f3f3f3f3f3fll;

int n,m,val[MAXN+5];

int a[(MAXN<<2)+5][2],b[(MAXN<<2)+5][2];

//a[i][0],b[i][0]:维护当前的 a,b , 若 i 不是叶节点, 那么这就是懒标记

//a[i][1],b[i][1]:维护历史最大版本

#define lc (i<<1)

#define rc (i<<1|1)

#define fff (i>>1)

#define MID ((l+r)>>1)

#define LEQ lc,l,MID

#define REQ rc,MID+1,r

inline void upd(const int i){

    a[i][1]=Max(a[i][1],a[i][0]+a[fff][1]);

    b[i][1]=Max(b[i][1],Max(b[i][0]+a[fff][1],b[fff][1]));

    a[i][0]=Max(a[i][0]+a[fff][0],-INF),b[i][0]=Max(b[i][0]+a[fff][0],b[fff][0]);

}

inline void pushdown(const int i){

    upd(lc),upd(rc);

    a[i][0]=a[i][1]=0,b[i][0]=b[i][1]=-INF;

}

void modify(const int i,const int l,const int r,const int L,const int R,const int c,const int d){

    if(L<=l && r<=R){

        a[i][1]=Max(a[i][1],a[i][0]+c);

        b[i][1]=Max(b[i][1],Max(b[i][0]+c,d));

        a[i][0]=Max(a[i][0]+c,-INF),b[i][0]=Max(b[i][0]+c,d);

        return;

    }

    pushdown(i);

    if(L<=MID)modify(LEQ,L,R,c,d);

    if(MID<R)modify(REQ,L,R,c,d);

}

int query(const int i,const int l,const int r,const int p,const int o){

    if(l==r)return Max(val[p]+a[i][o],b[i][o]);

    pushdown(i);

    if(p<=MID)return query(LEQ,p,o);

    else return query(REQ,p,o);

}

signed main(){

#ifdef FILEOI

    freopen("file.in","r",stdin);

    freopen("file.out","w",stdout);

#endif

    qread(n,m);

    rep(i,1,n)qread(val[i]);

    int t,l,r,x;

    while(m--){

        qread(t,l);

        if(t<=3){

            qread(r,x);

            if(t==1)modify(1,1,n,l,r,x,-INF);

            else if(t==2)modify(1,1,n,l,r,-x,0);

            else modify(1,1,n,l,r,-INF,x);

        }

        else writc(query(1,1,n,l,t-4),'\n');

    }

    return 0;

}

巴特西

「题解」「UOJ-164」「清华集训2015」V

题目

原题目

简要题目

正解

最新文章

热门文章