首页 > 代码库 > 树状数组 LA 4329 亚洲赛北京赛区题
树状数组 LA 4329 亚洲赛北京赛区题
复习下树状数组
还是蛮有意思的一道题:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=501&page=show_problem&problem=4174
学到几点:
1、树状数组C[i]的构建,一则c[i]=s[i]-s[i-lowbit(i)];这是一直用的做法。如今学到一种新的,直接add(i,a[i]),(s[i]为a[1]到a[i]的和)
2、前缀和思想,树状数组的Sum本身就是基于前缀和的思想。本题把比某数小的数的个数,通过开大量空间+后缀数组,高效的统计出来比某数小的数的个数
3、事实上我认为通过这个题。能够做出来一种O(nlogn)的排序算法。当然不完好的地方就是仅仅能是整数了,可是应该能够用vector+map解决?
贴自己的代码先。,,由于后面的Lrj大牛的代码太简洁...
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <functional> using namespace std; #define MAXN 20010 #define SIZE 100015 int a[MAXN],sma[SIZE],c[SIZE],s[SIZE],e[SIZE],tot[SIZE]; int n,mmax; int lowbit(int i) { return i & (-i); } int sum(int i) { int ans=0; for(;i>0;i-=lowbit(i)) ans+=c[i]; return ans; } void add(int x, int d) { while(x <= SIZE) { c[x] += d; x += lowbit(x); } } void Init() { memset(c,0,sizeof(c)); memset(a,0,sizeof(a)); memset(sma,0,sizeof(sma)); memset(s,0,sizeof(s)); memset(e,0,sizeof(e)); memset(tot,0,sizeof(tot)); } int main() { //freopen("la4329.txt","r",stdin); int t; long long ans; scanf("%d",&t); while(t--) { mmax=0; ans=0; Init(); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); mmax=max(mmax,a[i]); add(a[i],1); //c[i]=sum(a[i]-1); e[a[i]]=1; sma[a[i]]=sum(a[i]-1); } memset(c,0,sizeof(c)); for(int i=1;i<=mmax;i++) { s[i] =s[i-1]+e[i]; c[i]=s[i]-s[i-lowbit(i)]; tot[i]=sum(i-1); } /////////////////////// //for(int i=1;i<=n;i++) //{ // printf("sma[a[%d]] = %d tot(%d) = %d\n",i,sma[a[i]],a[i],tot[a[i]]); //} /////////////////////// for(int i=1;i<=n;i++) { int tmp = tot[a[i]]-sma[a[i]];/*a[i]之后比a[i]小的个数*/ ans+=(long long )tmp*(i-1-sma[a[i]])+(long long)sma[a[i]]*(n-i-tmp); } printf("%lld\n",ans); } return 0; }
标程
// LA4329 Ping pong // Rujia Liu #include<cstdio> #include<vector> using namespace std; //inline int lowbit(int x) { return x&(x^(x-1)); } inline int lowbit(int x) { return x&-x; } struct FenwickTree { int n; vector<int> C; void resize(int n) { this->n = n; C.resize(n); } void clear() { fill(C.begin(), C.end(), 0); } // ????A[1]+A[2]+...+A[x] (x<=n) int sum(int x) { int ret = 0; while(x > 0) { ret += C[x]; x -= lowbit(x); } return ret; } // A[x] += d (1<=x<=n) void add(int x, int d) { while(x <= n) { C[x] += d; x += lowbit(x); } } }; const int maxn = 20000 + 5; int n, a[maxn], c[maxn], d[maxn]; FenwickTree f; int main() { freopen("la4329.txt","r",stdin); int T; scanf("%d", &T); while(T--) { scanf("%d", &n); int maxa = 0; for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); maxa = max(maxa, a[i]); } f.resize(maxa); f.clear(); for(int i = 1; i <= n; i++) { f.add(a[i], 1); c[i] = f.sum(a[i]-1); } f.clear(); for(int i = n; i >= 1; i--) { f.add(a[i], 1); d[i] = f.sum(a[i]-1); } long long ans = 0; for(int i = 1; i <= n; i++) ans += (long long)c[i]*(n-i-d[i]) + (long long)(i-c[i]-1)*d[i]; printf("%lld\n", ans); } return 0; }
树状数组 LA 4329 亚洲赛北京赛区题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。