题目背景
无聊的 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).
输出格式:
对于每个询问, 输出答案, 每个答案占一行.
线段树维护差分数组即可
单点查询就是区间求和
没有判断 r!=n wa 了
- #include<bits/stdc++.h>
- using namespace std;
- //input by bxd
- #define rep(i,a,b) for(int i=(a);i<=(b);i++)
- #define repp(i,a,b) for(int i=(a);i>=(b);--i)
- #define RI(n) scanf("%d",&(n))
- #define RII(n,m) scanf("%d%d",&n,&m)
- #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
- #define RS(s) scanf("%s",s)
- #define ll long long
- #define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
- #define pb push_back
- #define inf 0x3f3f3f3f
- #define CLR(A,v) memset(A,v,sizeof A)
- #define lson l,m,pos<<1
- #define rson m+1,r,pos<<1|1
- typedef pair<int,int>pii;
- //////////////////////////////////
- const int N=1e5+5;
- ll t[N<<2],col[N<<2];
- int n,m,d,k,x,l,r;
- ll node[N],w[N];
- void up(int pos)
- {
- t[pos]=t[pos<<1]+t[pos<<1|1];
- }
- void build(int l,int r,int pos)
- {
- if(l==r){t[pos]=w[l];return ;}
- int m=(l+r)>>1;build(lson);build(rson);up(pos);
- }
- void down(int pos,int m)
- {
- if(col[pos])
- {
- t[pos<<1]+=(m-(m>>1))*col[pos];
- t[pos<<1|1]+=(m>>1)*col[pos];
- col[pos<<1]+=col[pos];col[pos<<1|1]+=col[pos];
- col[pos]=0;
- }
- }
- void upsum(int L,int R,int v,int l,int r,int pos)
- {
- if(L<=l&&r<=R){ col[pos]+=v;t[pos]+=(r-l+1)*v;return ; }
- int m=(l+r)>>1;down(pos,r-l+1);
- if(L<=m)upsum(L,R,v,lson);if(R>m)upsum(L,R,v,rson);up(pos);
- }
- ll qsum(int L,int R,int l,int r,int pos)
- {
- ll ans=0;if(L<=l&&r<=R)return t[pos];
- int m=(l+r)>>1;down(pos,r-l+1);
- if(L<=m)ans+=qsum(L,R,lson);if(R>m)ans+=qsum(L,R,rson);up(pos);return ans;
- }
- int main()
- {
- RII(n,m);
- rep(i,1,n)cin>>(node[i]);
- rep(i,1,n)w[i]=node[i]-node[i-1];
- build(1,n,1);
- while(m--)
- {
- RI(x);
- if(x==1)
- {
- RII(l,r);RII(k,d);
- upsum(l,l,k,1,n,1);
- if(l!=r)upsum(l+1,r,d,1,n,1);
- if(r!=n)upsum(r+1,r+1,-(k+(r-l)*d),1,n,1);
- }
- else
- {
- RI(l);
- printf("%lld\n",qsum(1,l,1,n,1));
- }
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3124035.html