序列操作

2019-11-06 06:09:59

字體：大中小

來源：轉載

供稿：網友

題目描述

給出一個N個元素的正整數序列，現在有兩種操作:

修改操作:給一段區間的每一個數加上一個正整數x查詢操作:查詢序列中當前第x個元素的值。

請寫一個程序實現這兩種操作。第一行，一個數N 第二行N個數，表示初始的序列，接下來一行一個數M，表示操作次數接下來M行，每行一個操作:

lrx表示把l到r的每一個數加上xx表示查詢第x個元素的值

輸入

第一行，一個數N 第二行N個數，表示初始的序列，接下來一行一個數M，表示操作次數接下來M行，每行一個操作:

lrx表示把l到r的每一個數加上xx表示查詢第x個元素的值

輸出

對于每一個查詢操作輸出一行結果

樣例輸入

5 1 1 1 1 1 4 1 2 3 2 2 3 1 1 5 3 2 5

樣例輸出

3 4

提示

數據范圍

N, M <= 100000，初始數列中每個元素不超過1000，修改操作中的x不超過1000

分析

個人覺得這點題有點像 HDU 1556 的“小飛鴿”。它和樹狀數組有一些不同，就是是區間求和，所以面對這一問題，我們也可以把它做成“小飛鴿”那道題的樣子。 “小飛鴿”那道題的意思是區間計算，而這道題只需要計算一個點，so。。。

初始化就不說了吧。我們先把初始的數據存起來，后面不用再處理的，或者update，否則很麻煩的，直接拿區間和加上即可。所以這道題的update就是針對一個區間的了。 update根據容斥原理，要讓[l,r]區間的值增加x，就先把前r個地方的值加上x，再把前l個地方的值減去x，就行了。O(∩_∩)O哈哈哈~ 讀入指令類型，如果是1，就區間更新值；如果是2，就先把樹狀數組的和求出來，再加上初始值即可。。。

源代碼

#include<cstdio>#define lowbit(a) a&-aint n,arr[100005],a[100005];void update(int i,int d){ while(i<=n){ arr[i]+=d; i+=lowbit(i); }}int getsum(int i){ int s=0; while(i){ s+=arr[i]; i-=lowbit(i); } return s;}int main(){ int m,x,l,r,o; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d",&o); if(o==1){ scanf("%d%d%d",&l,&r,&x); update(l,x); update(r+1,-x); } else{ scanf("%d",&x);