Fenwick

hdu1394 这题说的是给了一个序列计算这个序列的逆序对总共要进行n次每次都将目前的第一个放到序列的最后一个位置然后计算一次逆序对这样我们只需要先求一次逆序对然后接着每次都用F=F+(n-T[i]-1)+T[i] 求得下一个就不需要每次都去算逆序对

#include <iostream>

#include <cstdio>

#include <string.h>

using namespace std;

const int maxn = ;

int C[];

int T[];

int n;

int lowbit(int x){

    return x&(-x);

}

int sum(int x){

    int ret = ;

    while(x>){

         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 =;

       for(int i = ;i<n ;++ i){

            add(T[(st+i)%n],);

            int S1=sum(n);

            int S2 =sum(T[(st+i)%n]);

            ans+=S1-S2;

       }

       return ans;

}

int main()

{

      while(scanf("%d",&n) == ){

          int ans =0x7fffffff;

          for(int i =  ; i< n ;++ i){

                scanf("%d",&T[i]);

                ++T[i];

            }

            memset(C,,sizeof(C));

            int f=Fenwick();

            for(int i= ; i<n ;++i){

                f=f+n-T[i]-(T[i]-);

                ans =min(ans,f);

            }

          printf("%d\n",ans);

      }

      return ;

}

acdream1127 这题说的是给了两个大站点在大站点的他们附近有许多的小站点小站点只能通过大站点与外界通信大站点有一个圆形的作用范围这个范围内的点可以接受信息范围外的不能好了就这样,这样他给了很多个不同的半径计算在每个半径不同的情况下又多少个点不在范围内因为有两个点所以每个点就形成了与他们距离的一个二维的相对坐标,当他不在第一个点的坐标内的时候我们可以将他放进第二维的树状数组中通过求和判断是否在第二维的相应的坐标里这样我们用第二点的半径所在的位置去进行一次求和和总数n sum(n)得到的是目前不在第一个范围内的点的个数sum(第二个半径的位置) 得到的是在第二个范围内点的个数然后相减一下就得到了

#include <iostream>

#include <cstdio>

#include <string.h>

#include <algorithm>

using namespace std;

const int maxn=;

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 =;

      while(x>){

          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)==){

           scanf("%d",&N);

           for(int i = ; 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+]=P[i].y;

           }

           int M;

           scanf("%d",&M);

           for(int i = ; 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+,dist++N);

           int num=unique(dist+,dist++N)--dist;

           sort(Query,Query+N,cmp1);

           int id=;

           memset(C,,sizeof(C));

           for(int i =; i<M; ++ i) {

                 while( id<N && P[id].x >= Query[i].x ) {

                      int loc = lower_bound( dist + , dist++num, P[id].y )-dist;

                      add(loc,);

                      ++id;

                 }

                int lox = lower_bound(dist + , dist++num, Query[i].y)-dist-;

                int SN =sum(N);

                int SLOX =sum(lox);

                ans[Query[i].num] = SN -SLOX;

           }

           for(int i =; i<M; ++i)

            printf("%d\n",ans[i]);

      }

      return ;

}

#247div2 E 题这题说的是有n个试管每个试管中有一些汞然后又两种操作第一种是将某个试管中的汞的体积变成 xi 然后将第二种操作是将 Vi 升的水倒入这n个试管中求有装水的试管中水的体积最大的体积最小, 这样我们可以去二分找这个可能的高度 ,将所有可能的高度进行一次离散化,然后不断的用树状数组去修改和查询,然后得到了正解

#include <iostream>

#include <cstdio>

#include <string.h>

#include <set>

#include <map>

using namespace std;

const int maxn=;

int h[maxn],T[],n,q,max_h=;

int p[],x[],cap[maxn];

__int64 V[];

__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=;

     while(x>){

         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 =; i<=n; ++i){

          scanf("%d",&h[i]);

          Live.insert(h[i]);

       }

       for( int i =; i<q; ++i){

          scanf("%d",&T[i]);

          if(T[i] == ){

             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+));

           ++max_h;

           cap[max_h] = E;

       }

       for(int i =; i<=n; ++i){

          int loc = MP[h[i]];

          add(A,loc,);

          add(B,loc,h[i]);

       }

       for(int e=; e<q; ++e){

           if(T[e]==){

                int t = p[e];

                int loc = MP[h[t]];

                add(A, loc, -);

                add(B, loc, -h[t]);

                h[t] = x[e];

                loc  = MP[h[t]];

                add(A, loc, );

                add(B, loc, h[t]);

           }else{

                int H=;

                for(int i = ; i>=; -- i){

                    if((H+(<<i))>max_h) continue;

                    if(solve((H+(<<i)))<=V[e])

                        H=H+(<<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 ;

}

uva1513 这题说的是给了一个堆(从1...到n) 然后从堆中的某个位置取一个点出来放在最顶端每次操作时输出在该点的上方有多少个点用树状数组去查询自然前面预留m个位置可以放后面堆叠的在前面的然后每次操作记录一下该点所在的位置

#include <iostream>

#include <cstdio>

#include <string.h>

using namespace std;

const int maxn=;

int n,m,local[maxn];

int C[maxn*],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=;

    while(x>){

        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=;i<=n+m; ++i)C[i]=;

       for(int i=; i<=n; ++i){

            local[i]=i+m;

            add(m+i,);

       }

       int len=;

       for( int i=m; i> ; --i){

            int a;

            scanf("%d",&a);

            ans[len++]=sum(local[a]-);

            add(local[a],-);

            local[a]=i;

            add(local[a],);

        }

        for(int i=;i<len-; ++i)

            printf("%d ",ans[i]);

        printf("%d\n",ans[len-]);

    }

    return ;

}

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 = ;

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=;

   while(x>){

      ans+=C[x]; x-=lowbit(x);

   }

   return ans;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--){

        memset(C,,sizeof(C));

        scanf("%d",&K);

        for( int i=; i<K; ++i )

            scanf("%d",&S[i]);

        for(int i=; i<=K ; ++i)

            add(i,);

        for(int i=; i<K; ++i){

            int L=,R=K;

            while(L<R){

                int mid=L+((R-L)>>);

                int num=sum(mid);

                if(num>=(S[i]+))

                    R=mid;

                else L=mid+;

            }

            add(L,-);

            ans[i]=L;

        }

        for(int i=;i<K-; ++i)

            printf("%d ",ans[i]);

        printf("%d\n",ans[K-]);

    }

    return ;

}

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[],machine[];

__int64 X[],Y[];

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=;

    while(x>){

        ans+=C[x]; x-=lowbit(x);

    }

    return ans;

}

bool bit_time(int D)

{

   __int64 zong = sum(X,);

   __int64 di=sum(X,D-);

   if(zong-di<=)return false;

  // add(X,D,-1,1440);

   return  true;

}

bool bit_rank(int D)

{

   __int64 zong = sum(Y,);

   __int64 di = sum(Y,D-);

   __int64 er = zong-di;

   if(er<=)return false;

   int L = D , R =;

   while(L<R){

      int mid=(R+L)/;

      __int64 W =sum(Y,mid)-di;

      if(W==)L=mid+;

      else R=mid;

   }

   add(Y,L,-,);

   return true;

}

void solve(int N,int M)

{

      __int64 ans=;

      int s=,num=;

      for(int i=; i<N; ++i)

        {

             add(X,machine[i].timef,,);

        }

      for(int i=; i<M; ++i){

           while(s<N&&machine[s].timef>=Task[i].timef){

                add(Y,machine[s].rankf,,);

                s++;

           }

           if(bit_time(Task[i].timef)){

              if(bit_rank(Task[i].rankf)){

                    add(X,Task[i].timef,-,);

                 ans+= *Task[i].timef+*(Task[i].rankf-);

                 num++;

              }

           }

      }

      printf("%d %I64d\n",num,ans);

}

int main()

{

     int N,M;

     while(scanf("%d%d",&N,&M)==)

        {

            memset(X,,sizeof(X));

            memset(Y,,sizeof(Y));

              for(int i = ; i<N; ++i){

                scanf("%d%d",&machine[i].timef,&machine[i].rankf);

                machine[i].rankf++;

              }

              for(int i=; 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 ;

}

/*

3 4

100 3

101 2

99 2

99 3

100 3

100 2

99 2

*/

cf459D 题说的是计算 [1,i] 中值等于ai 的个数 x1，求出[j,n]中 aj的个数 x2 其中i小于 j 然后求出，使得x1小于x2的ij的对数，首先对数组进行离散然后，从后往前每个位子都将从该位置的aj以及该位置以后aj的个数，插入树状数组中去，然后枚举每一个i并将相应的aj个数从树状数组中删去然后对于每一个ai个数在数组中找出小于该个数长度的数有多少个，每次加起来就可以了

的

巴特西

Fenwick

最新文章

热门文章