其他一些数状数组的题

末蓝、 2021-12-11 05:43 153阅读 0赞

## APPLE TREE-POJ 3321 ##

树上树状数组，lef记录次节点的编号，rig记录他的字节点中编号最大的，则sum(rig)-sum(lef-1)即为

所求值，此题会卡vector常数（我也不知道是什么东西）

#include<iostream>
    #include<string.h> 
    #include<cmath>
    #include<vector>
    #define maxn 100000+10
    using namespace std;
    int n,m,lef[maxn],rig[maxn],sum[maxn],tot,s[maxn];
    vector<vector<int> > q(maxn);
    void add(int x,int d)
    {
        while(x<=n)
        {
            sum[x]+=d;
            x+=x&(-x);
        }
    }
    int susm(int x)
    {
        int ans=0;
        while(x)
        {
            ans+=sum[x];
            x-=x&(-x);
        }
        return ans;
    }
    void dfs(int x)
    {
        lef[x]=tot;
        for(int i=0;i<q[x].size();i++)
        {
            tot++;
            dfs(q[x][i]);
        }
        rig[x]=tot;
    }                    
    int main()
    {
        while(cin>>n)
        {
        memset(sum,0,sizeof(sum));
        memset(lef,0,sizeof(lef));
        memset(rig,0,sizeof(rig));
        memset(s,0,sizeof(s));
        for(int i=0;i<maxn;i++) q[i].clear();
       for(int i=1;i<=n-1;i++)
       {
        int x,y;
        cin>>x>>y;
        q[x].push_back(y);
       }
       tot=1;
       dfs(1);
       for(int i=1;i<=n;i++)
       {
           s[i]=1;
           add(i,1);
       }
       cin>>m;
       while(m--)
       {
             char s1[5];
             int x;
          scanf("%s%d",s1,&x);
          if(s1[0]=='Q')
          {
              //int x;
              //cin>>x;
              cout<<susm(rig[x])-susm(lef[x]-1)<<endl;
           } 
           else
           {
                 //int x;
                 //cin>>x;
                 if(s[x]) add(lef[x],-1);
                 else add(lef[x],1);
                 s[x]=!s[x];
                 
          }
       }
        }
       return 0;
    }

## Disharmony Trees   [HDU - 3015][] ##

树状数组加数据离散化，用三次排序解决即可

#include<iostream>
    #include<algorithm>
    using namespace std;
    #define maxn (int)1e5+5
    #include<cstring>
    typedef long long ll;
    int lowbit(int x)
    {
        return x&(-x);
    }
    ll n,c[maxn],c1[maxn];  //c tong ji he zhi c1 tong ji ge shu
    struct node
    {
        ll x,h;
    }tree[maxn];
    bool cmp(node a,node b)
    {
        return a.x<b.x;
    }
    bool cmp1(node a,node b)
    {
        return a.h<b.h;
    }
    void add(ll x,ll num,ll *s)
    {
        while(x<=n)
        {
            s[x]+=num;
            x+=lowbit(x);
        }
    }
    ll sum(ll x,ll *s)
    {
        ll ans=0;
        while(x)
        {
            ans+=s[x];
            x-=lowbit(x);
        }
        return ans;
    }
    int main()
    {
        while(cin>>n)
        {
            for(int i=1;i<=n;i++) cin>>tree[i].x>>tree[i].h;
            sort(tree+1,tree+1+n,cmp);
            int ji=tree[1].x;
            tree[1].x=1;
            for(int i=2;i<=n;i++)
            {
                if(tree[i].x==ji) tree[i].x=tree[i-1].x;
                else
                {
                    ji=tree[i].x;
                    tree[i].x=i;
                }
            }
            int jilu=tree[n].x;
            sort(tree+1,tree+1+n,cmp1);
            ji=tree[1].h;
            tree[1].h=1;
            for(int i=2;i<=n;i++)
            {
               if(tree[i].h==ji) tree[i].h=tree[i-1].h;
               else
               {
                   ji=tree[i].h;
                   tree[i].h=i;
               }    
            }
            sort(tree+1,tree+1+n,cmp1);
            memset(c,0,sizeof(c));
            memset(c1,0,sizeof(c1));
            for(int i=1;i<=n;i++)
            {
              add(tree[i].x,tree[i].x,c);
              add(tree[i].x,1,c1);    
            }
            int xiao,da;
            ll ans=0;
            for(int i=1;i<=n;i++)
            {
                xiao=sum(tree[i].x-1,c1)*tree[i].x-sum(tree[i].x-1,c);
                da=(sum(jilu,c)-sum(tree[i].x,c))-(sum(jilu,c1)-sum(tree[i].x,c1))*tree[i].x;
                ans+=tree[i].h*(xiao+da);
                add(tree[i].x,-tree[i].x,c);
                add(tree[i].x,-1,c1);
                
            }
            cout<<ans<<endl;    
        }    
        return 0;
    }

转载于:https://www.cnblogs.com/tombraider-shadow/p/11157897.html

[HDU - 3015]: https://vjudge.net/problem/17589/origin