Codechef DEC16 SEAINCR

Problem

U are given an array $A$ consisting of $N$ integers.There are $M$ queries$(L_i,R_i)$and u are required to find the length of the longest increasing subsequence in the array $A[L_i...R_i]$
$1\le \sum A[i],N,M\le 10^6$

Approach

Since it is ensured that$\sum A[i]$is no more than $10^6$,we suppose $f[i][j]$ to be the maximum index of front of all the length-j increasing subsequences that end at i .
For example,$A[]={6,7,6,8,10}$
So $A[5]=4$ and $f[5][3]=3$
It is because that there are four length-3 increasing subsquences that end at 5(they are {6,8,10},{6,7,10},{7,8,10},{6,8,10})and the maximum index of the beginning of them is 3(it is {6,8,10}).

Of cause $f[i][j]$ can be simply calculated with Segment Trees.And it is worth pointing out that u should create new points in Segment Tree only if you need because there may be lots of Segment Trees.
After solving $f[i][j]$,now we should consider how to deal with queries.Suppose our quIt is a typical way to solve problem by Binary Search.
Now we have a problem,how to check if there exists an increasing subsquence whose length is $x$ in $A[L..R]$.Well,it’s $f[i][j]$’s turn now.
Suppose $v$ to be the maximum $f[i][x](\forall i,L\le i\le R)$.The only thing we should do is to check if $v$ is no less than $L$.Obviously,our job is to find the maximum $f[i][x]$in a section and it can be solved simply by using another SGT.
But the time complexity of this approach is $O(n log^2n)$because we use Binary Search and SGT to check.
Now we consider another high-authority algorithm.There are M queries and we use Binary Search.Maybe we can get a high-authority algorithm by sorting the value of $f[i][j]$ and $L_i$of each query.As a matter of fact,it does work.After sorting these values in descending order,the SGT become something else.Let’s assume we still use SGT.Now when we get an $f[i][j]$,we add a tag in index i of SGT j.when we get a query$(L,R)$,we still use Binary Search and check if there are tags in a section of SGT x.Note that every time we add a tag,f[i][j]s are in descending order.That means when we get a query(L,R),the indexs of the leftmost tag in each SGT are no less than L.So we suppose $Lef[x]$to be the index of the leftmost tag in SGT x.And when we want to check a value $x$,just need to compare $Lef[x]$ and $R$,what’s more,if $Lef[x]\le R$ exits,it is a possible answer.
The above algorithm’s time complexity is $O(nlogn)$

Code

Here is my code:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;int get(){char ch;int s=0;bool bz=0;while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');if (ch=='-')bz=1;else s=ch-'0';while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';if (bz)return -s;return s;
}const int N = 1000000;int rt[N+10],vis[N+10],tim,tot;
struct pt{int l,r,v;
}tree[N*21+10];
int n,a[N+10],m,L[N+10],k,v[N+10],num[N+10];
int mv;void change(int &now,int l,int r,int x,int v){if (!now)now=++tot;if (l==r){tree[now].v=max(tree[now].v,v);return;}int mid=(l+r)/2;if(x<=mid)change(tree[now].l,l,mid,x,v);else change(tree[now].r,mid+1,r,x,v);tree[now].v=max(tree[tree[now].l].v,tree[tree[now].r].v);
}int getv(int now,int l,int r,int x,int y){if (!now)return 0;if (x<=l&&r<=y)return tree[now].v;int mid=(l+r)/2,v=0;if (x<=mid)v=getv(tree[now].l,l,mid,x,y);if (y>mid)v=max(v,getv(tree[now].r,mid+1,r,x,y));return v;
}int getmx(int now,int l,int r,int x){if (!now)return 0;if (r<=x)return tree[now].v;int mid=(l+r)/2;if (x<=mid)return getmx(tree[now].l,l,mid,x);return max(tree[tree[now].l].v,getmx(tree[now].r,mid+1,r,x));
}bool cmp(int x,int y){return a[x]<a[y];
}struct que{int v,ty,l,w;friend bool operator < (que a,que b){if (a.v!=b.v)return a.v>b.v;return a.ty<b.ty;}
}q[N*2+10];
int lef[N+10];
int ans[N+10];int main(){freopen("data.in","r",stdin);freopen("data.out","w",stdout);int t=get();fo(cas,1,t){n=get();m=get();tim++;tot=k=0;mv=0;fo(i,1,n){a[i]=get();num[i]=i;}sort(num+1,num+1+n,cmp);int kk=0,lst=0;fo(i,1,n){if (a[num[i]]>lst){kk++;lst=a[num[i]];}a[num[i]]=kk;}fo(i,1,n){L[i]=k+1;v[k+1]=i;fo(j,2,a[i]){v[k+j]=0;if (vis[j-1]<tim)continue;v[k+j]=getmx(rt[j-1],1,kk,a[i]-1);}fo(j,1,a[i])if (v[k+j]){mv=max(mv,j);if(vis[j]<tim){rt[j]=0;vis[j]=tim;}change(rt[j],1,kk,a[i],v[k+j]);}k+=a[i];}fo(i,1,tot)tree[i].l=tree[i].r=tree[i].v=0;fo(i,1,mv)rt[i]=0;k=0;fo(i,1,n){fo(j,1,a[i])if (v[L[i]+j-1]){q[++k].v=v[L[i]+j-1];q[k].ty=1;q[k].l=j;q[k].w=i;}}fo(i,1,m){int l=get(),r=get();q[++k].v=l;q[k].ty=2;q[k].w=r;q[k].l=i;}sort(q+1,q+1+k);tim++;fo(i,1,k)if (q[i].ty==1){if (vis[q[i].l]<tim){vis[q[i].l]=tim;lef[q[i].l]=N;}lef[q[i].l]=min(lef[q[i].l],q[i].w);}else{int L=1,R=mv,va=0;while(L<=R){int mid=(L+R)/2;if (vis[mid]==tim&&lef[mid]<=q[i].w){va=mid;L=mid+1;}else R=mid-1;}ans[q[i].l]=va;}fo(i,1,m)printf("%d\n",ans[i]);}return 0;
}