[hdu4217]Data Structure?

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Data structure is one of the basic skills for Computer Science students, which is a particular way of storing and organizing data in a computer so that it can be used efficiently. Today let me introduce a data-structure-like problem for you.

Original, there are N N N numbers, namely 1 , 2 , 3... N 1, 2, 3...N 1,2,3...N. Each round, iSea find out the Ki-th smallest number and take it away, your task is reporting him the total sum of the numbers he has taken away.

Input

The first line contains a single integer T T T, indicating the number of test cases.

Each test case includes two integers N N N, K , K K, K K,K indicates the round numbers. Then a line with K K K numbers following, indicating in i i i (1-based) round, iSea take away the K i Ki Ki-th smallest away.

Technical Specification

1 <= T <= 128
1 <= K <= N <= 262 144
1 <= Ki <= N - i + 1
           

Output

For each test case, output the case number first, then the sum.

Sample Input

2
3 2
1 1
10 3
3 9 1
           

Sample Output

Case 1: 3
Case 2: 14
           

題意：

給定 n n n個數字 1 1 1到 n n n，将他們存在集合中，有 K K K組詢問，每次詢問一個數字 k i ki ki，将集合中的第 k i ki ki小的數字加到ans上，并将其從集合中删去，問 K K K次操作之後，ans為多少。

題解：

權值線段樹，每次查詢字首和為 k i + 1 ki+1 ki+1的位置，并将其設為0即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct seg{
    int l,r,w;
}tr[1000004];
int n;
ll ans;
void build(int k,int l,int r){
    tr[k].l=l;tr[k].r=r;
    if(l==r){
        tr[k].w=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tr[k].w=tr[k<<1].w+tr[k<<1|1].w;
}
int work(int k,int x){
    int l=tr[k].l,r=tr[k].r;
    if(l==r){
        ans+=l;
        tr[k].w=0;
        return l;
    }
    int mid=(l+r)>>1;
    if(tr[k<<1].w>=x)work(k<<1,x);
    else work(k<<1|1,x-tr[k<<1].w);
    tr[k].w=tr[k<<1].w+tr[k<<1|1].w;
}
int w33ha(int CASE){
    scanf("%d",&n);
    build(1,1,n);
    ans=0;
    int K;scanf("%d",&K);
    for(int i=1;i<=K;i++){
        int x;scanf("%d",&x);
        work(1,x);
    }
    printf("Case %d: %lld\n",CASE,ans);
    return 0;
}

int main(){
    int T;scanf("%d",&T);
    for(int i=1;i<=T;i++)w33ha(i);
    return 0;
}