题目传送门
这题嘛，一拿到手，我第一反应是线段树套平衡树……然后就被ZH大佬D了：“这题不是排个序加平衡树就好了吗？”
QAQ，大佬就是大佬，一针见血的解决了题目。然后JYZ来问：“这一定是一道很难的题目吧？”“不会啊，一道傻逼模板题罢了。”ZH大佬淡淡的说。
（JYZ大佬只是在装弱罢了，他太强了，不过一个大佬%比他弱的人是要降RP的）
这题的题目中明确指出：每个区间不互相包含。
因此我们可以把所有的询问排个序，然后维护一棵平衡树，平衡树内的所有节点为当前询问区间内的所有狗狗的漂亮值。
在区间转换时，只需要删去前面多余的节点，增加后面需要的节点，维护平衡树就行了。
附上AC代码：
#include <cstdio> #include <cctype> #include <algorithm> #include <cstdlib> #define N 300010 using namespace std; struct note{ int x,y,w,wz; bool operator < (const note lyf) const { if (x==lyf.x) return y<lyf.y; return x<lyf.x; } }a[50010]; struct tree{ int w,g,size,rnd; }t[N]; int n,m,w[N],size,l,r,rt,son[N][2],ans[50010]; inline char nc(){ static char ch[100010],*p1=ch,*p2=ch; return p1==p2&&(p2=(p1=ch)+fread(ch,1,100010,stdin),p1==p2)?EOF:*p1++; } inline void read(int &a){ static char c=nc();int f=1; for (;!isdigit(c);c=nc()) if (c=='-') f=-1; for (a=0;isdigit(c);a=a*10+c-'0',c=nc()); a*=f;return; } inline void turn(int &k,int x){ int p=son[k][x]; son[k][x]=son[p][x^1]; son[p][x^1]=k; t[k].size=t[son[k][0]].size+t[son[k][1]].size+t[k].g; t[p].size=t[son[p][0]].size+t[son[p][1]].size+t[p].g; k=p;return; } inline void ist(int &k,int x){ if (!k){ k=++size,t[k].w=x,t[k].g=t[k].size=1,t[k].rnd=rand(); return; } ++t[k].size; if (t[k].w==x) ++t[k].g; else if (t[k].w<x){ ist(son[k][1],x); if (t[son[k][1]].rnd<t[k].rnd) turn(k,1); } else{ ist(son[k][0],x); if (t[son[k][0]].rnd<t[k].rnd) turn(k,0); } return; } inline void del(int &k,int x){ if (!k) return; if (t[k].w==x){ if (t[k].g>1){ --t[k].g,--t[k].size; return; } if (son[k][0]*son[k][1]==0) k=son[k][0]+son[k][1]; else if (t[son[k][0]].rnd<t[son[k][1]].rnd) turn(k,0),del(k,x); else turn(k,1),del(k,x); } else{ --t[k].size; if (t[k].w<x) del(son[k][1],x); else del(son[k][0],x); } return; } inline int query(int k,int x){ if (!k||x>t[k].size||x<=0) return 0; if (t[son[k][0]].size+t[k].g<x) return query(son[k][1],x-t[son[k][0]].size-t[k].g); else if (t[son[k][0]].size+1>x) return query(son[k][0],x); else return t[k].w; } int main(void){ read(n),read(m); for (int i=1; i<=n; ++i) read(w[i]); for (int i=1; i<=m; ++i) read(a[i].x),read(a[i].y),read(a[i].w),a[i].wz=i; sort(a+1,a+1+m),l=1,r=0; for (int i=1; i<=m; ++i){ while (r<a[i].y) ist(rt,w[++r]); while (l<a[i].x) del(rt,w[l++]); ans[a[i].wz]=query(rt,a[i].w); } for (int i=1; i<=m; ++i) printf("%d\n",ans[i]); return 0; }