本文主要是介绍[bzoj5042][笛卡尔树]LWD的分科岛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
大家都知道在文理分科的时候总是让人纠结的，纠结的当然不只是自己。比如 YSY 就去读了文科， LWD 知道了很
气。于是他就去卡了 BZOJ 测评机， 晚上他做了一个谜一样的梦，自己在一座全是 YSY 的分科岛。这里有 YSY
草， YSY 花， YSY 糖……每个 YSY 都有一个美（ Ti）丽（ Zhong）值。当然没有小于零的体重啦！LWD 于是不
惜重金卖肉想买下这座岛，可是分科岛的岛主，是一位忠实的区间问题爱好者。他想把小岛传给一个谜一样的爱好
者，所以岛主给了 LWD 一个终极挑战——选出一片区域中最美丽的 YSY。可是岛主的审美观不像 YYR那么专一，
他有时喜欢现代美——最轻的，有时喜欢唐代美——最重的。这让被欢喜冲昏了头脑（血液集中在下半身）的 LWD
十分苦恼。他要在规定时间内完成挑战赢得买岛的权利，于是只有求助 DalaoYYR，可是 YYR 要准备课件啊。只
有比 YYR 弱很多的你能够帮他了。挑战内容如下岛主将把 N 个 YSY 摆成一个条形，并给出所有 YSY 的美丽值。
挑出多少个就要看岛主心情了，他觉得 LWD 是条汉子就会给出很多很多的 YSY 满足他。岛主将给出 Q 个考验，
询问内容是在给定区间内求出最美丽的 YSY。你已经了解规则了，开始你的表演吧！
Input
第一行为一个整数 N，表示岛主摆出了 N 个 YSY。
接下来一行 N 个整数，表示每个 YSY 的美丽值(单位：kg)，因为 YSY 整体很美所以 YSY
不会超过 1019kg。
接下来一行一个整数 Q，表示岛主有 Q 个考验。Q<=1500000
接下来 Q 行，每行三个整数 opt, l, r 。 opt 等于 1 时表示岛主那时喜欢现代美，等于 2
时代表岛主那时喜欢唐代美。询问最美计划在区间[l, r]中进行
100%的数据 N<= 3000000, 美丽值不会超过 1019， Q<= 150000
数据量巨大，请优化读入
Output
每一行对于每个考验输出结果，以回车符结束。
Sample Input
5 5
1 2 3 4 5
1 1 2
2 1 3
1 2 5
2 4 5
2 1 5
Sample Output
1
3
2
5
5
这才是正经题解下面全是年轻废话…
对原数列建出笛卡尔树
然后两点之间的最值就是他们LCA的值
之后tarjan求一下LCA即可
笛卡尔树主要满足了两个性质
即左右儿子均满足不大于/不小于当前节点，并且左边节点的编号一定比他小，右边节点的编号一定比他大
建树的过程只需要维护右边一条链即可
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(void) {char ch=nc();int sum=0;while(!(ch>='0'&&ch<='9'))ch=nc();while(ch>='0'&&ch<='9')sum=(sum<<3)+(sum<<1)+(ch^48),ch=nc();return sum;
}
//inline int read()
//{
// int f=1,x=0;char ch=getchar();
// while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
// return x*f;
//}
int stack[20];
inline void write(int x)
{if(x<0){putchar('-');x=-x;}if(!x){putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x);putchar(' ');}
inline void pr2(int x){write(x);putchar('\n');}
const int MAXN=3000005;
struct egde{int x,y,o,next;}a[MAXN],b[MAXN];int len,last[MAXN],len1,last1[MAXN];
void ins1(int x,int y,int o){len1++;b[len1].x=x;b[len1].y=y;b[len1].o=o;b[len1].next=last1[x];last1[x]=len1;}
void ins(int x,int y){len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}int cal[MAXN],n,m;
int sta[MAXN],tp,root;
bool check(int u,int v,int o)
{if(o==1)return u<=v;else return u>=v;
}
void buildtree(int o)
{sta[tp=1]=1;for(int i=2;i<=n;i++){int lst=-1;while(tp&&check(cal[i],cal[sta[tp]],o)){if(lst!=-1)ins(sta[tp],lst);lst=sta[tp--];}if(lst!=-1)ins(i,lst);sta[++tp]=i;}while(tp>1)ins(sta[tp-1],sta[tp]),tp--;root=sta[1];
}
int rt[MAXN];
int findrt(int x){return rt[x]==x?x:rt[x]=findrt(rt[x]);}
//vector<pii> vec[MAXN];
int ok[MAXN],fa[MAXN],tim,ID,ans[MAXN];
void DFS(int x)
{for(int k=last[x];k;k=a[k].next){int y=a[k].y;fa[y]=x;DFS(y);}ok[x]=tim;for(int k=last1[x];k;k=b[k].next){int y=b[k].y;if(ok[y]==tim)ans[b[k].o]=cal[findrt(y)];}int up=findrt(fa[x]);rt[x]=up;
}
struct ed{int l,r,o;}w[MAXN];
int main()
{n=read();m=read();for(int i=1;i<=n;i++)cal[i]=read();for(int i=1;i<=m;i++)w[i].o=read(),w[i].l=read(),w[i].r=read();for(int i=1;i<=m;i++)if(w[i].o==1)ins1(w[i].l,w[i].r,i),ins1(w[i].r,w[i].l,i);tim++;buildtree(1);for(int i=1;i<=n;i++)rt[i]=i;DFS(root);tim++;len=0;memset(last,0,sizeof(last));len1=0;memset(last1,0,sizeof(last1));for(int i=1;i<=m;i++)if(w[i].o==2)ins1(w[i].l,w[i].r,i),ins1(w[i].r,w[i].l,i);buildtree(2);for(int i=1;i<=n;i++)rt[i]=i;DFS(root);for(int i=1;i<=m;i++)pr2(ans[i]);return 0;
}
下面全是废话
正经题解前说的话
写了这篇题解没想到帮了这么多被毒瘤题卡住的人。。
不过我还真想到了除了On的rmq外的东西。就是可持久化01tire
对于每个点反着建01tire，即高位的深度较低
然后像主席树那样合并起来搞可持久化数据结构。。
这样可以弄出来一个空间小于st表时间小于线段树的东西
至于我是怎么想到的？？这个魅力值<=1019很可疑啊
但是我发现我又被卡空间了。。各路神犇可以指导一下吗
//这是MLE的代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{int lc,rc,c0,c1;//lc 0 rc 1
}tr[30000005];int tot;
int tmp[15];
void getlen(int x)
{int p=11;if(x==0){for(int i=1;i<=11;i++)tmp[i]=0;return ;}while(x){tmp[p--]=x%2;x/=2;}for(int i=1;i<=p;i++)tmp[i]=0;
}
int rt[3100000];
void add()
{int x=++tot;for(int i=1;i<=11;i++){if(tmp[i]==0){tr[x].c0++;tr[x].lc=++tot;x=tr[x].lc;}else {tr[x].c1++;tr[x].rc=++tot;x=tr[x].rc;}}
}
void merge(int &x,int y)
{if(x==0){x=y;return ;}if(y==0)return ;tr[x].c0+=tr[y].c0;tr[x].c1+=tr[y].c1;merge(tr[x].lc,tr[y].lc);merge(tr[x].rc,tr[y].rc);
}
int bin[20],ans;
int solmax(int x,int y)
{ans=0;int px=x,py=y;for(int i=11;i>=1;i--){int c=tr[px].c1-tr[py].c1;if(c>0){ans+=bin[i];px=tr[px].rc;py=tr[py].rc;}else if(tr[px].c0-tr[py].c0>0){px=tr[px].lc;py=tr[py].lc;}else break;}return ans;
}
int solmin(int x,int y)
{ans=0;int px=x,py=y;for(int i=11;i>=1;i--){int c=tr[px].c0-tr[py].c0;if(c>0){px=tr[px].lc;py=tr[py].lc;}else if(tr[px].c1-tr[py].c1>0){ans+=bin[i];px=tr[px].rc;py=tr[py].rc;}else break;}return ans;
}
int main()
{int n,m;scanf("%d%d",&n,&m);bin[1]=1;for(int i=2;i<=15;i++)bin[i]=bin[i-1]*2;tot=0;for(int i=1;i<=n;i++){int x;scanf("%d",&x);getlen(x);rt[i]=tot+1;add();merge(rt[i],rt[i-1]);}while(m--){int op,l,r;scanf("%d%d%d",&op,&l,&r);if(op==1)printf("%d\n",solmin(rt[r],rt[l-1]));else printf("%d\n",solmax(rt[r],rt[l-1]));}return 0;
}
题解
首先，说点东西。。每个询问长度才1000左右？？？？？
所以这可以投机一点st表。。但是估计是卡着时间过去的
还有。。不能定两个数组，两个数组都会炸。。还得一个数组拆开来用。。
所以说切了这题还是觉得很无奈。。
两个数组维护最大最小值然后Nlogn求吧。bzoj上大佬D说可以线性RMQ然而不会，就卡下数据吧。
正解好像是On的RMQ 可以参照一下OZY大佬的blog
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int mn[11][3000001],s[3000001],Log[3000001];
int ans[1500001];
int x[1500001],y[1500001],k[1500001];
int n,m;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
void premn()
{//mn[i][j]=min(mn[i-1][j],mn[i-1][j+1<<i])Log[0]=-1;for(int i=1;i<=n;i++)Log[i]=Log[i/2]+1;for(int i=1;(1<<i)<=n && i<=10;i++)for(int j=1;j+(1<<i)-1<=n && j<=n;j++){mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);}
}
int maxnum;
void premx()
{for(int i=1;i<=n;i++)mn[0][i]=s[i];for(int i=1;(1<<i)<=maxnum && i<=10;i++)for(int j=1;j+(1<<i)-1<=maxnum && j<=maxnum;j++){mn[i][j]=max(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);}
}
int main()
{
// freopen("naive.in","r",stdin);
// freopen("naive.out","w",stdout);n=read();m=read();for(int i=1;i<=n;i++){mn[0][i]=s[i]=read();}premn();int tmp=0;maxnum=0;for(int i=1;i<=m;i++){int op=read(),xx=read(),yy=read();if(op==1){int kk=Log[yy-xx+1];ans[i]=min(mn[kk][xx],mn[kk][yy-(1<<kk)+1]);}else{tmp++;x[tmp]=xx;y[tmp]=yy;k[tmp]=i;maxnum=max(maxnum,yy);}}premx();for(int i=1;i<=tmp;i++){int kk=Log[y[i]-x[i]+1];ans[k[i]]=max(mn[kk][x[i]],mn[kk][y[i]-(1<<kk)+1]);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0;
}
这篇关于[bzoj5042][笛卡尔树]LWD的分科岛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
