2015
09-17

# The LCIS on the Tree

For a sequence S1, S2, … , SN, and a pair of integers (i, j), if 1 <= i <= j <= N and Si < Si+1 < Si+2 < … < Sj-1 < Sj , then the sequence Si, Si+1, … , Sj is a CIS (Continuous Increasing Subsequence). The longest CIS of a sequence is called the LCIS (Longest Continuous Increasing Subsequence).
Now we consider a tree rooted at node 1. Nodes have values. We have Q queries, each with two nodes u and v. You have to find the shortest path from u to v. And write down each nodes’ value on the path, from u to v, inclusive. Then you will get a sequence, and please show us the length of its LCIS.

The first line has a number T (T <= 10) , indicating the number of test cases.
For each test case, the first line is a number N (N <= 105), the number of nodes in the tree.
The second line comes with N numbers v1, v2, v3 … , vN, describing the value of node 1 to node N. (1 <= vi <= 109)
The third line comes with N – 1 numbers p2, p3, p4 … , pN, describing the father nodes of node 2 to node N. Node 1 is the root and will have no father.
Then comes a number Q, it is the number of queries. (Q <= 105)
For next Q lines, each with two numbers u and v. As described above.

The first line has a number T (T <= 10) , indicating the number of test cases.
For each test case, the first line is a number N (N <= 105), the number of nodes in the tree.
The second line comes with N numbers v1, v2, v3 … , vN, describing the value of node 1 to node N. (1 <= vi <= 109)
The third line comes with N – 1 numbers p2, p3, p4 … , pN, describing the father nodes of node 2 to node N. Node 1 is the root and will have no father.
Then comes a number Q, it is the number of queries. (Q <= 105)
For next Q lines, each with two numbers u and v. As described above.

1
5
1 2 3 4 5
1 1 3 3
3
1 5
4 5
2 5

Case #1:
3
2
3

#include<map>
#include<cstdio>
#include<iostream>
using namespace std;
#define ll  unsigned long long
#define mod 123
#define maxn 111111
map<ll,int>mp;
ll wei[maxn],h[maxn];
char ss[maxn];
int m,l,sum=0;
int main(){
wei[1]=1;
for(int i=2;i<=100011;++i)wei[i]=wei[i-1]*mod;

while(~scanf("%d%d%s",&m,&l,ss+1)){
sum=0;
int len=(int)strlen(ss+1);
int duan=m*l;
h[0]=0;
for(int i=1;i<=len;++i){
h[i]=(ss[i]-'a'+1)+h[i-1]*mod;
}
ll ans;

for(int i=1;i+duan-1<=len&&i<=l;++i){
mp.clear();
int st=i-1,ed=i-1;
while(ed+=l){
ans=h[ed]-h[ed-l]*wei[l+1];
mp[ans]++;
if(ed-st==duan){break;}
}
if(mp.size()==m){
sum++;
}
while(1){
if(ed+l>len)break;
st+=l;
ans=h[st]-h[st-l]*wei[l+1];
mp[ans]--;
if(mp[ans]==0)mp.erase(ans);
ed+=l;
ans=h[ed]-h[ed-l]*wei[l+1];
mp[ans]++;
if(mp.size()==m)sum++;
}
}
printf("%d\n",sum);
}
return 0;
}