首页 > ACM题库 > HDU-杭电 > HDU 3727-Jewel-字符串-[解题报告]HOJ
2015
02-21

HDU 3727-Jewel-字符串-[解题报告]HOJ

Jewel

问题描述 :

Jimmy wants to make a special necklace for his girlfriend. He bought many beads with various sizes, and no two beads are with the same size. Jimmy can’t remember all the details about the beads, for the necklace is so long. So he turns to you for help.

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)

输入:

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.
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)

输出:

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.
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)

样例输入:

10
Insert 1
Insert 4
Insert 2
Insert 5
Insert 6
Query_1 1 5 5
Query_1 2 3 2
Query_2 4
Query_3 3
Query_3 1

样例输出:

Case 1:
10
3
5

Hint
The answers for the 5 queries are 6, 4, 3, 4, 1, respectively.

题目大意

对一个序列进行以下四种操作:

1、Insert x 在序列尾部插入x

2、Query_1 s t k 查询区间[s,t]的第k小

3、Query_2 x 查询x的在序列中排名

4、Query_3 k 查询序列中的第k小

题解

第一个和第二个显然是主席树能够实现的功能,第三四个操作用vector+lower_bound就可以实现,妈蛋,写完交上去一直WA,fuck,然后把存储操作类型的每个字符串的大小从10改成15居然变RE了!!!才发现用来存储操作的数组开小了,只开到100000。。。改完就A了。。。3687MS,好慢。。。假设插入操作为n,其他操作位m,时间复杂度是nlogn+mlogn 应该没有这么慢的说啊,莫非是lower_bound调用次数太多,所以耗时很多?

代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 100005
#define lson l,m,ls[s]
#define rson m+1,r,rs[s]
typedef long long LL;
int ls[20*MAXN],rs[20*MAXN];
int cnt[20*MAXN],T[MAXN];
int a[MAXN],num[MAXN];
char op[2*MAXN][15];
int L[2*MAXN],R[2*MAXN],K[2*MAXN];
int tot;
vector<int>ivec;
void build(int l,int r,int &s)
{
    s=++tot;
    cnt[s]=0;
    if(l==r) return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void update(int last,int p,int l,int r,int &s)
{
    s=++tot;
    ls[s]=ls[last],rs[s]=rs[last];
    cnt[s]=cnt[last]+1;
    if(l==r) return;
    int m=(l+r)>>1;
    if(p<=m) update(ls[last],p,lson);
    else     update(rs[last],p,rson);
}
int query(int ss,int tt,int l,int r,int k)
{
    if(l==r) return r;
    int sum=cnt[ls[tt]]-cnt[ls[ss]];
    int m=(l+r)>>1;
    if(sum>=k) return query(ls[ss],ls[tt],l,m,k);
    else       return query(rs[ss],rs[tt],m+1,r,k-sum);
}
int main()
{
    int m,kase=0;
    while(scanf("%d",&m)!=EOF)
    {
        memset(cnt,0,sizeof(cnt));
        int len=0,n;
        LL qy1=0,qy2=0,qy3=0;
        ivec.clear();
        for(int i=0; i<m; i++)
        {
            scanf("%s%d",op[i],&L[i]);
            if(!strcmp(op[i],"Insert"))
            {
                ++len;
                num[len]=a[len]=L[i];
            }
            else if(!strcmp(op[i],"Query_1"))
                scanf("%d%d",&R[i],&K[i]);
        }
        sort(a+1,a+len+1);
        n=len;
        len=unique(a+1,a+len+1)-a-1;
        for(int i=1; i<=n; i++) num[i]=lower_bound(a+1,a+len+1,num[i])-a;
        tot=0;
        build(1,len,T[0]);
        for(int i=1; i<=n; i++) update(T[i-1],num[i],1,len,T[i]);
        for(int i=0; i<m; i++)
        {
            if(!strcmp(op[i],"Insert"))
                ivec.insert(lower_bound(ivec.begin(),ivec.end(),L[i]),L[i]);
            else if(!strcmp(op[i],"Query_1"))
                qy1+=a[query(T[L[i]-1],T[R[i]],1,len,K[i])];
            else if(!strcmp(op[i],"Query_2"))
                qy2+=lower_bound(ivec.begin(),ivec.end(),L[i])-ivec.begin()+1;
            else
                qy3+=ivec[L[i]-1];
        }
        printf("Case %d:\n",++kase);
        printf("%I64d\n%I64d\n%I64d\n",qy1,qy2,qy3);
    }
    return 0;
}

参考:http://www.cnblogs.com/zjbztianya/archive/2013/10/03/3350699.html


  1. [email protected]

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n