Jewel
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 985 Accepted Submission(s): 247
Initially, there is no bead at all, that is, there is an empty chain. Jimmy always sticks the new bead to the right of the chain, to make the chain longer and longer. We number the leftmost bead as Position 1, and the bead to its right as Position 2, and so on. Jimmy usually asks questions about the beads' positions, size ranks and actual sizes. Specifically speaking, there are 4 kinds of operations you should process:
Insert x
Put a bead with size x to the right of the chain (0 < x < 231, and x is different from all the sizes of beads currently in the chain)
Query_1 s t k
Query the k-th smallest bead between position s and t, inclusive. You can assume 1 <= s <= t <= L, (L is the length of the current chain), and 1 <= k <= min (100, t-s+1)
Query_2 x
Query the rank of the bead with size x, if we sort all the current beads by ascent order of sizes. The result should between 1 and L (L is the length of the current chain)
Query_3 k
Query the size of the k-th smallest bead currently (1 <= k <= L, L is the length of the current chain)
You can assume the amount of "Insert" operation is no more than 100000, and the amounts of "Query_1", "Query_2" and "Query_3" are all less than 35000.
There are several test cases in the input. The first line for each test case is an integer N, indicating the number of operations. Then N lines follow, each line contains one operation, as described above.
You can assume the amount of "Insert" operation is no more than 100000, and the amounts of "Query_1", "Query_2" and "Query_3" are all less than 35000.Query the rank of the bead with size x, if we sort all the current beads by ascent order of sizes. The result should between 1 and L (L is the length of the current chain)
Query_3 k
Query the size of the k-th smallest bead currently (1 <= k <= L, L is the length of the current chain)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5+;
int lson[maxn*],rson[*maxn],c[maxn*];
int tree[maxn],tot,idx,maxv;
int build (int l,int r)
{
int root = tot++;
c[root] = ;
if (l != r)
{
int mid =(l + r) >> ;
lson[root] = build(l,mid);
rson[root] = build(mid+,r);
}
return root;
}
int update(int root,int pos,int val)
{
int newroot = tot++;
int tmp = newroot;
int l = ,r = maxv;
c[newroot] = c[root] + val;
while (l < r)
{
int mid = (l + r) >> ;
if (pos <= mid)
{
rson[newroot] = rson[root];
root = lson[root];
lson[newroot] = tot++;
newroot = lson[newroot];
r = mid;
}
else
{
lson[newroot] = lson[root];
root = rson[root];
rson[newroot] = tot++;
newroot = rson[newroot];
l = mid + ;
}
c[newroot] = c[root] + val;
}
return tmp;
}
int query(int left,int right,int k)
{
int l_root = tree[left-];
int r_root = tree[right];
int l = , r = maxv;
while (l < r)
{
int mid = (l + r) >> ;
if (c[lson[r_root]] - c[lson[l_root]] >= k)
{
r = mid;
l_root = lson[l_root];
r_root = lson[r_root];
}
else
{
l = mid + ;
k -= c[lson[r_root]] - c[lson[l_root]];
l_root = rson[l_root];
r_root = rson[r_root];
}
}
return l;
}
int query(int root,int l,int r,int k)
{
if (l == r)
return l;
int mid = (l + r) >> ;
if (k <= mid)
return query(lson[root],l,mid,k);
else
return c[lson[root]] + query(rson[root],mid+,r,k);
}
ll bit_arr[maxn];
inline int lowbit (int x)
{
return x & -x;
}
void ADD(int x)
{
while (x < maxn)
{
bit_arr[x]++;
x += lowbit (x);
}
}
ll get_sum(int x)
{
ll res = ;
while (x)
{
res += bit_arr[x];
x -= lowbit (x);
}
return res;
}
struct
{
int x,y,k,flag;
}Q[maxn];
ll vec[maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
int n,cas = ;
while (~scanf ("%d",&n))
{
memset(bit_arr,,sizeof(bit_arr));
printf("Case %d:\n",cas++);
tot = idx = ;
for (int i = ; i < n; i++)
{
char op[];
scanf ("%s",op);
if (strcmp(op,"Insert") == )
{
int x;
scanf ("%d",&x);
Q[i].flag = ;
Q[i].x = x;
vec[idx++] = x;
}
if (strcmp(op,"Query_1") == )
{
int u,v,k;
scanf ("%d%d%d",&u,&v,&k);
Q[i].flag = ;
Q[i].x = u,Q[i].y = v,Q[i].k = k;
}
if (strcmp(op,"Query_2") == )
{
int x;
scanf ("%d",&x);
Q[i].flag = ;
Q[i].x = x;
}
if (strcmp(op,"Query_3") == )
{
int k;
scanf ("%d",&k);
Q[i].flag = ;
Q[i].x = k;
}
}
sort(vec,vec+idx);
idx = unique(vec,vec+idx) - vec;
maxv = idx ;
tree[] = build(,maxv);
int now = ;
ll ans1 = , ans2 = , ans3 = ;
for (int i = ; i < n; i++)
{
if (Q[i].flag == )
{
int tmp = lower_bound(vec,vec+idx,Q[i].x) - vec + ;
tree[now] = update(tree[now-],tmp,);
ADD(tmp);
now++;
}
if (Q[i].flag == )
{
ans1 += vec[query(Q[i].x,Q[i].y,Q[i].k)-];
}
if (Q[i].flag == )
{
int tmp = lower_bound(vec,vec+idx,Q[i].x) - vec + ;
ans2 += get_sum(tmp);
}
if (Q[i].flag == )
{
ans3 += vec[query(,now-,Q[i].x)-];
}
}
printf("%I64d\n%I64d\n%I64d\n",ans1,ans2,ans3);
}
return ;
}