牛客竞赛题目讲解_DongDong数颜色(树状数组)

//  https://ac.nowcoder.com/acm/contest/31084/C

#include "stdafx.h"

//#include <bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;

typedef long long ll;

const int maxn = 100010; 

int q;

int n;

std::vector<int> son[maxn];

int in[maxn];

int out[maxn];

int tree[maxn];

int num[maxn];

int a[maxn]={0,1 ,4 ,2, 2};

int vis[maxn];

struct node

{

    int l,r;

    int x;

    int id;

}b[maxn];

 int ans[maxn];

int edge[32][2]={

1 ,4,

1 ,2,

2, 3

};

 

void add(int x,int val)

{

    while(x<maxn)

    {

        tree[x]+=val;

        x+=-x&x;// 上移至父节点  

    }

}

int ask(int x)

{

    int res=0;

    while(x)

    {

        res+=tree[x];

        x-=-x&x;// 子节点, 如果i=3, 下一个节点为i=2  

    }

    return res;

}

int tot=0;

void dfs(int x,int pre)

{

    in[x]=++tot;// 以x为根的树起始顶点编号

    num[tot]=x;

    for(auto y:son[x])

    {

        if(y!=pre)

        {

            dfs(y,x);

        }

    }

    out[x]=tot;// 以x为根的树结束顶点编号

}

bool cmp(node aa,node bb)

{

    return aa.r<bb.r;

}

int main()

{

    

    gbtb;

n=4;q=3;

    //cin>>n>>q;

    repd(i,1,n)

    {

        //cin>>a[i];

    }

    int u,v;

    repd(i,2,n)

    {

        //cin>>u>>v;

u=edge[i-2][0];

v=edge[i-2][1];

        son[u].push_back(v);

        son[v].push_back(u);

    }

    dfs(1,-1);

   repd(i,1,n)cout<<"  num[i]= "<<num[i];

   cout<<endl<<"顶点新编号对应原来的顶点号码"<<endl;

    repd(i,1,n)

    {

        b[i].l=in[i];

        b[i].r=out[i];

        b[i].x=a[i];

        b[i].id=i;// 原来顶点号码

cout<<"  i= "<<i<<" in[i]="<<in[i]<<"  out[i]="<<out[i]<<endl;

    }

    sort(b+1,b+1+n,cmp);// 按照b[i].r排序

    int p=1;

    repd(i,1,n)

    {  

        while(p<=b[i].r)

        {

            int y=num[p];

//if(i==n)cout<<" vis[a[y]]="<<vis[a[y]]<<" b[i].l="<<b[i].l<<endl;

            if(vis[a[y]])

            { 

                add(vis[a[y]],-1);// 去除前面相同颜色在tree上面的值， 可能vis[a[y]]<b[i].l

                add(p,1);

                vis[a[y]]=p; 

            }else  

            {

add(p,1);

                vis[a[y]]=p;                

            }

            p++;

        }

cout<<"b[i].id="<<b[i].id<<"  ask(b[i].r)="<< ask(b[i].r)<<"   ask(b[i].l-1)="<<ask(b[i].l-1)<<endl;

        ans[b[i].id]=ask(b[i].r)-ask(b[i].l-1);

    }

int qu[32]={4,2,1};

    while(q--)

    {

        int x;

        //cin>>x;

        cout<<qu[q]<<"=qu[q],  "<<ans[qu[q]]<<endl;

    }

    return 0;

}