hdu 3436セグメントツリー1回の操作
Queue-jumpers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3348 Accepted Submission(s): 904
Problem Description
Ponyo and Garfield are waiting outside the box-office for their favorite movie. Because queuing is so boring, that they want to play a game to kill the time. The game is called “Queue-jumpers”. Suppose that there are N people numbered from 1 to N stand in a line initially. Each time you should simulate one of the following operations:
1. Top x :Take person x to the front of the queue
2. Query x: calculate the current position of person x
3. Rank x: calculate the current person at position x
Where x is in [1, N].
Ponyo is so clever that she plays the game very well while Garfield has no idea. Garfield is now turning to you for help.
Input
In the first line there is an integer T, indicates the number of test cases.(T<=50)
In each case, the first line contains two integers N(1<=N<=10^8), Q(1<=Q<=10^5). Then there are Q lines, each line contain an operation as said above.
Output
For each test case, output “Case d:“at first line where d is the case number counted from one, then for each “Query x” operation ,output the current position of person x at a line, for each “Rank x” operation, output the current person at position x at a line.
Sample Input
Sample Output
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3348 Accepted Submission(s): 904
Problem Description
Ponyo and Garfield are waiting outside the box-office for their favorite movie. Because queuing is so boring, that they want to play a game to kill the time. The game is called “Queue-jumpers”. Suppose that there are N people numbered from 1 to N stand in a line initially. Each time you should simulate one of the following operations:
1. Top x :Take person x to the front of the queue
2. Query x: calculate the current position of person x
3. Rank x: calculate the current person at position x
Where x is in [1, N].
Ponyo is so clever that she plays the game very well while Garfield has no idea. Garfield is now turning to you for help.
Input
In the first line there is an integer T, indicates the number of test cases.(T<=50)
In each case, the first line contains two integers N(1<=N<=10^8), Q(1<=Q<=10^5). Then there are Q lines, each line contain an operation as said above.
Output
For each test case, output “Case d:“at first line where d is the case number counted from one, then for each “Query x” operation ,output the current position of person x at a line, for each “Rank x” operation, output the current person at position x at a line.
Sample Input
3
9 5
Top 1
Rank 3
Top 7
Rank 6
Rank 8
6 2
Top 4
Top 5
7 4
Top 5
Top 2
Query 1
Rank 6
Sample Output
Case 1:
3
5
8
Case 2:
Case 3:
3
6
/*
hdu 3436
splay , ( splay )
Top: x
Query: x
Rank: x
top , 2e5. Rank
Query . ,
hhh-2016-04-12 19:20:16
*/
#include
#include
#include
#include
#include
#include
typedef long long ll;
#define lson (i<<1)
#define rson ((i<<1)|1)
using namespace std;
const int maxn = 1e6+10;
struct node
{
int l,r;
int sum,val;
int mid()
{
return (l+r)>>1;
}
} tree[maxn<<2];
int T,n,m;
int a[maxn];
int ano[maxn];
int st[maxn],en[maxn];
int pos[maxn];
char op[maxn][6];
int tot,TOT;
void push_up(int i)
{
tree[i].sum = tree[lson].sum + tree[rson].sum;
}
void build(int i ,int l,int r)
{
tree[i].l =l ,tree[i].r = r;
tree[i].sum = 0;
tree[i].val = 0;
if(l == r)
{
if(tree[i].l > m)
{
int t = tree[i].l-m;
tree[i].val = t;
tree[i].sum = en[t]-st[t]+1;
}
return ;
}
int mid = tree[i].mid();
build(lson,l,mid);
build(rson,mid+1,r);
push_up(i);
}
void push_down(int i)
{
}
void update(int i,int k,int val)
{
if(tree[i].l == tree[i].r )
{
if(!val) tree[i].sum = 0,tree[i].val = 0;
else tree[i].sum = en[val]-st[val]+1,tree[i].val = val;
return ;
}
int mid = tree[i].mid();
if(k <= mid)
update(lson,k,val);
else
update(rson,k,val);
push_up(i);
}
int sum(int i,int l,int r)
{
if(tree[i].l>=l && tree[i].r <= r)
return tree[i].sum;
int mid = tree[i].mid();
int su = 0;
if(l <= mid)
su += sum(lson,l,r);
if(r > mid)
su += sum(rson,l,r);
push_up(i);
return su;
}
int get_k(int i,int k)
{
if(tree[i].l == tree[i].r && k <= en[tree[i].val]-st[tree[i].val]+1)
return st[tree[i].val]+k-1;
int mid = tree[i].mid();
if(k <= tree[lson].sum)
return get_k(lson,k);
else
return get_k(rson,k-tree[lson].sum);
push_up(i);
}
int bin(int key)
{
int l = 1,r = tot-1;
while(l <= r)
{
int mid = (l+r)>>1;
if(st[mid]<=key && en[mid]>=key)
return mid;
else if(key < st[mid])
r = mid - 1;
else
l = mid + 1;
}
}
int main()
{
int cas = 1;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
tot = 0;
for(int i = 1; i <= m; i++)
{
scanf("%s%d",op[i],&a[i]);
if(op[i][0] == 'T' || op[i][0] == 'Q')
ano[tot++] = a[i];
}
ano[tot++] = 1,ano[tot++] = n;
sort(ano,ano+tot);
// for(int i = 0;i < tot;i++)
// cout << ano[i] < 1)
{
st[tot] = ano[i-1]+1;
en[tot++] = ano[i]-1;
}
st[tot] = ano[i];
en[tot] = ano[i];
tot++;
}
}
// for(int i = 1;i < tot;i++)
// cout <