所有的排序和复杂度比较
/wuxinyan/p/8615127.html
华为笔试题回顾：
第2道：
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int maxn = 4e4 + 5;int a[maxn];int st[maxn];void build(int o,int l,int r){if(l == r)st[o] = a[l];else{int m = l + ((r-l) >> 1);build(o << 1,l,m);build((o<<1)|1,m+1,r);st[o] = st[o << 1] + st[(o<<1)|1];}}void update(int o,int l,int r,int ind,int ans){if(l == r){st[o] += ans;return ;}int m = l + ((r-l) >> 1);if(ind <= m)update(o << 1,l,m,ind,ans);elseupdate((o<<1)|1,m+1,r,ind,ans);st[o] = st[o<<1] + st[(o<<1)|1];}int query(int o,int l,int r,int ql,int qr){if(ql > r || qr < l)return 0;if(ql <=l && qr >=r)return st[o];int m = l + ((r-l) >> 1);int p1 = query(o<<1,l,m,ql,qr);int p2 = query((o<<1)|1,m+1,r,ql,qr);return p1 + p2;}int main(){int n,m;scanf("%d %d",&n,&m);for(int i = 1; i <= n; i++)scanf("%d",&a[i]);build(1,1,n);char op[5];int l,r;while(m--){scanf("%s",op);if(op[0] == 'Q'){scanf("%d %d",&l,&r);int ans = query(1, 1, n, l, r);ans /= (r - l + 1);printf("%d\n",ans);}else {scanf("%d %d",&l,&r);update(1, 1, n, l, r);}}}
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int maxn = 1e5 + 50;int c[maxn];int lowbit(int x) {return x & (-x);}void update(int x,int y,int n){for(int i=x;i<=n;i+=lowbit(i)) c[i] += y;}int getsum(int p) {if(p == 0)return 0;int res = 0;while(p) {res += c[p];p -= lowbit(p);}return res;}int num[maxn];int main(){int t;int MAXN = 1e5 + 4;scanf("%d",&t);while(t--){memset(num,0,sizeof num);memset(c,0,sizeof c);int n;scanf("%d",&n);int maxx = -1;int sum = 0;int x;for(int i = 0; i < n; i++){scanf("%d",&x);int t1 = getsum(x - 1);int t3 = getsum(MAXN);// cout << t3 << endl;t3 -= num[x];int t2 = t3 - t1;// printf("%d %d %d\n",t1,t2,t3);sum += (t1 - t2);maxx = max(maxx,sum);num[x]++ ;// cout << num[x] << " sdf " << endl;update(x,1,MAXN);}printf("%d %d\n",maxx,sum);}}
