[BZOJ] 2083: [Poi2010]Intelligence test

2083: [Poi2010]Intelligence test

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 597  Solved: 311
[Submit][Status][Discuss]

Description

霸中智力测试机构的一项工作就是按照一定的规则删除一个序列的数字，得到一个确定的数列。Lyx很渴望成为霸中智力测试机构的主管，但是他在这个工作上做的并不好，俗话说熟能生巧，他打算做很多练习，所以他希望你写一个程序来快速判断他的答案是否正确。

Input

第一行为一个整数m（1<=m<=1000000）第二行包括m个用空格分开的整数ai（1<=ai<=1000000），组成了最初的序列，第三行为一个整数n（1<=n<=1000000），表示n个Lyx经过一系列删除得到的序列，每个序列两行，第一行给出长度L（1<=L<=m），然后下一行为L个由空格分开的整数bi（1<=bi<=1000000）。

Output

共n行，如果Lyx的序列确实是由最初的序列删除一些数得到，就输出TAK，否则输出NIE。

Sample Input

7
1 5 4 5 7 8 6
4
5
1 5 5 8 6
3
2 2 2
3
5 7 8
4
1 5 7 4

Sample Output

TAK
NIE
TAK
NIE

HINT

 

Source

Analysis

据说这是范围暴露算法典型，，，

对的

对原初序列里每一个数字建一个地址表

记录每个数字出现的位置

然后录入待查找序列

对待查找里的每个数字相应的地址表进行二分

看会不会有矛盾

如果不会就....

Bi的范围有点问题，不要压线开vector

Code

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;

vector<int> pos_list[101010];

int find(int val,int pos){
    if(!pos_list[val].size()) return -1;
    int L = 0,R = pos_list[val].size()-1;
    while(L < R){
        int mid = (L+R)/2;
        if(pos_list[val][mid] <= pos) L = mid+1;
        else R = mid;
    }return pos_list[val][L];
}

int n,cnt,m,T;

int main(){
    scanf("%d",&n);
    
    for(int i = 1;i <= n;i++){
        scanf("%d",&cnt);
        pos_list[cnt].push_back(i);
    }
    
    scanf("%d",&m);
    while(m--){
        scanf("%d",&T);
        
        int last = 0;
        for(int i = 1;i <= T;i++){
            scanf("%d",&cnt);
            if(last == -1) continue;
            int pos = find(cnt,last);
            if(pos > last) last = pos;
            else{
                last = -1;
            }
        }if(last < 0) printf("NIE
");
        else printf("TAK
");
    }
    
    return 0;
}