本文主要是介绍树状数组经典例题:楼兰图腾+一个简单的整数问题+一个简单的证书问题2+谜一样的牛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
一、楼兰图腾
二、一个简单的整数问题
三、一个简单的整数问题2
四、谜一样的牛
一、楼兰图腾
题目描述:
在完成了分配任务之后,西部 314 来到了楼兰古城的西部。
相传很久以前这片土地上(比楼兰古城还早)生活着两个部落,一个部落崇拜尖刀(V),一个部落崇拜铁锹(∧),他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。
西部 314 在楼兰古城的下面发现了一幅巨大的壁画,壁画上被标记出了 n 个点,经测量发现这 n 个点的水平位置和竖直位置是两两不同的。
西部 314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关,因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn),其中 y1∼yn 是 1 到 n 的一个排列。
西部 314 打算研究这幅壁画中包含着多少个图腾。
如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n 且 yi>yj,yj<yk,则称这三个点构成 V 图腾;
如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n 且 yi<yj,yj>yk,则称这三个点构成 ∧ 图腾;
西部 314 想知道,这 n 个点中两个部落图腾的数目。
因此,你需要编写一个程序来求出 V 的个数和 ∧ 的个数。
输入格式:
第一行一个数 n。第二行是 n 个数,分别代表 y1,y2,…,yn。
输出格式:
两个数,中间用空格隔开,依次为 V 的个数和 ∧ 的个数。数据范围
对于所有数据,n≤200000,且输出答案不会超过 int64。
y1∼yn 是 1 到 n 的一个排列。输入样例:
5 1 5 3 2 4
输出样例:
3 4
#include<iostream>
using namespace std;
const int N=2e5+5;
typedef long long LL;
LL a[N],res1,res2,tr[N],n;
int lowbits(int x)
{return -x&x;
}
void add(int x,int c)
{for(;x<=n;x+=lowbits(x)) tr[x]+=c;
}
int ask(int x)
{LL res=0;for(;x;x-=lowbits(x)) res+=tr[x];return res;
}
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){int y=a[i];int t1=ask(y-1),t2=i-1-t1;res2+=t1*(a[i]-1-t1);res1+=t2*(n-a[i]-t2);add(y,1);}cout<<res1<<' '<<res2;
}
二、一个简单的整数问题
题目描述:
给定长度为N的数列A,然后输入M行操作指令。
第一类指令形如“C l r d”,表示把数列中第l~r个数都加d。
第二类指令形如“Q X”,表示询问数列中第x个数的值。
对于每个询问,输出一个整数表示答案。
输入格式:
第一行包含两个整数N和M。第二行包含N个整数A[i]。
接下来M行表示M条指令,每条指令的格式如题目描述所示。
输出格式:
对于每个询问,输出一个整数表示答案。每个答案占一行。
数 据 范 围 1 ≤ N , M ≤ 10^5 , ∣ d ∣ ≤ 10000 , ∣ A [ i ] ∣ ≤ 1000000000 。
输入样例:
10 5 1 2 3 4 5 6 7 8 9 10 Q 4 Q 1 Q 2 C 1 6 3 Q 2
输出样例:
4 1 2 5
#include<iostream>
using namespace std;
const int N=1e5+5;
typedef long long LL;
LL a[N],tr[N],n,m;
int lowbits(int x)
{return -x&x;
}
void add(int x,int c)
{for(;x<=n;x+=lowbits(x)) tr[x]+=c;
}
LL ask(int x)
{LL res=0;for(;x;x-=lowbits(x)) res+=tr[x];return res;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i],add(i,a[i]-a[i-1]);for(int i=1;i<=m;i++){char ch;cin>>ch;int x,y,d;cin>>x;if(ch=='C'){cin>>y>>d;add(x,d),add(y+1,-d);}else{cout<<ask(x)<<endl;}}
}
三、一个简单的整数问题2
题目描述:
给定一个长度为N的数列A,以及M条指令,每条指令可能是以下两种之一:
1、“C l r d”,表示把 A[l],A[l+1],…,A[r] 都加上 d。
2、“Q l r”,表示询问 数列中第 l~r 个数的和。
对于每个询问,输出一个整数表示答案。输入格式:
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行表示M条指令,每条指令的格式如题目描述所示。输出格式:
对于每个询问,输出一个整数表示答案。
每个答案占一行。数据范围:
1≤N,M≤105,
|d|≤10000,
|A[i]|≤1000000000输入样例:
10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4
输出样例:
4 55 9 15
#include<iostream>
using namespace std;
const int N=1e5+5;
typedef long long LL;
LL a[N],tr[N],tri[N],n,m;
int lowbits(int x)
{return -x&x;
}
void add(LL b[],LL x,LL c)
{for(;x<=n;x+=lowbits(x)) b[x]+=c;
}
LL ask(LL b[],LL x)
{LL res=0;for(;x;x-=lowbits(x)) res+=b[x];return res;
}
LL prefix_sum(LL x)
{return ask(tr,x)*(x+1)-ask(tri,x);
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){LL b=a[i]-a[i-1];add(tr,i,b),add(tri,i,i*b);}for(int i=1;i<=m;i++){char ch;int l,r;cin>>ch>>l>>r;if(ch=='C'){LL d;cin>>d;add(tr,l,d),add(tr,r+1,-d);add(tri,l,l*d),add(tri,r+1,(r+1)*-d);}else{cout<<prefix_sum(r)-prefix_sum(l-1)<<endl;}}
}
四、谜一样的牛
题目描述:
有n头奶牛,已知它们的身高为 1~n 且各不相同,但不知道每头奶牛的具体身高。
现在这n头奶牛站成一列,已知第i头牛前面有Ai头牛比它低,求每头奶牛的身高。
输入格式:
第1行:输入整数n。第2…n行:每行输入一个整数Ai,第i行表示第i头牛前面有Ai头牛比它低。
(注意:因为第1头牛前面没有牛,所以并没有将它列出)输出格式
输出包含n行,每行输出一个整数表示牛的身高。第i行输出第i头牛的身高。
数据范围:
1≤n≤10^5。输入样例:
5 1 2 1 0
输出样例:
2 4 5 3 1
#include<iostream>
using namespace std;
const int N=1e5+5;
int h[N],a[N],n,tr[N];
int lowbit(int x)
{return -x&x;
}
void add(int x,int c)
{for(;x<=n;x+=lowbit(x)) tr[x]+=c;
}
int ask(int x)
{int res=0;for(;x;x-=lowbit(x)) res+=tr[x];return res;
}
int main()
{cin>>n;for(int i=1;i<=n;i++) add(i,1);for(int i=2;i<=n;i++) cin>>a[i];for(int i=n;i>=1;i--){int k=a[i]+1;int l=1,r=n;while(l<r){int mid=l+r>>1;if(ask(mid)>=k) r=mid;else l=mid+1;}h[i]=r;add(r,-1);}for(int i=1;i<=n;i++) cout<<h[i]<<endl;return 0;
}
这篇关于树状数组经典例题:楼兰图腾+一个简单的整数问题+一个简单的证书问题2+谜一样的牛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!