vp的时候没码出来。。

我们用set去维护, 每一块区域, 每块区域内的元素与下一个元素的差值刚好为ki,每次加值的时候我们暴力合并,

可以发现我们最多合并O(n)次。 然后写个线段树就没了。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); int n, q, val[N], k[N];
LL prefix[N];
set<PII> seg;
char op[]; LL a[N << ], add[N << ];
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
void push(int rt, int l, int mid, int r) {
if(add[rt]) {
a[rt << ] += add[rt] * (mid - l + );
a[rt << | ] += add[rt] * (r - mid);
add[rt << ] += add[rt];
add[rt << | ] += add[rt];
add[rt] = ;
}
}
void build(int l, int r, int rt) {
if(l == r) {
a[rt] = val[l];
return;
}
int mid = l + r >> ;
build(lson); build(rson);
a[rt] = a[rt << ] + a[rt << | ];
} void update(int L, int R, LL val, int l, int r, int rt) {
if(l >= L && r <= R) {
a[rt] += val * (r - l + );
add[rt] += val;
return;
}
int mid = l + r >> ;
push(rt, l, mid, r);
if(L <= mid) update(L, R, val, lson);
if(R > mid) update(L, R, val, rson);
a[rt] = a[rt << ] + a[rt << | ];
}
LL query(int L, int R, int l, int r, int rt) {
if(l >= L && r <= R) return a[rt];
int mid = l + r >> ;
push(rt, l, mid, r);
if(R <= mid) return query(L, R, lson);
else if(L > mid) return query(L, R, rson);
else return query(L, R, lson) + query(L, R, rson);
} int main() {
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &val[i]);
prefix[i] = prefix[i - ] + val[i];
}
for(int i = ; i < n; i++) scanf("%d", &k[i]);
for(int i = ; i <= n; i++) seg.insert(mk(i, i));
build(, n, );
scanf("%d", &q);
while(q--) {
scanf("%s", op);
if(op[] == '+') {
int x, v; scanf("%d%d", &x, &v);
auto sg = seg.upper_bound(mk(x, inf)); sg--;
int L = sg->fi, R = sg->se;
seg.erase(sg);
if(L <= x - ) seg.insert(mk(L, x - ));
update(x, R, v, , n, );
while(R < n) {
LL v1 = query(R, R, , n, );
LL v2 = query(R + , R + , , n, );
if(v1 + k[R] <= v2) break;
LL add = v1 + k[R] - v2;
auto sg = seg.lower_bound(mk(R + , R + ));
update(sg->fi, sg->se, add, , n, );
R = sg->se;
seg.erase(sg);
}
seg.insert(mk(x, R));
} else {
int L, R; scanf("%d%d", &L, &R);
printf("%lld\n", query(L, R, , n, ));
}
}
return ;
} /*
*/

最新文章

  1. csapp2e-chapter2-homework
  2. PDO和PDOStatement类常用方法
  3. Android平台下OpenCV移植与使用---基于C/C++
  4. div四个边框分别设置阴影样式
  5. Centos 6.5 下php5.6.2 的编译安装
  6. KnockoutJS 3.X API 第三章 计算监控属性(4)Pure computed observables
  7. 7z压缩文件时排除指定的文件
  8. mysql分表的三种方法
  9. 网游中的网络编程3:在UDP上建立虚拟连接
  10. 软件工程课程作业(三)--四则运算3(C++)
  11. [AngularJS + Webpack] Using Webpack for angularjs
  12. ZZ_INEERNAL每个栏位的含义
  13. Bootstrap免费模板站推荐
  14. php获取两个时间戳之间相隔多少天多少小时多少分多少秒
  15. 【windows】查询占用端口的程序——记一次解决webloigc启动失败的过程
  16. Eclipse工程 导入 Android Studio
  17. Eclipse中配置Solr源码
  18. CVE-2010-3971 CSS内存破坏漏洞分析
  19. MySQL order by的一个优化思路
  20. 网络传输层之TCP/UDP详解

热门文章

  1. json-lib转化java对象,是否转化为null的属性
  2. php OpenSSL 加解密
  3. Select查询命令
  4. 玩转 lua in Redis
  5. xampp 搭建好本地服务器以后手机无法访问
  6. 将Maven项目打包成可执行jar文件(引用第三方jar)
  7. mysql数据库之基本操作和存储引擎
  8. 网络扫描信息收集基于(Windows)
  9. queryset优化 。。。。。exists()与iterator()方法
  10. Python序列[1,2,3,4,5]