hdu 5437 Alisha’s Party (线段树)

Problem Description

Princess Alisha invites her friends to come to her birthday party. Each of her friends will bring a gift of some value

person to enter her castle is.

Input

The first line of the input gives the number of test cases,

Output

For each test case, output the corresponding name of Alisha’s query, separated by a space.

Sample Input

5 2 3

Sorey 3

Rose 3

Maltran 3

Lailah 5

Mikleo 6

1 1

4 2

1 2 3

Sample Output

Sorey Lailah Rose

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 int mxx,jl[150005],xyz;
  6 struct tr
  7 {
  8    int l,r,mx,d;
  9 };tr tree[1500000];
 10 struct p
 11 {
 12   int x;
 13   char s[205];
 14 };p str[150005];
 15 struct pp
 16 {
 17    int id,y;
 18 };pp arr[150005];
 19 bool com(pp a,pp b)
 20 {
 21    return a.id<b.id;
 22 }
 23 void build(int l,int r,int p)
 24 {
 25    tree[p].l=l;
 26    tree[p].r=r;
 27    if (l==r)
 28    {
 29        tree[p].mx=str[l].x;
 30        tree[p].d=l;
 31        return ;
 32    }
 33    int m=(l+r)/2;
 34    build(l,m,p*2);
 35    build(m+1,r,p*2+1);
 36    tree[p].mx=max(tree[p*2].mx,tree[p*2+1].mx);
 37 }
 38 void find(int l,int r,int p)
 39 {
 40    if (tree[p].l==l&&tree[p].r==r)
 41    {
 42       mxx=max(mxx,tree[p].mx);
 43       return ;
 44    }
 45    int m=(tree[p].l+tree[p].r)/2;
 46    if (l>m) find(l,r,p*2+1);
 47    else if (m>=r) find(l,r,p*2);
 48    else
 49    {
 50       find(l,m,p*2);
 51       find(m+1,r,p*2+1);
 52    }
 53 }
 54 void un(int l,int r,int x,int p)
 55 {
 56    if (xyz==1) return ;
 57    if (tree[p].l==tree[p].r)
 58    {
 59        if (tree[p].mx==x&&tree[p].l==l&&tree[p].r==r)
 60        {
 61            mxx=tree[p].d;
 62            tree[p].mx=0;
 63            xyz++;
 64        }
 65        return ;
 66    }
 67    if (tree[p].l==l&&tree[p].r==r)
 68    {
 69        int m=(l+r)/2;
 70        if (x==tree[p*2].mx) un(l,m,x,p*2);
 71        else if (x==tree[p*2+1].mx) un(m+1,r,x,p*2+1);
 72        tree[p].mx=max(tree[p*2].mx,tree[p*2+1].mx);
 73        return ;
 74    }
 75    int m=(tree[p].l+tree[p].r)/2;
 76    if (l>m) un(l,r,x,p*2+1);
 77    else if (m>=r) un(l,r,x,p*2);
 78    else
 79    {
 80       un(l,m,x,p*2);
 81       un(m+1,r,x,p*2+1);
 82    }
 83    tree[p].mx=max(tree[p*2].mx,tree[p*2+1].mx);
 84 }
 85 int main()
 86 {
 87    int t,n,i,k,m,q,p;
 88    scanf("%d",&t);
 89    while (t--)
 90    {
 91        scanf("%d%d%d",&k,&m,&q);
 92        for (i=1;i<=k;i++)
 93        {
 94           getchar();
 95           scanf("%s %d",&str[i].s,&str[i].x);
 96        }
 97        for (i=1;i<=m;i++) scanf("%d %d",&arr[i].id,&arr[i].y);
 98        sort(arr+1,arr+m+1,com);
 99        build(1,k,1);
100        p=1;
101        for (i=1;i<=m;i++)
102        {
103        if (arr[i].id>k) arr[i].id=k;
104            while (arr[i].y--)
105            {
106               mxx=0;
107               xyz=0;
108               find(1,arr[i].id,1);
109               if (mxx==0) break;
110               un(1,arr[i].id,mxx,1);
111               jl[p]=mxx;
112               p++;
113            }
114        }
115        while (1)
116        {
117             mxx=0;
118             xyz=0;
119             find(1,k,1);
120             if (mxx==0) break;
121             un(1,k,mxx,1);
122             jl[p]=mxx;
123             p++;
124         }
125        for (i=1;i<q;i++)
126        {
127            scanf("%d",&n);
128            printf("%s ",str[jl[n]].s);
129        }
130        if (q!=0)
131        {
132           scanf("%d",&n);
133           printf("%s
",str[jl[n]].s);
134        }
135    }
136 }

hdu 5437 Alisha’s Party (线段树)

相关推荐