P1438 无聊的数列

P1438 无聊的数列

链接

分析:

  等差数列可加,首项相加,公差相加。

代码:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = 1e5 + ;
int A[N << ], D[N << ], ori[N]; void pushdown(int rt,int l,int r) {
int mid = (l + r) >> ;
A[rt << ] += A[rt];
A[rt << | ] += A[rt] + (mid - l + ) * D[rt];
D[rt << ] += D[rt];
D[rt << | ] += D[rt];
A[rt] = D[rt] = ;
}
void update(int l,int r,int rt,int L,int R,int a,int d) {
if (L <= l && r <= R) {
A[rt] += a + (l - L) * d; D[rt] += d; return ;
}
if (A[rt] || D[rt]) pushdown(rt, l, r);
int mid = (l + r) >> ;
if (L <= mid) update(l, mid, rt << , L, R, a, d);
if (R > mid) update(mid + , r, rt << | , L, R, a, d);
}
int query(int l,int r,int rt,int p) {
if (l == r) return ori[l] + A[rt];
if (A[rt] || D[rt]) pushdown(rt, l, r);
int mid = (l + r) >> ;
if (p <= mid) return query(l, mid, rt << , p);
else return query(mid + , r, rt << | , p);
}
int main() {
int n = read(), m = read();
for (int i = ; i <= n; ++i) ori[i] = read();
while (m --) {
if (read() == ) {
int l = read(), r = read(), a = read(), d = read();
update(, n, , l, r, a, d);
}
else {
int x = read();
cout << query(, n, , x) << "\n";
}
}
return ;
}
上一篇:LoibreOJ 2042. 「CQOI2016」不同的最小割 最小割树 Gomory-Hu tree


下一篇:自学Linux Shell3.2-切换目录命令cd