首页 > 代码库 > cogs 358. [SDOI2012] 体育课

cogs 358. [SDOI2012] 体育课

★   输入文件:sdoi12_line.in   输出文件:sdoi12_line.out   简单对比

时间限制:10 s   内存限制:128 MB

体育课(line)问题描述:

又是一节体育课的时间了,有n个同学排成了一排。他们都很讨厌排在第一个位置的同学,于是后面的同学中比第一个高的都会产生一个高兴值,这个高兴值等于他的身高减去第一个同学的身高。当然比第一个同学矮的同学产生兴奋值为0。

现在体育老师来了,他拥有神奇的魔法,现在他能做如下的三件事:

1:询问某段区间高兴值最大的那个是多少。

2:把某两个同学交换一下位置。

3:选取一段区间的人,把第一个人身高加上t,第二个加上2t,第三个加上3t以此类推。

但是体育老师不会数数,于是他找到你了,对于每一个询问,他要你帮他求出那个值。

输入说明:

第一行两个整数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)

输出说明:

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

样例输入:

6 8

109 827 100 530 10 826

3 1 6 1

2 2 6

1 2 4

1 2 3

2 2 6

1 2 6

1 2 5

样例输出:

431

0

817

431

719

数据范围:

有20%的数据:n,m<=5000

另有10%的数据:没有第三种操作.

另有20%的数据: 没有第二种操作

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

 

UPD:2017.7.7 by Mike

我猜样例是错的,第一个测试点发出来当样例算了

sdoi12_line.in

 

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

sdoi12_line.out

 

0

4

6

9

13

 

看到1星的山东省选题,本想写一写,然而连暴力都写不出来:

#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int N=100010;int Height[N],diff[N];int how,n,m,l,r,t;inline int read(){	int x=0;int f=1;char c=getchar();	while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}	while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar();	return x*f;  }inline void add(int l,int r,int t){	int js=0;	if(l==1)	{		for(int i=r+1;i<=n;i++)			diff[i]-=t;		for(int i=2;i<=r;i++)			diff[i]+=(++js)*t;	}		else		for(int i=l;i<=r;i++)			diff[i]+=(++js)*t;	return ;}inline int Find_max(int l,int r){	int answer=-1;	for(int i=l;i<=r;i++)		answer=max(answer,diff[i]);	return answer;}int main(){	n=read();	m=read();	for(int i=1; i<=n; i++)	{		Height[i]=read();		diff[i]=Height[i]-Height[1];		diff[i]=max(diff[i],0);	}			for(int i=1; i<=m; i++)	{		how=read();		switch(how)		{			case 1:			{				l=read(),r=read();				printf("%d\n",Find_max(l,r));				break;			}			case 2:			{				l=read(),r=read();				swap(diff[l],diff[r]);				break;			}			case 3:			{				l=read(),r=read(),t=read();				add(l,r,t);				break;			}		}	}	return 0;}/*10 710 9 8 7 6 5 4 3 2 11 4 73 2 4 31 2 31 3 62 1 101 8 101 2 3046913*/	

看到ac代码,hehehe

#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <cmath>#include <queue>#include <set>#include <cassert> using namespace std; typedef long long LL; void read(LL &x) {    char c;bool flag = 0;    while((c=getchar())<‘0‘||c>‘9‘) flag |= (c==‘-‘);    x=c-‘0‘;while((c=getchar())>=‘0‘&&c<=‘9‘) x = x*10+c-‘0‘;    flag?x=-x:x;} void read(int &x) {    char c;bool flag = 0;    while((c=getchar())<‘0‘||c>‘9‘) flag |= (c==‘-‘);    x=c-‘0‘;while((c=getchar())>=‘0‘&&c<=‘9‘) x = x*10+c-‘0‘;    flag?x=-x:x;} const LL inf = ~0u>>2;void FRE(); void upval(LL &a,const LL &b) {if(a<b) a=b;} #define MAXX 101000#define N 600int n,m;LL h[MAXX],bsf[N];int bsiz,bl[N],br[N],bk[MAXX];LL lazy1[N],lazy2[N];struct pii{LL h,pos;pii(LL h=0,LL pos=0):h(h),pos(pos){}} st[N][N];int top[N]; void reset(int bk) {	bsf[bk] = inf; top[bk] = 0;	for (LL i = bl[bk]; i <= br[bk]; i++) {		while(top[bk] && st[bk][top[bk]].h <= h[i]) top[bk]--;		st[bk][++top[bk]] = pii(h[i],i);				}	for (LL i = 2; i <= top[bk]; i++)	  bsf[bk] = min(bsf[bk], 	     ((st[bk][1].h-st[bk][i].h)/(st[bk][i].pos-st[bk][1].pos)));} void push_down(int bk) {	if(!lazy1[bk] && !lazy2[bk]) return;	for (LL i = bl[bk]; i <= br[bk]; i++)	 h[i] += lazy1[bk]+i*lazy2[bk];	lazy1[bk] = lazy2[bk] = 0;} void Swap(int x,int y) {	push_down(bk[x]); push_down(bk[y]);	swap(h[x],h[y]);	reset(bk[x]); reset(bk[y]);} LL Max(int x,int y) {	int li = min(br[bk[x]],y); LL mx = 0;	push_down(bk[x]);	for (int i = x; i <= li; i++) upval(mx,h[i]);	reset(bk[x]);	for (int i = bk[x]+1; i < bk[y]; i++) {	  	if(lazy2[i] >= bsf[i] && lazy2[i]) {			push_down(i);			reset(i);		}		upval(mx,st[i][1].h+lazy1[i]+lazy2[i]*st[i][1].pos);	}	if(bk[x] != bk[y]) {		push_down(bk[y]);		for (int i = bl[bk[y]]; i <= y; i++) upval(mx,h[i]);		reset(bk[y]);	}    mx -= h[1]+lazy1[bk[1]]+lazy2[bk[1]];    return mx>0 ? mx : 0;} void Add(int x,int y,LL t) {	int li = min(br[bk[x]],y); LL L = x-1;	push_down(bk[x]);	for (int i = x; i <= li; i++) h[i] += (i-L)*t;	reset(bk[x]);	for (int i = bk[x]+1; i < bk[y]; i++) 		lazy1[i] += -L*t,lazy2[i] += t;	if(bk[x] != bk[y]) {		push_down(bk[y]);		for (int i = bl[bk[y]]; i <= y; i++) h[i] += (i-L)*t;		reset(bk[y]);	}} int main() {	read(n); read(m);	bsiz = sqrt(n+0.5);    for (int i = 1; i <= n; i++) {       read(h[i]);       bk[i] = i/bsiz+1;       if(!bl[bk[i]]) bl[bk[i]] = i;       br[bk[i]] = i;	} 	for (int i = 1; i <= bk[n]; i++) reset(i);	for (int i = 1,tp,x,y,t; i <= m; i++) {		read(tp); read(x); read(y);		if(tp == 1) printf("%lld\n",Max(x,y));		else if(tp == 2) Swap(x,y);		else read(t),Add(x,y,t);	}	return 0;}

  

cogs 358. [SDOI2012] 体育课