模板题
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<cstdio> #include<queue> #include<map> #include<vector> #include<set> using namespace std; const int maxn=101000; const int INF=0x3fffffff; typedef long long LL; #define lowbit(x) ((x)&(-x)) int tree[maxn]; int n,m; void add(int x,int d){ while(x<=n){ tree[x]+=d; x+=lowbit(x); } } LL getsu(int x){ LL ans=0; while(x>0){ ans+=tree[x]; x-=lowbit(x); } return ans; } int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); add(i,x); } int k,a,b; while(m--){ scanf("%d %d %d",&k,&a,&b); if(k==0) printf("%lld\n",getsu(b)-getsu(a-1)); else add(a,b); } return 0; }
//二维的树状数组bushi
//认真读题呀!!!!!看给出数据的特征,是按照纵坐标从小到大排序的,纵坐标相同的是横坐标从小到大给出的
//也就是说,我们可以不管纵坐标,按照它给出的横坐标依次插入,并统计当前星星之前的横坐标小于它的星星个数。
#include <iostream> #include <cstdio> #include <cmath> using namespace std; int n; int c[100005]; int ans[100055]; int maxn=32001; struct node{ int x,y; }a[100005]; int lowbit(int x) { return x&(-x); } void update(int x,int y) { while(x<=maxn) { c[x]+=y; x+=lowbit(x); } } int sum(int x) { int cnt=0; while(x>0) { cnt+=c[x]; x-=lowbit(x); } return cnt; } int main(){ cin>>n; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&a[i].y); } for(int i=1;i<=n;i++) { int wzx=a[i].x+1; int jd=sum(wzx); update(wzx,1); ans[jd]++; } for(int i=0;i<n;i++) printf("%d\n",ans[i]); return 0; }
原文:https://www.cnblogs.com/shirlybaby/p/12732595.html