微网站下载资料怎么做,WordPress怎么文章分类,界面ui设计,wordpress 分类目录 导航A simple rmq problem 题目大意#xff1a;给定一个长度为$n$的序列#xff0c;给出$m$个询问#xff1a;在$[l,r]$之间找到一个在这个区间里只出现过一次的最大的数。 注释#xff1a;$1\le n\le 10^5$#xff0c;$1\le mle 2\cdot 10^5$。 想法#xff1a; 我的第一想法…A simple rmq problem 题目大意给定一个长度为$n$的序列给出$m$个询问在$[l,r]$之间找到一个在这个区间里只出现过一次的最大的数。 注释$1\le n\le 10^5$$1\le mle 2\cdot 10^5$。 想法 我的第一想法是莫队。 结果发现是强制在线离线我也不会... 想了想其实$KD-Tree$还是比较显然的。 我们设$l_i$表示$a_i$上一次出现的位置$r_i$表示下一次。 紧接着我们把第$i$个数转化为三维坐标轴上的点$(l_i,i,r_i)$。 用$KD-Tree$维护直接查即可。 Code #include iostream
#include cstdio
#include cstring
#include algorithm
#define N 100010
using namespace std;
int v[N],lst[N],dic[N],nxt[N],d,l,r,ans,rt;
char *p1,*p2,buf[100000];
#define nc() (p1p2(p2(p1buf)fread(buf,1,100000,stdin),p1p2)?EOF:*p1)
int rd() {int x0,f1; char cnc(); while(c48) {if(c-) f-1; cnc();} while(c47) x(((x2)x)1)(c^48),cnc(); return x*f;}
inline void Max(int x,int y) {xxy?x:y;}
inline void Min(int x,int y) {xxy?x:y;}
struct Node {int p[3],mx[3],mn[3],ans,size,val,ls,rs;}a[N];
inline bool cmp(const Node a,const Node b)
{for(int i0;i3;i) if(a.p[(di)%3]!b.p[(di)%3]) return a.p[(di)%3]b.p[(di)%3];return true;
}
inline void pushup(int x,int k)
{a[x].sizea[k].size;for(int i0;i3;i) Max(a[x].mx[i],a[k].mx[i]),Min(a[x].mn[i],a[k].mn[i]);Max(a[x].ans,a[k].ans);
}
int build(int l,int r,int now)
{int mid(lr)1;dnow; nth_element(al,amid,ar1,cmp);for(int i0;i3;i) a[mid].mx[i]a[mid].mn[i]a[mid].p[i];a[mid].ansa[mid].val;if(lmid) a[mid].lsbuild(l,mid-1,(now1)%3),pushup(mid,a[mid].ls);if(midr) a[mid].rsbuild(mid1,r,(now1)%3),pushup(mid,a[mid].rs);return mid;
}
bool judge(int x)
{return a[x].ansansa[x].mx[0]la[x].mn[0]ra[x].mn[1]la[x].mx[2]r;
}
void query(int x)
{if(!x||!judge(x)) return;if(a[x].p[0]la[x].p[0]ra[x].p[1]la[x].p[2]r) Max(ans,a[x].val);query(a[x].ls); query(a[x].rs);
}
int main()
{int nrd(),mrd();for(int i1;in;i) v[i]rd(),lst[i]dic[v[i]],nxt[dic[v[i]]]i,dic[v[i]]i;for(int i1;in;i) a[i].p[0]i,a[i].p[1]lst[i],a[i].p[2]nxt[i]?nxt[i]:n1,a[i].valv[i];rtbuild(1,n,0); while(m--){l(rd()ans)%n1,r(rd()ans)%n1; if(lr) swap(l,r);ans0,query(rt); printf(%d\n,ans);}return 0;
}小结$KD-Tree$虽然是一个暴力但是它的思想还是非常不错的。转载于:https://www.cnblogs.com/ShuraK/p/10243973.html
