題目鏈接：https://loj.ac/problem/10115

題目描述

原題來自：Vijos P1448

校門外有很多樹，學校決定在某個時刻在某一段種上一種樹，保證任一時刻不會出現兩段相同種類的樹，現有兩種操作：

• K=1，讀入l,r 表示在l? 到 r 之間種上一種樹，每次操作種的樹的種類都不同；
• K=2，讀入 l,r 表示詢問 l 到 r 之間有多少種樹。

注意：每個位置都可以重復種樹。

輸入格式

第一行??表示道路總長為 n，共有? m個操作；
接下來 m 行為 m 個操作。

輸出格式

對于每個 K=2 輸出一個答案。

樣例

樣例輸入

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

樣例輸出

1 2

?

解題思路:開始怎么想都不知道怎么維護不同段中樹的種類是否相同的情況，感覺這題有個思維技巧還是挺難想的，就是我們要開兩個數組，sum1分別維護左端點的數目，另一個數組sum2維護右端點的數目。這樣區間[l,r]的樹的種類的數目就是1-r中左端點的數目減去1-(l-1)中右端點的數目，即表示為sum1[r]-sum2[l-1]。

如圖假如我們第一次在區間a[2,6]種上一種樹，然后再在區間b[5,10]種上一種樹，這時我們要統計區間c[8,12]中樹的種類數目，我們就統計[1,12]中左端點的數目即 sum1[12]等于2，說明有兩種樹可能在給定區間內，然后我們再求區間[1,7]中右端點的數目即sum2[7-1]=1,表示有一種樹完全在給定區間左邊，并不是我們要求的，所以減去就好了，所以答案就為sum1[12]-sum2[7-1]了。

代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<algorithm> #include<queue> #define mod 1000000007 using namespace std; typedef long long ll; const int maxn=5e4+10; int n,m,k,l,r,sum1[maxn],sum2[maxn]; //sum1[i]表示的是區間[1,i]中左端點的數目,sum2[i]表示的是區間[1,i]右端點的數目； int lowbit(int x){return x&(-x);} void update1(int x,int val){ //更新左端點的數目 while(x<=maxn){sum1[x]+=val;x+=lowbit(x);} } void update2(int x,int val){ //更新右端點的數目 while(x<=maxn){sum2[x]+=val;x+=lowbit(x);} } int ask1(int x){ //查找區間[1,x]中左端點的數目 int res=0;while(x){res+=sum1[x];x-=lowbit(x);}return res; } int ask2(int x){ //查找區間[1,x]中右端點的數目 int res=0;while(x){res+=sum2[x];x-=lowbit(x);}return res; } int main(){cin>>n>>m;while(m--){cin>>k>>l>>r;if(k==1){update1(l,1); update2(r,1);}else{cout<<ask1(r)-ask2(l-1)<<endl;}}return 0; }

?

轉載于:https://www.cnblogs.com/zjl192628928/p/10630450.html

總結

以上是生活随笔為你收集整理的Loj 10115 「一本通 4.1 例 3」校门外的树 (树状数组)的全部內容，希望文章能夠幫你解決所遇到的問題。

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