The main idea of the topic :

A sequence of , There are two operations :1. Modify the operating , Add... To a number in an interval c;2. Query operation , Query the sum of numbers in an interval .

Ideas :

Line tree naked problem , Interval modification 、 Interval query , Maintenance and plus , Because of disorder , There is no need to push the tag down , Just update the root node after the subtree is updated .

Code :

 #include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; long long sum[],mor[]; void up(int cur,int t)
{
sum[cur]=sum[cur<<]+sum[cur<<|]+t*mor[cur];
} void add(int L,int R,int l,int r,int x,int cur)
{
if (L>=l && R<=r)
{
mor[cur]+=x;
sum[cur]+=(R-L+)*x;
return;
}
int mid=L+R>>;
if (l<=mid) add(L,mid,l,r,x,cur<<);
if (r>mid) add(mid+,R,l,r,x,cur<<|);
up(cur,R-L+);
} long long ask(int L,int R,int l,int r,int cur)
{
if (L>=l && R<=r) return sum[cur];
int mid=L+R>>;
long long ans=mor[cur]*(r-l+);
if (l<=mid) ans+=ask(L,mid,l,min(mid,r),cur<<);
if (r>mid) ans+=ask(mid+,R,max(l,mid+),r,cur<<|);
return ans;
} int main()
{
int n,m,i,a,b,c;
scanf("%d%d",&n,&m);
for (i=;i<=n;i++) scanf("%d",&a),add(,n,i,i,a,);
for (i=;i<=m;i++)
{
char ch=getchar();
while (ch<'A' || ch>'Z') ch=getchar();
if (ch=='Q') scanf("%d%d",&a,&b),printf("%lld\n",ask(,n,a,b,));
else scanf("%d%d%d",&a,&b,&c),add(,n,a,b,c,);
}
return ;
}

BZOJ3212 Pku3468 A Simple Problem with Integers More related articles on the solution of the problem

  1. BZOJ-3212 Pku3468 A Simple Problem with Integers Bare line segment tree interval maintenance query

    3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec Memory Limit: 128 MB Submit: 1278 Sol ...

  2. bzoj3212 Pku3468 A Simple Problem with Integers Line segment tree

    3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 2046  So ...

  3. BZOJ3212: Pku3468 A Simple Problem with Integers( Line segment tree )

    3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 2530  So ...

  4. bzoj3212 pku3468 A Simple Problem with Integers

    A sequence of numbers with initial values . Interval plus . Interval search Use the line tree to water directly But there is no 1A, The main problem is too fast to see the scale of the results did not pay attention to the line segment tree to use longlong build How can the trough be so boring , I saw it wa Flustered , I thought I had to kneel on the line Open up ...

  5. 【 Block 】【 Line segment tree 】bzoj3212 Pku3468 A Simple Problem with Integers

    Introduction to line tree …… because poj The original code is inexplicable RE, So I wrote the block of interval modification …… It's just marking on the block , There's no upload or download or anything like that . #include<cstdio> #include<cmat ...

  6. 3212: Pku3468 A Simple Problem with Integers

    3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 1053  So ...

  7. bzoj 3212 Pku3468 A Simple Problem with Integers

    3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 128 MB Description You ...

  8. bzoj 3212 Pku3468 A Simple Problem with Integers Line segment tree basic operation

    Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 2173  Solved:  ...

  9. POJ3468:A Simple Problem with Integers—— Answer key

    http://poj.org/problem?id=3468 Implement a line tree , Can do interval modification and interval query and . Obvious board problem . #include<cstdio> #include<cma ...

Random recommendation

  1. The siege lion is on the way ( 3 )Linux( Twelve )--- Linux The directory and path of

    One . Relative path and absolute path : A. Absolute path : By root / The path to start writing , for example /usr/share/doc B. Relative paths : Not by the root / The path to start writing . Two . Operation related to directory : 1.cd: Directory switching cd ~ ...

  2. startUML Common combination fragments

    1.   Common combination fragments Fragment type name explain Opt Options Contains a sequence that may or may not occur .  The conditions under which the sequence occurs can be specified in criticality . Alt Choose Contains a list of fragments , These fragments contain alternative message sequences .  In any field ...

  3. PHP Closure (Closure) On

    Unknowingly find out PHP It has arrived 5.5 edition , And I've been using PHP5.2, Make me look like a young man coming out of a deep mountain , Earth and backwardness . I'm used to javascript After using closures in , All of a sudden PHP I'm interested in the closure of . So ...

  4. Organized Unity Export Android project using ANT Multi channel batch packaging APK

    Unity The exported Android project uses ant Multi channel batch packaging One : Set up JAVA environment variable do android The configuration of development is the foundation . win7 The configuration java environment variable , Here's the link http://www.cnbl ...

  5. About ASIHTTPRequest A continuous request , Concurrent continuous , The interval is very small, the crash problem

    In the constant refresh ASIHttpRequest When the network requests , Always after a few refreshes , Whole app Collapse . my app The use of ARC Pattern , Thought it could be automatically released to request Request . After groping , Still need to be in dealloc Function plus ...

  6. Windows Message programming ( Well written , There are causes and consequences )

    This article mainly includes the following contents : 1. Simple understanding Windows The news of 2. Through a simple Win32 Program understanding Windows news 3. Through a few Win32 Further understanding of program examples Windows news 4. Queued messages and non queued messages 5. ...

  7. 【7】 use Laravel5.1 Develop a simple blog system

    Statement : This tutorial refers to Jeffrey way stay laracasts.com Video tutorial on , thank Jeffrey way Wonderful tutorial for you , If there is any infringement in this course , Please let me know in time , Contact email wanglv93@gmail.c ...

  8. Build and test Redis Master / standby and cluster

    This article is just for self-study , It's not suitable to reprint . 1. Redis Active / standby cluster 1.1 Steps to build machine : HNA cloud virtual machine (2 nucleus 4GB Memory ), Use Centos 7.2 64bit operating system ,IP Namely  192.168.10 ...

  9. Socket Layer implementation series — accept() The implementation of the ( Two )

    The main analysis of this paper accept() Blocking, waiting and waking up . Kernel version :3.6 Author:zhangskd @ csdn blog Waiting in line (1)socket Waiting queue /* * @sk_wq: sock w ...

  10. [ Re posting ]Windows Kernel description

    source :https://zhidao.baidu.com/question/398191459.html My understanding . windows Kernel files for Is in c:\windows\system32 Below directory ...