首页 > 代码库 > Codeforces 57B Martian Architecture 暴力||线段树
Codeforces 57B Martian Architecture 暴力||线段树
题目链接:点击打开链接
题意:n长的序列(初始全为0) m个操作 k个查询
下面m个操作[l,r] h 代表 a[l] +=h; a[l+1] += h+i; a[l+i] += h+i; l<=i<=r
然后问k个位置的和
因为k<=100 所以直接暴力也可以
-----------------------
如果k<=100000 也是可以做的
只需要给区间记录一个标记lazy,表示从左端点开始 l, l+1, l+i ··· l+r
而向下更新时, 左区间则直接更新, 右区间先给整个区间加上一个值tree[L(id)].r , 然后再传个标记下去,这样就能解决了。。
先来份暴力的。。
#include<iostream> #include<cstdio> #include<vector> #include<string.h> using namespace std; #define ll long long #define N 100005 #define mod 1000000007 ll l[N], r[N], hehe[N]; ll n, m, k; int main(){ ll i, j; while(cin>>n>>m>>k){ for(i = 1; i <= m; i++)scanf("%I64d %I64d %I64d", &l[i], &r[i], &hehe[i]); ll ans = 0; while(k--) { scanf("%I64d",&j); for(i = 1; i <= m; i++) { if(j < l[i] || j > r[i])continue; ans += hehe[i]; ans += j - l[i]; } } cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。