首页 > 代码库 > 洛谷 P2068 统计和

洛谷 P2068 统计和

2024-09-08 00:52:45   215人阅读

题目描述

给定一个长度为n（n<=100000），初始值都为0的序列，x(x<=10000)次的修改某些位置上的数字，每次加上一个数，然后提出y (y<=10000)个问题，求每段区间的和。时间限制1秒。

输入输出格式

输入格式：

 

第一行1个数，表示序列的长度n

第二行1个数，表示操作的次数w

后面依次是w行，分别表示加入和询问操作

其中，加入用x表示，询问用y表示

x的格式为"x a b" 表示在序列a的位置加上b

y的格式为"y a b" 表示询问a到b区间的加和

 

输出格式：

 

每行一个数，分别是每次询问的结果

 

输入输出样例

输入样例#1：
54x 3 8y 1 3x 4 9y 3 4
输出样例#1：
817


线段树版题
区间求和 
单点修改 
屠龙宝刀点击就送
#include <iostream>#include <cstdio>using namespace std;#define Max 200000struct node{    int l,r,dis;}tree[Max*4];int t=0,n,w;char cz;void up(int k){    tree[k].dis=tree[k<<1].dis+tree[k<<1|1].dis;}void build(int l,int r,int k){    tree[k].l=l;tree[k].r=r;    if(l==r)    {        tree[k].dis=0;        return;    }    int mid=(l+r)>>1;    build(l,mid,k<<1);    build(mid+1,r,k<<1|1);    up(k);}void add(int to,int v,int k){    if(tree[k].l==tree[k].r)    {        tree[k].dis+=v;        return;    }    int mid=(tree[k].l+tree[k].r)>>1;    if(to<=mid) add(to,v,k<<1);    else add(to,v,k<<1|1);    up(k);}int ans=0;void query(int u,int v,int k){    if(tree[k].l==u&&tree[k].r==v)    {        ans+=tree[k].dis;        return ;    }    int mid=(tree[k].l+tree[k].r)>>1;    if(mid>=v) query(u,v,k<<1);    else if(mid<u) query(u,v,k<<1|1);    else query(u,mid,k<<1),query(mid+1,v,k<<1|1);}int main(){    scanf("%d",&n);    build(1,n,1);    scanf("%d",&w);    int u,v;    while(w--)    {        cin>>cz;        scanf("%d%d",&u,&v);        if(cz==‘x‘)         add(u,v,1);        else if(cz==‘y‘)         {            ans=0;            query(u,v,1);            printf("%d\n",ans);        }    }    return 0;}

 

洛谷 P2068 统计和


联系
我们