首页 > 代码库 > NYOJ 945 Just do it

NYOJ 945 Just do it

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=945

 

思路:和hdu3333一个类型的题目。。图灵树,据说很有名~。。 

 

 #include <iostream>#include <cstring> #include <algorithm> #include <cstdio>#include <map> #define MAXSIZE 300001using namespace std;struct query_node{    int l,r,index;    friend bool operator < (query_node a,query_node b)    {        return a.r < b.r;     } }q[200010];struct node {    int l,r;    int sum;}tree[MAXSIZE*4];int num[MAXSIZE];void build(int root,int l,int r){    tree[root].sum = 0;    tree[root].l = l;    tree[root].r = r;        if(l==r)    {        return;    }        int mid = (l+r)/2;        build(root*2,l,mid);    build(root*2+1,mid+1,r);}void updata(int root,int pos,int value){    int mid;    if(tree[root].l==tree[root].r&&tree[root].l==pos)    {        tree[root].sum += value;        return;    }        mid = (tree[root].l+tree[root].r)>>1;        if(pos<=mid)    {        updata(root*2,pos,value);            }    else    {        updata(root*2+1,pos,value);    }    tree[root].sum = tree[2*root].sum+tree[2*root+1].sum;    return; }int query(int root,int l,int r){    if(tree[root].l>=l&&tree[root].r<=r)    {        return tree[root].sum;    }        int mid = (tree[root].r+tree[root].l)/2;        if(l>mid)    {        return query(root*2+1,l,r);    }    else if(r<=mid)    {        return query(root*2,l,r);     }    else    {        int a = query(root*2,l,mid);        int b = query(root*2+1,mid+1,r);        return a+b;    }}int main(){    //freopen("data.txt","r",stdin);    int ans[MAXSIZE];    map<int,int> hash;    int t;    scanf("%d",&t);    while(t--)    {        int n,m;        hash.clear();        scanf("%d",&n);        memset(ans,0,sizeof(ans));        build(1,1,n);        for(int i=1;i<=n;i++)        {            scanf("%d",num+i);        }        scanf("%d",&m);                for(int i=0;i<m;i++)        {            scanf("%d %d",&(q[i].l),&(q[i].r));            q[i].index = i;        }        sort(q,q+m);                int pos = 1;                for(int i=0;i<m;i++)        {            for(;pos<=n&&pos<=q[i].r;pos++)            {                if(hash[num[pos]]!=0)                     updata(1,hash[num[pos]],-1);                updata(1,pos,1);                hash[num[pos]] = pos;            }                ans[q[i].index] = query(1,q[i].l,q[i].r);        }                 for(int i=0;i<m;i++)        {            printf("%d\n",ans[i]);        }    }    return 0;}         

 

NYOJ 945 Just do it