洛谷P2068 统计和题解
题目描述
给定一个长度为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<button class="copy-btn lfe-form-sz-middle" data-v-89a1e792="" data-v-f3e1ca6a="" type="button">复制</button>
5 4 x 3 8 y 1 3 x 4 9 y 3 4
输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-89a1e792="" data-v-f3e1ca6a="" type="button">复制</button>
8 17
解析：
模板题目
树状数组1模板
支持单调修改，区间查询
上代码吧
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<string> 6 #include<algorithm> 7 #include<iomanip> 8 #include<cstdlib> 9 #include<queue> 10 #include<set> 11 #include<map> 12 #include<stack> 13 #include<vector> 14 #define re register 15 #define Max 210000 16 #define D double 17 #define gc getchar 18 inline int read() 19 { 20 int a=0;int f=0;char p=gc(); 21 while(!isdigit(p)){f|=p=='-';p=gc();} 22 while(isdigit(p)){a=a*10+p-'0';p=gc();} 23 return f?-a:a; 24 } 25 int c[Max]={0},n,m;char ch; 26 int lowbit(int x) 27 { 28 return x&-x; 29 } 30 void add(int x,int k) 31 { 32 for(;x<=m;x+=lowbit(x)) c[x]+=k; 33 } 34 int query(int x) 35 { 36 int ans=0; 37 for(;x;x-=lowbit(x)) ans+=c[x]; 38 return ans; 39 } 40 int main() 41 { 42 m=read();n=read();int l,r; 43 for(re int i = 1 ; i <= n ; ++ i) { 44 std::cin>>ch;l=read(),r=read(); 45 if(ch=='x') add(l,r); 46 if(ch=='y') printf("%d\n",query(r)-query(l-1)); 47 } 48 return 0; 49 }
投递小米集团等公司10个岗位 >
