首页 > 代码库 > Fenwick
Fenwick
hdu1394 这题说的是给了一个序列计算这个序列的逆序对总共要进行n次 每次都将目前的第一个放到序列的最后一个位置然后 计算一次逆序对 这样我们只需要先求一次逆序对 然后接着每次都用F=F+(n-T[i]-1)+T[i] 求得下一个 就不需要每次都去算逆序对
#include <iostream>#include <cstdio>#include <string.h>using namespace std;const int maxn = 5005;int C[5005];int T[5005];int n;int lowbit(int x){ return x&(-x);}int sum(int x){ int ret = 0; while(x>0){ ret+=C[x]; x-=lowbit(x); } return ret;}void add(int x,int d){ while(x<=n){ C[x]+=d; x+=lowbit(x); }}int Fenwick(int st){ int ans =0; for(int i = 0;i<n ;++ i){ add(T[(st+i)%n],1); int S1=sum(n); int S2 =sum(T[(st+i)%n]); ans+=S1-S2; } return ans;}int main(){ while(scanf("%d",&n) == 1){ int ans =0x7fffffff; for(int i = 0 ; i< n ;++ i){ scanf("%d",&T[i]); ++T[i]; } memset(C,0,sizeof(C)); int f=Fenwick(0); for(int i=0 ; i<n ;++i){ f=f+n-T[i]-(T[i]-1); ans =min(ans,f); } printf("%d\n",ans); } return 0;}
acdream1127 这题说的是给了两个 大站点 在大站点的他们附近有许多的小站点 小站点只能通过大站点与外界通信 大站点有一个圆形的作用范围 这个范围内的点可以接受信息 范围外的不能好了就这样,这样他给了很多个不同的半径 计算在每个半径不同的情况下又多少个点不在范围内 因为有两个点所以 每个点就形成了与他们距离 的一个二维的相对坐标,当他不在第一个点的坐标内的时候我们可以将他 放进 第二维的树状数组中 通过求和判断是否在第二维的相应的坐标里这样我们 用 第二点的半径所在的位置去进行一次求和 和 总数n sum(n)得到的是 目前不在 第一个范围内的点的个数sum(第二个半径的位置) 得到的是在第二个范围内点的个数 然后相减一下就得到了
#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>using namespace std;const int maxn=100005;int C[maxn],N;struct node{ long long x,y; int num; bool operator <(const node &A)const { return x>=A.x; }}P[maxn],Query[maxn];long long dist[maxn];bool cmp1(node A,node B){ return A.x >= B.x ;}int lowbit(int x){ return x&(-x);}void add(int x,int d){ while(x<=N){ C[x]+=d; x+=lowbit(x); }}int sum(int x){ int ans =0; while(x>0){ ans+=C[x]; x-=lowbit(x); } return ans;}int ans[maxn];int main(){ long long x1,y1,x2,y2; while(scanf("%I64d%I64d%I64d%I64d",&x1,&y1,&x2,&y2)==4){ scanf("%d",&N); for(int i = 0; i<N; ++ i){ long long x,y; scanf("%I64d%I64d",&x,&y); P[i].x=(x-x1)*(x-x1)+(y-y1)*(y-y1); P[i].y=(x-x2)*(x-x2)+(y-y2)*(y-y2); dist[i+1]=P[i].y; } int M; scanf("%d",&M); for(int i = 0; i<M; ++i){ long long r1,r2; scanf("%I64d%I64d",&r1,&r2); Query[i].x=r1*r1; Query[i].y=r2*r2; Query[i].num=i; } sort(P,P+N,cmp1); sort(dist+1,dist+1+N); int num=unique(dist+1,dist+1+N)-1-dist; sort(Query,Query+N,cmp1); int id=0; memset(C,0,sizeof(C)); for(int i =0; i<M; ++ i) { while( id<N && P[id].x >= Query[i].x ) { int loc = lower_bound( dist + 1, dist+1+num, P[id].y )-dist; add(loc,1); ++id; } int lox = lower_bound(dist + 1, dist+1+num, Query[i].y)-dist-1; int SN =sum(N); int SLOX =sum(lox); ans[Query[i].num] = SN -SLOX; } for(int i =0; i<M; ++i) printf("%d\n",ans[i]); } return 0;}
#247div2 E 题 这题说的是 有n个试管每个试管中有一些汞 然后又两种操作 第一种是将某个试管中的汞的体积变成 xi 然后将第二种操作是将 Vi 升的水倒入 这n个试管中求 有装水的试管中水的体积最大的 体积最小, 这样我们可以去二分找这个可能的高度 ,将所有可能的高度进行一次离散化,然后不断的用树状数组去修改和查询,然后得到了正解
#include <iostream>#include <cstdio>#include <string.h>#include <set>#include <map>using namespace std;const int maxn=200005;int h[maxn],T[100005],n,q,max_h=0;int p[100005],x[100005],cap[maxn];__int64 V[100005];__int64 A[maxn],B[maxn];int lowbit(int x){ return x&(-x);}void add(__int64 *C, int x,__int64 d){ while(x<=max_h){ C[x]+=d; x+=lowbit(x); }}__int64 sum(__int64 *C,int x){ __int64 ans=0; while(x>0){ ans+=C[x]; x-=lowbit(x); } return ans;}__int64 solve(int H){ __int64 num=sum(A,H); __int64 remain = sum(B,H); __int64 line=cap[H]; __int64 ans = num * line - remain; return ans;}int main(){ set<int>Live; scanf("%d%d",&n,&q); for(int i =1; i<=n; ++i){ scanf("%d",&h[i]); Live.insert(h[i]); } for( int i =0; i<q; ++i){ scanf("%d",&T[i]); if(T[i] == 1){ scanf("%d%d",&p[i],&x[i]); Live.insert(x[i]); }else scanf("%I64d",&V[i]); } map<int,int>MP; for(set<int>::iterator it=Live.begin(); it!=Live.end(); ++it){ int E = *it; MP.insert(make_pair(E,max_h+1)); ++max_h; cap[max_h] = E; } for(int i =1; i<=n; ++i){ int loc = MP[h[i]]; add(A,loc,1); add(B,loc,h[i]); } for(int e=0; e<q; ++e){ if(T[e]==1){ int t = p[e]; int loc = MP[h[t]]; add(A, loc, -1); add(B, loc, -h[t]); h[t] = x[e]; loc = MP[h[t]]; add(A, loc, 1); add(B, loc, h[t]); }else{ int H=0; for(int i =20 ; i>=0; -- i){ if((H+(1<<i))>max_h) continue; if(solve((H+(1<<i)))<=V[e]) H=H+(1<<i); } double remain=solve(H); double num=sum(A,H); double ans = cap[H]; ans =ans + (double(V[e]) - remain)/num; printf("%.5lf\n",ans); } } return 0;}
uva1513 这 题 说 的 是 给 了 一 个 堆(从1...到n) 然 后 从 堆 中 的 某 个 位 置 取 一 个 点 出 来 放在最顶端 每次 操作时输出在该点的上方有多少个点用树状数组去查询 自然前面预留m个位置 可 以 放 后 面 堆 叠 的 在 前 面 的 然后每次操作记录一下该点所在的位置
#include <iostream>#include <cstdio>#include <string.h>using namespace std;const int maxn=100005;int n,m,local[maxn];int C[maxn*2],ans[maxn];int lowbit(int x){ return x&(-x);}void add(int x,int d){ while(x<=n+m){ C[x]+=d; x+=lowbit(x); }}int sum(int x){ int ans=0; while(x>0){ ans+=C[x]; x-=lowbit(x); } return ans;}int main(){ int cas; scanf("%d",&cas); while( cas -- ){ scanf("%d%d",&n,&m); for(int i=0;i<=n+m; ++i)C[i]=0; for(int i=1; i<=n; ++i){ local[i]=i+m; add(m+i,1); } int len=0; for( int i=m; i>0 ; --i){ int a; scanf("%d",&a); ans[len++]=sum(local[a]-1); add(local[a],-1); local[a]=i; add(local[a],1); } for(int i=0;i<len-1; ++i) printf("%d ",ans[i]); printf("%d\n",ans[len-1]); } return 0;}
uva11525 这个题说的是给了1到K的数列 求出这个数列 的 第n 大 当然按照字典序排列, 因为 n=Si(k-i)!+Si-1(k-(i-1))!+...S0(k-k)! 经过分析我们可以得出这样的一个结论就是Si 代表的是剩下的第几大的数 然后二分去用树状数组照这个点
#include <iostream>#include<cstdio>#include <string.h>using namespace std;const int maxn = 50005;int n,K,S[maxn],ans[maxn],C[maxn];int lowbit(int x){ return x&(-x);}void add(int x,int d){ while(x<=K){ C[x] += d; x+=lowbit(x); }}int sum(int x){ int ans=0; while(x>0){ ans+=C[x]; x-=lowbit(x); } return ans;}int main(){ int t; scanf("%d",&t); while(t--){ memset(C,0,sizeof(C)); scanf("%d",&K); for( int i=0; i<K; ++i ) scanf("%d",&S[i]); for(int i=1; i<=K ; ++i) add(i,1); for(int i=0; i<K; ++i){ int L=1,R=K; while(L<R){ int mid=L+((R-L)>>1); int num=sum(mid); if(num>=(S[i]+1)) R=mid; else L=mid+1; } add(L,-1); ans[i]=L; } for(int i=0;i<K-1; ++i) printf("%d ",ans[i]); printf("%d\n",ans[K-1]); } return 0;}
hdu4863 这题说的是给了 一个公司有 M 个任务 但是有N 台机器每台机器 只能完成一项任务,每个任务只允许一台机器完成,每个任务有一个完成时间和等级 , 每台机器有等级和所能承受的最大时间,然后我们先将按照时间排序 时间形同的任务 ,等级大的放前面,然后每次将时间大于等于当前任务的机器的等级放入树状数组中每次去修改树状数组
#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>using namespace std;struct point{ int timef,rankf; bool operator < (const point A) const{ return timef>A.timef||(timef==A.timef&&rankf>=A.rankf); }}Task[200005],machine[200005];__int64 X[2446],Y[205];int lowbit(int x){ return x&(-x);}void add(__int64 *C, int x, int d,int N){ while(x<=N){ C[x]+=d; x+=lowbit(x); }}__int64 sum(__int64 *C, int x){ __int64 ans=0; while(x>0){ ans+=C[x]; x-=lowbit(x); } return ans;}bool bit_time(int D){ __int64 zong = sum(X,1440); __int64 di=sum(X,D-1); if(zong-di<=0)return false; // add(X,D,-1,1440); return true;}bool bit_rank(int D){ __int64 zong = sum(Y,101); __int64 di = sum(Y,D-1); __int64 er = zong-di; if(er<=0)return false; int L = D , R =101; while(L<R){ int mid=(R+L)/2; __int64 W =sum(Y,mid)-di; if(W==0)L=mid+1; else R=mid; } add(Y,L,-1,101); return true;}void solve(int N,int M){ __int64 ans=0; int s=0,num=0; for(int i=0; i<N; ++i) { add(X,machine[i].timef,1,1440); } for(int i=0; i<M; ++i){ while(s<N&&machine[s].timef>=Task[i].timef){ add(Y,machine[s].rankf,1,101); s++; } if(bit_time(Task[i].timef)){ if(bit_rank(Task[i].rankf)){ add(X,Task[i].timef,-1,1440); ans+= 500*Task[i].timef+2*(Task[i].rankf-1); num++; } } } printf("%d %I64d\n",num,ans);}int main(){ int N,M; while(scanf("%d%d",&N,&M)==2) { memset(X,0,sizeof(X)); memset(Y,0,sizeof(Y)); for(int i =0 ; i<N; ++i){ scanf("%d%d",&machine[i].timef,&machine[i].rankf); machine[i].rankf++; } for(int i=0; i<M; ++i){ scanf("%d%d",&Task[i].timef,&Task[i].rankf); Task[i].rankf++; } sort(machine,machine+N); sort(Task,Task+M); solve(N,M); } return 0;}/*3 4100 3101 299 299 3100 3100 299 2*/
cf459D 题说的是 计算 [1,i] 中 值等于ai 的个数 x1， 求出[j,n]中 aj的 个数 x2 其中i小于 j 然后求出，使得x1小于x2的ij的对数，首先对数组进行离散然后，从后往前每个位子都将从该位置的aj以及该位置以后aj的个数，插入树状数组中去，然后 枚举每一个i并将相应的aj个数从 树状数组中删去然后 对于每一个ai个数 在数组中找出小于该个数长度的数有多少个，每次加起来就可以了
的
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。