思路

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

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

暴力枚举方法最坏情况

O(n * n)

。

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

这里讲分块

首先建块，代码如下。

CPP

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;//本块的最大
}

另一部分。

CPP

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

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

代码如下。

CPP

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);

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

代码如下。

CPP

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 。

CPP

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);

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

暴力枚举出奇迹。

CPP

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

题解：P2496 [SDOI2012] 体育课

文章操作

思路

这里讲分块

暴力枚举出奇迹。

相关推荐

评论

题解：P2496 [SDOI2012] 体育课

文章操作

思路

这里讲分块

暴力枚举出奇迹 。

相关推荐

评论

暴力枚举出奇迹。