D 套娃
这个trick是真没见过，也难怪场上没几个人过这个代码这么简单的题
题目大意
给定一排 \(n\) 个套娃，套娃的大小互不相同。你可以将相邻两个套娃套在一起，问最多能套几
次？
题解
发现可以\(O(n)\)的判断一个长度为\(n\)的套娃序列是否能合并成一个，接下来从左边开始就可以贪心地往右扩展，尽量地让更多的套娃合并成一个，到合并不了的地方，说明只能合并这么多了
接下来就想到二分右端点，然后用\(O(n)\)的算法来进行二分的判断，但直接做复杂度是\(O(n^2\log n)\)的
接下来比较精髓的trick就是，先用倍增确定二分的一个右端点，然后再二分，这样可以就可以让二分区间的长度去到\(O(n\log n)\)，加上二分的复杂度，总复杂度就是\(O(n\log^2 n)\)的
代码
点击查看代码
#include<cstdio>
#include<algorithm>
using namespace std;
void read(int &res)
{
res=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
const int N=1e5+100;
int T,n,a[N+10],p[N+10];
bool cmp(int x,int y)
{
return a[x]<a[y];
}
struct node
{
int l,r;
}sta[N+10];
int top;
bool check(int l,int r)
{
for(int i=l;i<=r;i++)
p[i]=i;
sort(p+l,p+1+r,cmp);
top=0;
for(int i=l;i<=r;i++)
{
sta[++top]=(node){p[i],p[i]};
while(top>1)
{
if(sta[top].l==sta[top-1].r+1)
{
sta[top-1].r=sta[top].r;
top--;
continue;
}
if(sta[top].r+1==sta[top-1].l)
{
sta[top-1].l=sta[top].l;
top--;
continue;
}
break;
}
}
return top==1;
}
int main()
{
// freopen("d.in","r",stdin);
read(T);
for(;T--;)
{
read(n);
for(int i=1;i<=n;i++) read(a[i]);
int Ans=0;
for(int i=1;i<=n;i++)
{
int k=0;
while(i+(1<<k)-1<=n&&check(i,i+(1<<k)-1)) k++;
int l=i,r=min(n,i+(1<<k)-1),mid,ans=i;
while(l<=r)
{
mid=l+r>>1;
if(check(i,mid))
ans=mid,l=mid+1;
else
r=mid-1;
}
Ans++;
i=ans;
}
printf("%d\n",n-Ans);
}
return 0;
}