玄学アルゴリズムCDQ分治

ああ、これを勉强したばかりで、ちょうど1つの问题を过ぎたばかりで、おべっかを使ってブログを书くのはとても虚しいですbzoj 4553はこの问题です
私のCDQ分治に対する理解を話してください.のこれは似ています.暴力を、転化させる.最適化されやすい暴力.のそして最適化??
また一般的には,問題の単調性を有する問題,すなわちf[i]が任意のf[j](j={1..i}に影響を及ぼさない処理にのみ用いられる.
例えば最長上昇サブシーケンスの問題
私たちはもともとこのjを列挙する必要があるが,CDQ分治によってすべて列挙する必要はない.
我々が1~nを処理するとき,1~n/2がすべて処理済みであれば,1~n/2の結果でn/2+1~nの結果を更新することができる.
ここでは、n/2+1~n/2+n/4を列挙してn/2+n/4を更新するので、計算するのではなく、更新することに注意してください.
これにより、f[i]は彼より小さいすべてのポイントに更新されます.
ここでは,最も長い上昇サブシーケンスの例を挙げ,暴力dpは明らかにn^2であるが,上記の考えは,何の処理も加えなければよい.n^2で定数まで大きくなります
しかし、a[i]でソートするなど、前の値についていくつかの処理を行うことができます.
同時に後の値処理に対して、私達は線形に押すことができて、一回の更新の時間を2(r-l)に最適化して、全体の時間の効率もn*log nに最適化しました
では、最初に言った問題を見てみましょう.実は私たちは
a[i]，
n^2 dp ， min,max j しかありません.
正確性は明らかである.
ではCDQ分治を考えると
今回は2次元の条件があり、明らかに1つのソート後も前の値がすべて取れるように確保できないので、どうすればいいのでしょうか.
ソート後は明らかに1次元の条件しかありません.CDQをもう1つセットセットします.ツリー配列を使って、重み値の接頭辞とを記録すればいいです.
自分でもよくわからないから
CODE:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1e9
#define ll long long
#define For(i,j,k) for(ll i=j;i<=k;i++)
#define Dow(i,j,k) for(ll i=k;i>=j;i--)
using namespace std;
int n,m,a[100001],f[100001],ff[100001],mi[100001],mx[100001],num[100001];
inline bool cmp1(int x,int y)
{
    return mi[x]inline bool cmp2(int x,int y)
{
    return a[x]inline int lowbit(int x){return x&-x;}
void add(int x,int v)
{
for(int i=x;i<=100001;i+=lowbit(i)) if (v!=0)ff[i]=max(ff[i],v);else ff[i]=0;   
}
int get(int x)
{
int sum=0;
for(int i=x;i;i-=lowbit(i)) sum=max(sum,ff[i]);
return sum;
}
void solve (int l,int r)
{
if(l==r)
{
f[l]=max(f[l],1);
return;
}   
int mid=(l+r)>>1;
solve(l,mid);
For(i,l,r)  num[i]=i;
sort(num+l,num+mid+1,cmp2);sort(num+mid+1,num+r+1,cmp1);
int poi=l;
For(i,mid+1,r)
{
while(a[num[poi]]<=mi[num[i]]&&poi<=mid)
add(mx[num[poi]],f[num[poi]]),poi++;
f[num[i]]=max(f[num[i]],get(a[num[i]])+1);
}
For(i,l,poi)    add(mx[num[i]],0);
solve(mid+1,r);
}
int main()
{
scanf("%d%d",&n,&m);
For(i,1,n)  scanf("%d",&a[i]),mx[i]=mi[i]=a[i];
For(i,1,m)
{
int x,y;
scanf("%d%d",&x,&y);
mx[x]=max(mx[x],y);
mi[x]=min(mi[x],y);
}
solve(1,n);
int ans=0;
For(i,1,n)  ans=max(ans,f[i]);
printf("%d",ans);
}