bzoj2083[Poi2010]Intelligence test*

bzoj2083[Poi2010]Intelligence test

题意：

给出一个序列，m个询问，每次问一个序列是否为所给序列的子序列（可以不连续）。n≤1000000，m≤1000000，询问序列总长度≤1000000。

题解：

以元素的值为第一关键字，位置为第二关键字排序。接着对于每次询问，二分查找询问序列中元素在给出序列的最早出现次数，如果后一个数的最早出现次数大于等于前一个则输出NIE。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 1000010
 7 #define INF 0x3fffffff
 8 using namespace std;
 9 
10 inline int read(){
11     char ch=getchar(); int f=1,x=0;
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
14     return f*x;
15 }
16 struct nd{int v,id;}nds[maxn]; bool cmp(nd a,nd b){return a.v==b.v?a.id<b.id:a.v<b.v;}
17 int n,l,m;
18 int main(){
19     n=read(); inc(i,1,n)nds[i].v=read(),nds[i].id=i; sort(nds+1,nds+1+n,cmp); m=read(); nds[n+1].v=INF;
20     inc(i,1,m){
21         l=read(); int pos=0; bool f=0;
22         inc(j,1,l){
23             int x=read(); if(!f){
24                 int y=lower_bound(nds+1,nds+n+2,(nd){x,pos},cmp)-nds;
25                 if(nds[y].v!=x){puts("NIE"); f=1;} pos=nds[y].id+1;
26             }
27         }
28         if(!f)puts("TAK");
29     }
30     return 0;
31 }

20161107