http://acm.tju.edu.cn/toj/showp3758.html
TJU 3758. Jewel
模拟题，开始数组为空，有以下操作：
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)
要求统计每种问题的答案
分析：对于问题1和3可用划分树解决，对于问题2用树状数组解决，注意用树状数组前需要对数据离散化
View Code
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
struct Q//问题
{
int kind;//问题类型
int x,k;
int s,t;
int ans;
}q[35000*4+10];
const int MAXN = 100000+10;
int tree[22][MAXN],toleft[22][MAXN];
int sorted[MAXN];//已经排好序的数据
int c[MAXN];
inline int low(int x)
{
return (x&(-x));
}
void add(int x, int n)
{
while( x <= n)
{
c[x] ++;
x += low(x);
}
}
LL Sum(int x)
{
LL ans = 0;
while(x > 0)
{
ans += c[x];
x -= low(x);
}
return ans;
}
void build_tree(int left,int right,int deep)//建树
{
if(left==right)return;
int mid = (left+right)>>1;
int i;
int same = mid-left+1;//位于左子树的数据
for(i=left;i<=right;i++) //计算放于左子树中与中位数相等的数字个数
{
if(tree[deep][i]<sorted[mid])
same--;
}
int ls = left;
int rs = mid+1;
for(i=left;i<=right;i++)
{
int flag = 0;
if((tree[deep][i]<sorted[mid])||(tree[deep][i]==sorted[mid]&&same>0))
{
flag = 1;
tree[deep+1][ls++] = tree[deep][i];
if(tree[deep][i]==sorted[mid])same--;
}
else
{
tree[deep+1][rs++] = tree[deep][i];
}
toleft[deep][i]=toleft[deep][i-1]+flag;
}
build_tree(left,mid,deep+1);
build_tree(mid+1,right,deep+1);
}
int query(int left,int right,int k,int L,int R,int deep)
{
if(left==right)return tree[deep][left];
int mid = (L+R)>>1;
int x = toleft[deep][left-1]-toleft[deep][L-1];//位于left左边的放于左子树中的数字个数
int y = toleft[deep][right] - toleft[deep][L-1];//到right为止位于左子树的个数
int ry = right-L-y;//到right右边为止位于右子树的数字个数
int cnt = y-x;//[left,right]区间内放到左子树中的个数
int rx = left-L-x;//left左边放在右子树中的数字个数
if(cnt>=k)
return query(L+x,L+y-1,k,L,mid,deep+1);
else
return query(mid+rx+1,mid+1+ry,k-cnt,mid+1,R,deep+1);
}
int find(int x,int left,int right)
{
int ans = 0;
while(left<=right)
{
int mid = (left+right)>>1;
if(x==sorted[mid])return mid;
if(x<sorted[mid])
right=mid-1;
else
left=mid+1;
}
return ans;
}
int main()
{
int op = 0;
int cases = 0;
while(scanf("%d",&op)!=EOF)
{
cases++;
int n = 1;
int qnum = 0;//问题个数
while(op--)
{
char str[20];
scanf("%s",str);
if(str[0]=='I')
{
scanf("%d",&sorted[n]);
tree[0][n]=sorted[n];
n++;
}
else
{
int len = strlen(str);
if(str[len-1]=='1')
{
q[qnum].kind = 1;
scanf("%d%d%d",&q[qnum].s,&q[qnum].t,&q[qnum].k);
qnum++;
}
else
if(str[len-1]=='2')
{
q[qnum].kind = 2;
scanf("%d",&q[qnum].x);
q[qnum].t = n-1;
qnum++;
}
else
if(str[len-1]=='3')
{
q[qnum].kind = 3;
scanf("%d",&q[qnum].k);
q[qnum].s=1;
q[qnum].t = n-1;
qnum++;
}
}
}
sort(sorted+1,sorted+n);
memset(c,0,sizeof(c));
int i,pre = 1;
build_tree(1,n-1,0);
LL sum1=0,sum2=0,sum3=0;
for(i=0;i<qnum;i++)
{
if(q[i].kind==1)
{
//query(int left,int right,int k,int L,int R,int deep)
sum1+=query(q[i].s,q[i].t,q[i].k,1,n-1,0);
}
else
if(q[i].kind==3)
{
sum3+=query(q[i].s,q[i].t,q[i].k,1,n-1,0);
}
else
{
for(;pre<=q[i].t;pre++)
{
int index = find(tree[0][pre],1,n-1);
add(index,n-1);
}
int index=find(q[i].x,1,n-1);
//printf("%ld\n",Sum(index));
sum2+=Sum(index);
}
}
printf("Case %d:\n",cases);
cout<<sum1<<endl;
cout<<sum2<<endl;
cout<<sum3<<endl;
// printf("%I64d\n%I64d\n%I64d\n",sum1,sum2,sum3);
}
return 0;
}