【bzoj3005】体育课

2015.04.28 11:07 Tue | 56次阅读 | 旧日oi | 固定链接 | 源码

Description

       又是一节体育课的时间了,有n个同学排成了一排。他们都很讨厌排在第一个位置的同学,于是后面的同学中比第一个高的都会产生一个高兴值,这个高兴值等于他的身高减去第一个同学的身高。当然比第一个同学矮的同学产生兴奋值为0。
现在体育老师来了,他拥有神奇的魔法,现在他能做如下的三件事:
       1:询问某段区间高兴值最大的那个是多少。
       2:把某两个同学交换一下位置。
       3:选取一段区间的人,把第一个人身高加上t,第二个加上2t,第三个加上3t以此类推。
但是体育老师不会数数,于是他找到你了,对于每一个询问,他要你帮他求出那个值。

Input

第一行两个整数n,m表示有n个人,有m个操作。
第二行n个整数,顺序输入每个人的身高。(身高<=10^8)
接下来m行,每行第一个数位一个type表示是做哪一件事情。
如果type=1,那么接下来有两个整数l,r,表示询问这段区间的最大的高兴值
如果Type=2,接下来两个整数a,b,表示交换这两个位置的人
如果type=3,接下来三个整数l,r,t,表示把l个人的升高增加t,l+1个人增加2t…第r个人增加(r-l+1)t, (0<=t<= 10000)

Output

对于每个询问按照顺序输出每个操作1的答案。

Sample Input

10 7
10 9 8 7 6 5 4 3 2 1
1 4 7
3 2 4 3
1 2 3
1 3 6
2 1 10
1 8 10
1 2 3

Sample Output

0
4
6
9
13

HINT

对于100的数据:n,m<=100000

题解

跟2388差不多,把对后面的操作删掉再加一个交换就行了。
50秒时限,本机测42秒A,交上去tle,把一些ll改成int,本机37秒A,交上去49秒A………

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 101000
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
namespace IStream{
    const int L=1<<15;
    char buffer[L],*S,*T;
    inline char Get_Char()
    {
        if(S==T)
        {
            T=(S=buffer)+fread(buffer,1,L,stdin);
            if(S==T) return EOF;
        }
        return *S++;
    }
    inline int Get_Int()
    {
        char c;
        int re=0;
        for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
        while(c>='0'&&c<='9')
            re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
        return re;
    }
}
int n,q,w,x,y,m,z,block;
ll sum[maxn],dif[maxn],fir[maxn];
int pos[maxn],con[505][505],num[maxn],st[maxn];
inline double slop(int x,int y)
{
    return (double)(sum[y]-sum[x])/(y-x);
}
ll max(ll a,ll b)
{
    return a>b?a:b;
}
void reset(int x)
{
    if(x==184)
    {
        int tmp=1;
    }
    int l=(x-1)*block+1,r=min(n,x*block);
    int top=0;st[++top]=l;
    for(int i=l+1;i<=r;i++)
    {
        while(top>=2&&slop(st[top-1],st[top])<slop(st[top-1],i)) top--;
        st[++top]=i;
    }
    st[0]=0;st[top+1]=n+1;num[x]=top;
    //for(int i=1;i<=top;i++) cout<<sum[st[i]]<<" ";
    for(int i=0;i<=top+1;i++) con[x][i]=st[i];
}
void pushdown(int x)
{
    ll tmp=fir[x];
    for(int i=(x-1)*block+1;i<=min(x*block,n);i++)
        tmp+=dif[x],sum[i]+=tmp;
    fir[x]=dif[x]=0;
}
inline ll calc(int x)
{
    return sum[x]+fir[pos[x]]+dif[pos[x]]*(x-(pos[x]-1)*block);
}
ll find(int x)
{
    int l=1,r=num[x],mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        ll t1=calc(con[x][mid-1]);
        ll t2=calc(con[x][mid]);
        ll t3=calc(con[x][mid+1]);
        if(t1<t2&&t2<t3) l=mid+1;
        else if(t1>t2&&t2>t3) r=mid-1;
        else return t2;
    }
}
void update(int l,int r,ll x)
{
    ll tmp=0;
    if(pos[l]==pos[r])
    {
        pushdown(pos[l]);
        for(int i=l;i<=r;i++) tmp+=x,sum[i]+=tmp;
        reset(pos[l]);return;
    }
    pushdown(pos[l]);
    for(int i=l;i<=pos[l]*block;i++) tmp+=x,sum[i]+=tmp;
    reset(pos[l]);
    for(int i=pos[l]+1;i<pos[r];i++)
    {
        fir[i]+=tmp;
        dif[i]+=x;
        tmp+=(ll)block*x;
    }
    pushdown(pos[r]);
    for(int i=(pos[r]-1)*block+1;i<=r;i++) tmp+=x,sum[i]+=tmp;
    reset(pos[r]);
}
ll query(int l,int r)
{
    ll ans=0;
    if(pos[l]==pos[r])
    {
        for(int i=l;i<=r;i++) ans=max(ans,calc(i));
        return max(0ll,ans-calc(1));
    }
    for(int i=l;i<=pos[l]*block;i++) ans=max(ans,calc(i));
    for(int i=(pos[r]-1)*block+1;i<=r;i++)  ans=max(ans,calc(i));
    for(int i=pos[l]+1;i<pos[r];i++)  ans=max(ans,find(i));
    return max(0ll,ans-calc(1));
}
void change(int x,int y)
{
    if(pos[x]==pos[y]) 
    {
        pushdown(pos[x]);
        swap(sum[x],sum[y]);
        reset(pos[x]);
        return; 
    }
    pushdown(pos[x]);pushdown(pos[y]);
    swap(sum[x],sum[y]);
    reset(pos[x]);reset(pos[y]);
}
int main()
{
    freopen("line.in","r",stdin);
    freopen("line.out","w",stdout);
    using namespace IStream;
    n=Get_Int();q=Get_Int();block=int(sqrt(n))+log(n)/log(2)+1;
    for(int i=1;i<=n;i++)
    {
        sum[i]=Get_Int();
        pos[i]=(i-1)/block+1;
    }
    if(n%block) m=n/block+1;
    else m=n/block;
    for(int i=1;i<=m;i++) reset(i);
    while(q--)
    {
        w=Get_Int(),x=Get_Int(),y=Get_Int();if(x>y) swap(x,y);
        if(w==1) printf("%lld\n",query(x,y));
        else if(w==3) z=Get_Int(),update(x,y,z);
        else change(x,y);
    }
    return 0;
}```