P1438 无聊的数列
题目背景
无聊的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）。
题解：
差分，线段树
const int maxn = 1e6+11;
int sum[maxn],lazy[maxn];void pushup(int i)
{sum[i] = sum[i<<1]+sum[i<<1|1];
}void pushdown(int i,int l,int r)
{int mid = (l+r)>>1;if(!lazy[i])return;sum[i<<1] += (mid-l+1)*lazy[i];sum[i<<1|1] += (r - mid)*lazy[i];lazy[i<<1] += lazy[i];lazy[i<<1|1] += lazy[i];lazy[i] = 0;
}void update(int i,int l,int r,int ql,int qr,int v)
{if(ql <= l && qr >= r){sum[i] += v*(r-l+1);lazy[i] += v;return; }pushdown(i,l,r);int mid = (l+r)>>1;if(ql<=mid)update(i<<1,l,mid,ql,qr,v);if(qr>mid)update(i<<1|1,mid+1,r,ql,qr,v);pushup(i);
}int query(int i,int l,int r,int ql,int qr)
{if(ql<=l && qr>=r)return sum[i];pushdown(i,l,r);int mid = (l+r)>>1;int ans = 0;if(ql<=mid)ans+=query(i<<1,l,mid,ql,qr);if(qr>mid)ans+=query(i<<1|1,mid+1,r,ql,qr);return ans;
}int a[maxn];
int main()
{int n,m;cin>>n>>m;rep(i,1,n+1)scanf("%d",a+i);rep(i,1,m+1){ int op,l;scanf("%d%d",&op,&l);if(op == 1){int r,k,d;scanf("%d%d%d",&r,&k,&d);update(1,1,n,l,l,k);if(r!=n)update(1,1,n,r+1,r+1,-(k+(r-l)*d));if(r>l)update(1,1,n,l+1,r,d); }elseprintf("%d\n",a[l]+query(1,1,n,1,l));}
}
树状数组：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100010
using namespace std;
int a[MAXN][2],p[MAXN],n;
int lowbit(int x)
{return x&(-x);
}
void add(int x,int k,int d)
{while(x<=n){a[x][0]+=k;a[x][1]+=d;k+=d*lowbit(x);x+=lowbit(x);}
}
int sum(int x)
{int ans=0,pos=x;while(pos){ans+=a[pos][0]+(x-pos)*a[pos][1];pos-=lowbit(pos);}return ans;
}
int main()
{int x,i,l,r,k,d,s,m;scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&p[i]);for(i=1;i<=m;i++){scanf("%d",&s);if(s==1){scanf("%d%d%d%d",&l,&r,&k,&d);add(l,k,d);add(r+1,-k-(r-l+1)*d,-d);}else{scanf("%d",&x);printf("%d\n",p[x]+sum(x));}}return 0;
}