hdu3727Jewel(劃分樹+二分)

題目請戳這裡

題目大意：給許多操作，4類：

1，insert x，插入一個數x，x範圍2^31内（題目描述有誤）

2，query_1 s t k，查詢範圍[s,t]内第k小的數，s<=t<=len(目前數字長度)

3,query_2 x   查詢x的rank，從小到大。x保證出現過

4，query_3 x，查詢[1,len]第x小的數。

輸出3個數，為3個詢問累加和。

題目分析：由于沒有删除操作，是以加入的數字序列是不變的，是以離線處理。

q1和q3其實是一個操作，查詢區間第k大值問題，劃分樹搞。

q2的話，其實也可以通過二分轉化為劃分樹操作。如果願意，寫棵線段樹單獨維護一下也是可以的，不過要離散化。為了偷懶，選擇二分+劃分樹啦

關于劃分樹，其實也是基于線段樹的一個資料結構，模拟歸并排序的過程，不斷分治。詳細講解戳這裡

詳情請見代碼：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100005;
const int M = 110005;
const int DEEP = 20;
typedef __int64 ll;
ll ans[3];
struct node
{
    int optype;
    int a,b,c;
}op[M];
int n,m;
char str[20];
int num[DEEP][N],lefta[DEEP][N],lcm[N];

void build(int s,int e,int nm,int dp)
{
    if(s == e)
        return;
    int mid = (s + e)>>1;
    int lsame = mid - s + 1;
    int i,same = 0;
    for(i = s;i <= e;i ++)
        if(num[dp][i] < lcm[mid])
            lsame --;
    int lpos = s,rpos = mid + 1;
    for(i = s;i <= e;i ++)
    {
        if(i == s)
            lefta[dp][i] = 0;
        else
            lefta[dp][i] = lefta[dp][i - 1];
        if(num[dp][i] < lcm[mid])
        {
            lefta[dp][i] ++;
            num[dp + 1][lpos ++] = num[dp][i];
        }
        else
        {
            if(num[dp][i] > lcm[mid])
                num[dp + 1][rpos ++] = num[dp][i];
            else
            {
                if(same < lsame)
                {
                    same ++;
                    lefta[dp][i] ++;
                    num[dp + 1][lpos ++] = num[dp][i];
                }
                else
                    num[dp + 1][rpos ++] = num[dp][i];
            }
        }
    }
    build(s,mid,nm<<1,dp + 1);
    build(mid + 1,e,nm<<1|1,dp + 1);
}
int query(int s,int e,int nm,int dp,int l,int r,int k)
{
    if(s == e)
        return num[dp][s];
    int mid = (s + e)>>1;
    int sa,sb;
    if(s == l)
        sb = 0;
    else
        sb = lefta[dp][l - 1];
    sa = lefta[dp][r] - sb;
    if(sa >= k)
    {
        int newl = s + sb;
        int newr = s + sb + sa - 1;
        return query(s,mid,nm<<1,dp + 1,newl,newr,k);
    }
    else
    {
        int bb = l - s - sb;
        int b = r - l + 1 - sa;
        int newl = mid + bb + 1;
        int newr = mid + bb + b;
        return query(mid + 1,e,nm<<1|1,dp + 1,newl,newr,k - sa);
    }
}
ll getans1(int a,int b,int c)
{
    int mid,la,ra;
    la = a;ra = b;
    while(la <= ra)
    {
        mid = (la + ra)>>1;
        int tmp = query(1,n,1,0,a,b,mid);
        if(tmp == c)
            return mid - a + 1;
        else if(tmp > c)
                ra = mid - 1;
            else
                la = mid + 1;
    }
}
int main()
{
    int i;
    int t,q,a,b,c,cas = 0;
    while(~scanf("%d",&q))
    {
        n = m = 1;
        while(q --)
        {
            scanf("%s",str);
            if(str[0] == 'I')
            {
                scanf("%d",&lcm[n]);
                num[0][n] = lcm[n ++];
            }
            else
            {
                if(str[strlen(str) - 1] == '1')
                {
                    scanf("%d%d%d",&a,&b,&c);
                    op[m].optype = 0;
                    op[m].a = a;op[m].b = b;op[m ++].c = c;
                }
                else if(str[strlen(str) - 1] == '2')
                    {
                        scanf("%d",&a);
                        op[m].optype = 1;
                        op[m].a = 1;op[m].b = n - 1;
                        op[m ++].c = a;
                    }
                    else
                    {
                        scanf("%d",&a);
                        op[m].optype = 2;
                        op[m].a = 1;op[m].b = n - 1;
                        op[m ++].c = a;
                    }
            }
        }
        sort(lcm + 1,lcm + n);
        n --;
        build(1,n,1,0);
        ans[1] = ans[0] = ans[2] = 0;
        for(i = 1;i < m;i ++)
        {
            if(op[i].optype == 1)
            {
                int tmp = getans1(op[i].a,op[i].b,op[i].c);
                ans[op[i].optype] += tmp;
            }
            else
            {
                int tmp = query(1,n,1,0,op[i].a,op[i].b,op[i].c);
                ans[op[i].optype] += tmp;
            }
        }
        printf("Case %d:\n%I64d\n%I64d\n%I64d\n",++cas,ans[0],ans[1],ans[2]);
    }
    return 0;
}
//265MS	15908K