(其實這篇部落格是為了寫主席樹的學習記錄的，可是看到闆子題可以用分塊寫，就心裡比較癢，小敲了一下，，，，)
題目：
（雙倍經驗：LUOGU P1533 可憐的狗狗）
題目連結：K-th Number
題意：給定的序列中求詢問區間的第k大的數
題解：
解法一：
主席樹：（這個本蒟蒻昨天才學，說實話樹上的很多資料結構 學的少，，，），說是可持久化線段樹，其實根據個人了解就是分層線段樹，建樹不斷更新連接配接進而達到一種可持久化的樹便于查詢。對于這道題就可以直接用主席樹解決，主席樹維護的是曆史版本的權值線段樹，那麼root[i]存的就是第i個權值線段樹的曆史版本，這樣的話要求[L,R]區間時，答案就是[L-1,R].。
解法二：
一看 資料結構題，一看求第k大，就知道分塊啊~~~
（可能是直覺吧，就覺得分塊能寫）上去就寫了個粗略的分塊，為什麼是粗略呢，，是沒有離散化啊，，，，結果就T掉了，，，，(Ｔ▽Ｔ)，還是要加上離散化的，但是加上離散化後就覺得既然沒有強制線上何妨不加個莫隊優化呢，（可能這又是直覺吧，，，）然後，，，，就過了，，，（開心(^_−)☆）
代碼：
主席樹寫法：
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
inline int read()
{
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int sea=1e5+7;
struct hit{int l,r,sum;}t[sea*40];
int n,m,x,y,k,cnt,a[sea],root[sea];//root[]就是第i棵樹
vector<int>v;
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}//離散化
void alter(int l,int r,int &x,int y,int pos)
{
t[++cnt]=t[y],t[cnt].sum++; x=cnt;//連接配接
if(l==r) return ;
int mid=(l+r)>>1;
if(mid>=pos) alter(l,mid,t[x].l,t[y].l,pos);
else alter(mid+1,r,t[x].r,t[y].r,pos);
}
int ask(int l,int r,int x,int y,int k)
{
if(l==r) return l;
int mid=(l+r)>>1;
int sum=t[t[y].l].sum-t[t[x].l].sum; //
if(sum>=k) return ask(l,mid,t[x].l,t[y].l,k);
else return ask(mid+1,r,t[x].r,t[y].r,k-sum);
}
int main()
{
n=read(), m=read();
for(int i=1;i<=n;i++) a[i]=read(),v.push_back(a[i]);
sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=n;i++) alter(1,n,root[i],root[i-1],getid(a[i]));
for(int i=1;i<=m;i++)
{
x=read(); y=read(); k=read();
printf("%d\n",v[ask(1,n,root[x-1],root[y],k)-1]);
}
return 0;
}
粗略分塊寫法（會TLE）
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,w[10010];
int belong[10010],l[10010],r[10010];
vector<int> vec[10010];
inline void srt(int x)
{
vec[x].clear();
for(int i=l[x]; i<=r[x]; i++) vec[x].push_back(w[i]);
sort(vec[x].begin(),vec[x].end());
}
inline void buildbl()
{
int len=sqrt(n),num=n/len;
if(n%len) num++;
for(int i=1; i<=num; i++) l[i]=(i-1)*len+1,r[i]=i*len; r[num]=n;
for(int i=1; i<=n; i++) belong[i]=(i-1)/len+1;
for(int i=1; i<=num; i++) srt(i);
}
inline int judge(int li,int ri,int wi)
{
int ans=0;
if(belong[li]==belong[ri])
{
for(int i=li; i<=ri; i++)
if(wi>w[i]) ans++;
return ans;
}
for(int i=li; i<=r[bel[li]]; i++) if(wi>w[i]) ans++;
for(int i=l[bel[ri]]; i<=ri; i++) if(wi>w[i]) ans++;
for(int i=belong[li]+1; i<=belong[ri]-1; i++)
ans+=lower_bound(vec[i].begin(),vec[i].end(),wi)-vec[i].begin();
return ans;
}
inline int binary(int li,int ri,int k)
{
int ans;
int x=(-1)*inf,y=inf;
while(x<=y)
{
int mid=(x+y)>>1;
if(judge(li,ri,mid)<k) ans=mid,x=mid+1;
else y=mid-1;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) scanf("%d",&w[i]);
buildbl();
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
printf("%d\n",binary(x,y,z));
}
}
分塊+莫隊優化
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int sea=1e5+7;
struct hit{int l,r,k,id;}q[sea];
struct beat{int v,id;}t[sea];
int n,m,cnt,num,block,a[sea],f[sea],belong[sea],l[sea],r[sea],ans[sea],v[sea],sumv[sea];
bool cmpt(beat a,beat b){if(a.v==b.v) return a.id<b.id;else return a.v<b.v;}
bool cmpq(hit a,hit b){if(belong[a.l]==belong[b.l])return a.r<b.r;else return a.l<b.l;}
void build()
{
block=sqrt(n);num=n/block; if(n%block) num++;
for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=block*i; r[n]=num;
}
void add(const int &x){++f[x]; ++sumv[belong[x]];}
void del(const int &x){--f[x]; --sumv[belong[x]];}
int Kth(const int &x)
{
int c=0;
for(int i=1;;i++)
{
c+=sumv[i];
if(c>=x)
{c-=sumv[i]; for(int j=l[i];;j++){c+=f[j];if(c>=x) return j;}}
}
}
int main()
{
n=read(); m=read();
for(int i=1;i<=n;i++) t[i].v=read(),t[i].id=i;
sort(t+1,t+n+1,cmpt); v[a[t[1].id]=++cnt]=t[1].v;
for(int i=2;i<=n;i++)
{
if(t[i].v!=t[i-1].v) ++cnt;
v[a[t[i].id]=cnt]=t[i].v;
}
build();
for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].k=read(),q[i].id=i;
sort(q+1,q+m+1,cmpq);
int L=1,R=0,Ans=0;
for(int i=1;i<=m;i++)
{
while(L>q[i].l) L--,add(a[L]);
while(L<q[i].l) del(a[L]),L++;
while(R<q[i].r) R++,add(a[R]);
while(R>q[i].r) del(a[R]),R--;
ans[q[i].id]=v[Kth(q[i].k)];
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}