题解：P2496 [SDOI2012] 体育课

· · 题解

思路

题目6s ，就算暴力枚举也可以过 。

没看到题的点这里看 题目 。

暴力枚举方法最坏情况 O(n * n) 。

但重点不在这 ， 暴力枚举代码被同学抢先了（悲） 。

这里讲分块

首先建块，代码如下 。

void build(long long x) {
    long long maxv=a[(x-1)*mid+1];
    for(long long i=(x-1)*mid+2;i<=min(x*mid,n);i++) maxv=max(maxv,a[i]);
    maxn[x]=maxv;//本块的最大
}

另一部分 。 

for(long long i=1;i<=num;i++) build(i);//遍历每一块的最大 。

对于第一种操作 ，只需要判断中间整块大小加上散块大小 ，但要开long long ，要不然会WA ，让后记得如果高兴值小于 0 输出 0 （ 不要输错了 ） 。

代码如下 。

scanf("%lld%lld",&l,&r);
            long long maxv=0;
            for(long long i=(l-1)/mid+1+1;i<(r-1)/mid+1;i++) maxv=max(maxv,maxn[i]);//遍历中间整块块。
            for(long long i=l;i<=min((l-1)/mid+1*mid,r);i++) maxv=max(maxv,a[i]);//遍历左散块。
            if((l-1)/mid+1!=(r-1)/mid+1) for(long long i=((l-1)/mid)*mid+1;i<=r;i++) maxv=max(maxv,a[i]);//遍历右散块。
            if(maxv-a[1]>0) printf("%lld\n",maxv-a[1]);
            else printf("%d\n",0);

对于第二种操作 ， 只需要调换两个数 ， 让后重新排列两块 ， 其实可以判断一下减少时间复杂度 。

代码如下 。

scanf("%lld%lld",&l,&r);
            if(l==r) continue;
            swap(a[l],a[r]);
            build((l-1)/mid+1);
            if((l-1)/mid+1!=(r-1)/mid+1) build((r-1)/mid+1);

而对于第三种操作 ，只需要不断相加 ，让后重新排列受影响块即可 ，一下为最简单版 ，如果想快还是用if 。

scanf("%lld%lld%lld",&l,&r,&x);
            for(long long i=l;i<=r;i++) a[i]+=x*(i-l+1);
            for(long long i=(l-1)/mid+1;i<=(r-1)/mid+1;i++) build(i);

我算了一下时间复杂度 ，比暴力枚举久 ，于是我拿我做喜欢的暴力枚举过来 。

暴力枚举出奇迹 。

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100005],e,f,g,h; 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%lld",&e);
        if(e==1){
            scanf("%lld%lld",&f,&g);
            long long maxx=0;
            for(int j=f;j<=g;j++){
                if(a[j]-a[1]>maxx) maxx=a[j]-a[1];
            }
            printf("%lld\n",maxx);
        }
        else if(e==2){
            scanf("%lld%lld",&f,&g);
            swap(a[f],a[g]);
        }
        else{
            scanf("%lld%lld%lld",&f,&g,&h);
            for(int j=f;j<=g;j++){
                a[j]+=h*(j-f+1);
            }
        }
    }
    return 0;
}