首页 > 代码库 > POJ 3468 A Simple Problem with Integers
POJ 3468 A Simple Problem with Integers
不得不说,线段树学的太渣了,找了一份大神的代码贴上,以后仔细研读一下。
因为找不到出处,无法注明转载链接,请谅解。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 #define lson l , m , rt << 1 6 #define rson m + 1 , r , rt << 1 | 1 7 #define LL long long 8 const int maxn = 111111; 9 LL add[maxn<<2];10 LL sum[maxn<<2];11 void PushUp(int rt) {12 sum[rt] = sum[rt<<1] + sum[rt<<1|1];13 }14 void PushDown(int rt,int m) {15 if (add[rt]) {16 add[rt<<1] += add[rt];17 add[rt<<1|1] += add[rt];18 sum[rt<<1] += add[rt] * (m - (m >> 1));19 sum[rt<<1|1] += add[rt] * (m >> 1);20 add[rt] = 0;21 }22 }23 void build(int l,int r,int rt) {24 add[rt] = 0;25 if (l == r) {26 scanf("%lld",&sum[rt]);27 return ;28 }29 int m = (l + r) >> 1;30 build(lson);31 build(rson);32 PushUp(rt);33 }34 void update(int L,int R,int c,int l,int r,int rt) {35 if (L <= l && r <= R) {36 add[rt] += c;37 sum[rt] += (LL)c * (r - l + 1);38 return ;39 }40 PushDown(rt , r - l + 1);41 int m = (l + r) >> 1;42 if (L <= m) update(L , R , c , lson);43 if (m < R) update(L , R , c , rson);44 PushUp(rt);45 }46 LL query(int L,int R,int l,int r,int rt) {47 if (L <= l && r <= R) {48 return sum[rt];49 }50 PushDown(rt , r - l + 1);51 int m = (l + r) >> 1;52 LL ret = 0;53 if (L <= m) ret += query(L , R , lson);54 if (m < R) ret += query(L , R , rson);55 return ret;56 }57 int main() {58 int N , Q;59 //freopen("D:acm.txt","r",stdin);60 scanf("%d%d",&N,&Q);61 build(1 , N , 1);62 while (Q --) {63 char op[2];64 int a , b , c;65 scanf("%s",op);66 if (op[0] == ‘Q‘) {67 scanf("%d%d",&a,&b);68 printf("%lld\n",query(a , b , 1 , N , 1));69 } else {70 scanf("%d%d%d",&a,&b,&c);71 update(a , b , c , 1 , N , 1);72 }73 }74 return 0;75 }
POJ 3468 A Simple Problem with Integers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。