博客

题目背景

无聊的YYB总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的YYB想出了一道无聊的题：无聊的数列。。。（K峰：这题不是傻X题吗）

题目描述

维护一个数列{a[i]}，支持两种操作：

1、1 L R K D：给出一个长度等于R-L+1的等差数列，首项为K，公差为D，并将它对应加到a[L]~a[R]的每一个数上。即：令a[L]=a[L]+K，a[L+1]=a[L+1]+K+D，

a[L+2]=a[L+2]+K+2D……a[R]=a[R]+K+(R-L)D。

2、2 P：询问序列的第P个数的值a[P]。

输入输出格式

输入格式：

第一行两个整数数n，m，表示数列长度和操作个数。

第二行n个整数，第i个数表示a[i]（i=1,2,3…,n）。

接下来的m行，表示m个操作，有两种形式：

1 L R K D

2 P 字母意义见描述（L≤R）。

输出格式：

对于每个询问，输出答案，每个答案占一行。

输入输出样例

5 2
1 2 3 4 5
1 2 4 1 2
2 3

6

说明

数据规模：

0≤n，m≤100000

|a[i]|，|K|，|D|≤200

Hint：

有没有巧妙的做法？

解法一：线段树维护差分操作。

#include<iostream>
#define f(i,l,r) for(i=(l);i<=(r);i++)
using namespace std;
const int MAXN=100005;
int a[MAXN];
int n,m;
int tree[MAXN<<2],lazy[MAXN<<2];
inline void pushup(int x)
{
	tree[x]=tree[x<<1]+tree[x<<1|1];
}
inline void pushdown(int x,int l,int r)
{
	int mid=l+r>>1;
	tree[x<<1]+=(mid-l+1)*lazy[x];
	lazy[x<<1]+=lazy[x];
	tree[x<<1|1]+=(r-mid)*lazy[x];
	lazy[x<<1|1]+=lazy[x];
	lazy[x]=0;
}
inline void change(int x,int l,int r,int sj,int tj,int d)
{
	if(sj<=l&&tj>=r){
		tree[x]+=(r-l+1)*d;
		lazy[x]+=d;
		return;
	}
//	cout<<l<<' '<<r<<"GG"<<endl; 
	if(lazy[x]) pushdown(x,l,r);
	int mid=l+r>>1;
	if(mid>=sj) change(x<<1,l,mid,sj,tj,d);
	if(mid+1<=tj) change(x<<1|1,mid+1,r,sj,tj,d);
	pushup(x);
}
inline int query(int x,int l,int r,int sj,int tj)
{
	int res=0;
	if(sj<=l&&tj>=r){
		return tree[x];
	}
	if(lazy[x]) pushdown(x,l,r);
	int mid=l+r>>1;
	if(mid>=sj) res+=query(x<<1,l,mid,sj,tj);
	if(mid+1<=tj) res+=query(x<<1|1,mid+1,r,sj,tj);
	pushup(x);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	int i,j,flag,l,r,k,d,p;
	cin>>n>>m;
	f(i,1,n){
		cin>>a[i];
	}
	f(i,1,m){
		cin>>flag;
		if(flag==1){
			cin>>l>>r>>k>>d;
			change(1,1,n,l,l,k);
			if(l+1<=r) change(1,1,n,l+1,r,d);
			if(r+1<=n) change(1,1,n,r+1,r+1,-k-(r-l)*d);
		}
		else{
			cin>>p;
			cout<<a[p]+query(1,1,n,1,p)<<endl;
		}
	}
	return 0;
}

解法二：分块。

#include<iostream>
#include<cmath>
#define f(i,l,r) for(i=(l);i<=(r);i++)
using namespace std;
const int MAXN=100005;
int n,m,a[MAXN],Tim,cnt,bel[MAXN];
int ll[MAXN],rr[MAXN],S[MAXN],D[MAXN];
inline void add(int l,int r,int k,int d)
{
	int i;
	if(bel[l]==bel[r]){
		f(i,l,r){
			a[i]+=k+(i-l)*d;
		}
	}
	else{
		int L=rr[bel[l]],R=ll[bel[r]];
		f(i,l,L){
			a[i]+=k+(i-l)*d;
		}
		f(i,R,r){
			a[i]+=k+(i-l)*d;
		}
		f(i,bel[l]+1,bel[r]-1){
			S[i]+=k+(ll[i]-l)*d;
			D[i]+=d;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	int i,j,flag,l,r,k,d;
	cin>>n>>m;
	f(i,1,n) cin>>a[i];
	Tim=sqrt(n);
	cnt=n/Tim;
	if(n%Tim) cnt++;
	f(i,1,n){
		bel[i]=(i-1)/Tim+1; 
	}
	f(i,1,cnt){
		ll[i]=(i-1)*Tim+1;
		rr[i]=i*Tim;
	}
	rr[cnt]=n;
	f(i,1,m){
		cin>>flag;
		if(flag==1){
			cin>>l>>r>>k>>d;
			add(l,r,k,d);
		}
		else{
			cin>>l;
			cout<<a[l]+S[bel[l]]+D[bel[l]]*(l-ll[bel[l]])<<endl;
		}
	}
	return 0;
}