首页 > 代码库 > A Simple Problem with Integers

A Simple Problem with Integers

2024-07-13 12:59:21   218人阅读

Description

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4

Sample Output

455915

Hint

The sums may exceed the range of 32-bit integers.
 
/**********************线段树  编程上有难度，高级数据结构。树状数组能解决的，线段树一定能解决树状数组编程难度远比线段树低，多做线段树能提高自己的代码能力****************************/#include"iostream"#include"cstdio"#include"cstring"#include"algorithm"using namespace std;struct node{    int l,r;    long long sum;    long long inc;    node *pl,*pr;} ;node tree[200001];int cnt=0;int mid(node *p){    return (p->l+p->r)/2;}void buildtree(node *p,int l,int r){    p->l=l;    p->r=r;    p->sum=0;    p->inc=0;    if(l==r)        return ;    cnt++;    p->pl=tree+cnt;    cnt++;    p->pr=tree+cnt;    buildtree(p->pl,l,(l+r)/2);    buildtree(p->pr,(l+r)/2+1,r);}void insert(node *p,int i,int v){    if(p->l==i&&p->r==i)    {        p->sum=v;        return ;    }    p->sum+=v;    if(i<=(p->l+p->r)/2)        insert(p->pl,i,v);    else        insert(p->pr,i,v);}void add(node *p,int a,int b,long long c){    if(p->l==a&&p->r==b)    {        p->inc+=c;        return ;    }    p->sum+=c*(b-a+1);    if(b<=(p->l+p->r)/2)        add(p->pl,a,b,c);    else if(a>(p->l+p->r)/2)        add(p->pr,a,b,c);    else    {        add(p->pl,a,(p->l+p->r)/2,c);        add(p->pr,(p->l+p->r)/2+1,b,c);    }}long long querysum(node *p,int a,int b){    if(p->l==a&&p->r==b)        return p->sum+p->inc*(b-a+1);    p->sum+=(p->r-p->l+1)*p->inc;    add(p->pl,p->l,(p->l+p->r)/2,p->inc);    add(p->pr,(p->l+p->r)/2+1,p->r,p->inc);    p->inc=0;    if(b<=(p->l+p->r)/2)        return querysum(p->pl,a,b);    else if(a>(p->l+p->r)/2)        return querysum(p->pr,a,b);    else        return querysum(p->pl,a,(p->l+p->r)/2)+querysum(p->pr,(p->l+p->r)/2+1,b);}int main(){    int n,q,a,b,c;    int i,j,k;    char cmd[10];    //cin>>n>>q;    scanf("%d%d",&n,&q);    cnt=0;    buildtree(tree,1,n);    for(i=1;i<=n;i++)    {        //cin>>a;        scanf("%d",&a);        insert(tree,i,a);    }    for(i=0;i<q;i++)    {        //cin>>cmd;        scanf("%s",cmd);        if(cmd[0]==‘C‘)        {            //cin>>a>>b>>c;            scanf("%d%d%d",&a,&b,&c);            add(tree,a,b,c);        }        else        {            //cin>>a>>b;            scanf("%d%d",&a,&b);            cout<<querysum(tree,a,b)<<endl;        }    }    return 0;}

 


联系
我们