Problem C

發布時間: 2017年6月28日 11:38?? 最后更新: 2017年6月28日 16:38?? 時間限制: 1000ms?? 內存限制: 32M

描述

給定一個長度為n的序列a1,?a2, ...,?an, 其中ai∈[1,10]

給出q個操作, 操作分為兩種

對于形如1?x?y的操作, 將ax改為y, 滿足1≤x≤n,?1≤y≤10

對于形如2?x?y?z的操作, 輸出下標介于[x,y]之間的元素中, 值為z的元素個數, 滿足1≤x≤y≤n,?1≤z≤10

9×104≤n≤105,?9×104≤q≤105

輸入

第一行兩個整數n,?q, 意義如上所述。
接下來q行, 每行第一個數為opt, 如果opt=1, 后面緊跟兩個數, 意義如上所述; 如果opt=2, 后面緊跟三個數, 意義如上所述。

輸出

對于每個操作3, 輸出答案, 一行一個。

樣例輸入1?復制 8 3 3 1 4 1 5 9 2 6 2 1 8 2 1 2 2 2 1 8 2 樣例輸出1 1 2

非常簡單的一道題目，開10個樹狀數組。

bitree[z]含義分別是值為z的位置分布的樹狀數組。

當把數字a[x]變成y的時候，要做兩件事情

第一件：消除舊值的影響

add(a[x],x,-1);

第二件

a[x] = y

add(a[x],x,1)

增加對新的數的影響

查詢區間[x,y]等于z的數的個數時候

直接在z對應的樹狀數組里求部分和就OK了

是不是非常簡單

#include <cstdio> const int MAX = 1e5+7; int a[MAX]; int in[11][MAX]; int n,q; inline int lowbit(int x){return x&(-x); } void add(int id,int pos,int val){while(pos <= n){in[id][pos] += val;pos += lowbit(pos);} } int getsum(int id,int pos){int res = 0;while(pos){res += in[id][pos];pos -= lowbit(pos);}return res; } int main(){scanf("%d%d",&n,&q);for(int i = 1;i <= n;i++){scanf("%d",&a[i]);add(a[i],i,1);}while(q--){int opt;scanf("%d",&opt);if(opt == 1){int x,y;scanf("%d%d",&x,&y);add(a[x],x,-1);a[x] = y;add(a[x],x,1);}else {int x,y,z;scanf("%d%d%d",&x,&y,&z);printf("%d\n",getsum(z,y) - getsum(z,x-1));}}}

總結

以上是生活随笔為你收集整理的2017西安交大ACM小学期数据结构 [树状数组]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。